⼆叉查树C++实现(含完整代码)
⼀般⼆叉树的查是通过遍历整棵⼆叉树实现,效率较低。⼆叉查树是⼀种特殊的⼆叉树,可以提⾼查的效率。⼆叉查树⼜称为⼆叉排序树或⼆叉搜索树。
⼆叉查树的定义
⼆叉排序树(Binary Search Tree)⼜称⼆叉排序树(Binary Sort Tree),或者是⼀颗空⼆叉树,或者是具有⼀下特性的⼆叉树:
1. 若它的左⼦树不为空,则左⼦树上的所有结点的值均⼩于根节点的值。
2. 若它的右⼦树不为空,则右⼦树上的所有结点的值均⼩于根节点的值。
3. 它的左右⼦树⼜分别是⼆叉排序树。
由定义可知,⼆叉查树中结点的值不允许重复。图a是⼀棵⼆叉查树。当加⼊结点90后如图b,图b的⼆叉树不是⼆叉查树,因其不满⾜⼆叉排序树的特性1.
图a 图b
⼆叉树的C++实现
1. ⼆叉查树的结点结构
template<typename T>
//树结点结构
class BSTNode{
public:
T _key; //关键在字(键值)
BSTNode *_lchild; //左孩
BSTNode *_rchild; //右孩
BSTNode *_parent; // 双亲
//构造函数
BSTNode(T key ,BSTNode *lchild,BSTNode *rchild,BSTNode *parent):
_key(key),_lchild(lchild),_rchild(rchild),_parent(parent){};
};
结点结构BSTNode中含有三个指针域,分别是:
1. _lchild,指向结点的左孩⼦。
2. _rchild,指向结点的右孩⼦。
3. _parent,指向结点的双亲。
包含⼀个数据域 _key,为结点的关键字值。
使⽤构造函数初始化表列对以上四个数据进⾏初始化。
2. ⼆叉查树的操作
template<typename T>
class BSTree{
private:
BSTNode<T> *_Root ; //根结点
public:
BSTree():_Root(NULL){};
~BSTree(){};
void insert (T key);//⼆叉树的插⼊
BSTNode<T>* search (T key) ;//⼆叉树的查
void preOrder() ; //先序输出
void inOrder() ; //中序输出
void postOrder() ; //后序输出
BSTNode<T>* minimumNode();//查最⼩的节点
BSTNode<T>* maximumNode ();//查最⼤的节点
T minimumKey();//查最⼩的键值
T maximumKey();//查最⼩的键值
void print();//打印⼆叉树
void remove(T key);
BSTNode<T>* predecessor(BSTNode<T>* x);//查某个结点的前驱
BSTNode<T>* sucessor(BSTNode<T>* x); //查某个结点的后继
void destory ();
//内部使⽤函数,供外部接⼝调⽤
private:
void insert(BSTNode<T>* &tree,BSTNode<T>* z);
BSTNode<T>* search(BSTNode<T>* &tree,T key) const;
void preOrder(BSTNode<T>*&tree) const;
void inOrder(BSTNode<T>*&tree) const;
void postOrder(BSTNode<T>*&tree) const;
BSTNode<T>* minimumNode(BSTNode<T> *&tree);
BSTNode<T>* maximumNode (BSTNode<T> *&tree);
void print(BSTNode<T>*& tree);
BSTNode<T>* remove(BSTNode<T>* &tree, BSTNode<T> *z);
void destory(BSTNode<T>*& tree);
};
BSTree类包含了⼀个BSTNode指针数据成员,代表⼆叉查树的根结点。类种封装了⼆叉查树常⽤的操作接⼝,包括:
二叉树中序遍历非递归算法1. 插⼊操作:也是建⽴⼆叉查树的⽅法。
2. 遍历算法:包括前序、中序、后序(递归实现)。
3. 查操作:包括查某个结点、查最⼩结点、查最⼤结点、查最⼩值、查最⼤值。
4. 删除操作。
5. 销毁操作。
6. 打印操作:打印说明⼆叉树的结构。
BSTree类⼤部分的函数都有两个重载版本,⼀个仅供类内部使⽤(privata声明),另⼀个则为类⽤户使⽤的公⽤接⼝(public声明)。
2.1⼆叉查树的遍历
2.1.1遍历⼆叉树
遍历⼆叉树是指从根结点出发,按照某种次序访问⼆叉树所有结点,使得每个结点被且仅被访问⼀次,这⾥的访问可以是输出、⽐较、更新、查看结点信息等各种操作。遍历是⼆叉树的⼀类重要操作,
也是⼆叉树的其他⼀些操作和各种应⽤算法的基本框架。⽤V表⽰根节点,⽤L表⽰左孩⼦,⽤R表⽰右孩⼦,且规定先L后R的访问顺序,则有VLR(前序)、LVR(中序)、LRV(后续)三种遍历算法。对于图a中的⼆叉树,其遍历结果为:
前序遍历:88 47 19 55 50 98
中序遍历:19 47 50 55 88 98
后序遍历:19 50 55 47 98 88
下⾯来看BSTtree提供的三种遍历接⼝:
前序遍历:
1. 访问根节点。
2. 遍历访问左⼦树。
3. 遍历访问右⼦树。
/*
*
*前序遍历算法
*BSTree类内部调⽤函数
*
*/
template<typename T>
void BSTree<T>::preOrder(BSTNode<T>*&tree) const {
if(tree)
{
cout<<tree->_key<<"";
preOrder(tree->_lchild);
preOrder(tree->_rchild);
}
}
/*
*接⼝
*
*/template<typename T>
void BSTree<T>::postOrder()
{
postOrder(_Root);
}
中序遍历:
1. 遍历访问左⼦树
2. 访问根节点。
3. 遍历访问右⼦树。
/*
*
*中序遍历算法
*类内部调⽤函数
*
*/
template <typename T>
void BSTree<T>::inOrder(BSTNode<T>*&tree) const {
if(tree)
{
inOrder(tree->_lchild);
cout<<tree->_key<<"";
inOrder(tree->_rchild);
}
}
/*
*
*接⼝
*
*/
template<typename T>
void BSTree<T>::inOrder()
{
inOrder(_Root);
}
后序遍历:
1. 遍历访问左⼦树。
2. 遍历访问右⼦树。
3. 访问根节点。
/*
*
*后序遍历算法
*类内部调⽤函数
*
*/
template <typename T>
void BSTree<T>::postOrder(BSTNode<T>*&tree) const
{
if(tree)
{
postOrder(tree->_lchild);
postOrder(tree->_rchild);
cout<<tree->_key<<"";
}
}
/*
*
*接⼝
*
*/
template<typename T>
void BSTree<T>::postOrder()
{
postOrder(_Root);
}
2.2⼆叉查树的插⼊
构建查⼆叉树通过⼆叉查树的插⼊操作来进⾏。插⼊时严格按照查⼆叉树的定义来进⾏,其插⼊算法的基本过程可以分解为:
1. 根结点为空则进⾏插⼊。
2. 值⽐根结点⼩,在根结点的左⼦树进⾏插⼊。
3. 值⽐根结点⼤,在根节点的右⼦树进⾏插⼊。
本⽂采⽤⾮递归算法实现插⼊操作。
/*
*插⼊操作
*⾮递归实现
*内部使⽤函数
*/
template<typename T>
void BSTree<T> ::insert(BSTNode<T>* &tree,BSTNode<T>* z)
{
BSTNode<T>* parent = NULL;
BSTNode<T>* temp = tree;
//寻插⼊点
while(temp!=NULL)
{
parent= temp;
if(z->_key>temp->_key)
temp= temp->_rchild;
else
temp=temp->_lchild;
}
z->_parent = parent;
if(parent==NULL) //如果树本来就是空树,则直接把z节点插⼊根节点
tree = z;
else if(z->_key>parent->_key) //如果z的值⼤于其双亲,则z为其双亲的右孩
parent->_rchild = z;
else
parent->_lchild = z;
}
/*
*
*接⼝
*/
template <typename T>
void BSTree<T>::insert(T key)
{
//创建⼀个新的节点,使⽤构造函数初始化
BSTNode<T>* z= new BSTNode<T>(key,NULL,NULL,NULL);
if(!z) //如果创建失败则返回
return ;
//调⽤内部函数进⾏插⼊
insert(_Root,z);
} 2.3 ⼆叉查树的查
2.3.1 查某个值的结点
这⾥提供递归与⾮递归算法实现查操作。
/*
*查操作
*⾮递归实现
*内部使⽤函数
*/
template <typename T>
BSTNode<T>* BSTree<T>::search(BSTNode<T>* &tree,T key) const
{
BSTNode<T>* temp = tree;
while(temp != NULL)
{
if(temp->_key == key)
return temp;
else if(temp->_key>key)
temp = temp->_lchild;
else
temp = temp->_rchild;
}
return NULL;
}
////查算法的递归实现
//template<typename T>
//BSTNode<T>* BSTree<T>::search( BSTNode<T>* &tree,T key) const
//{
// if(!tree)
// {
// if(tree->_key==key)
// return tree;
// if(tree->_key>key)
// return search(tree->_lchild,key);
/
/ if(tree->_key<z->_key)
// return search(tree->_rchild,key);
// }
// return NULL;
//}
/*
*接⼝
*/
template <typename T>
BSTNode<T> * BSTree<T>::search(T key)
{
return search(_Root,key);
}
2.3.2查⼆叉查树值最⼩的结点
/*
*
*查最⼩的结点
*内部调⽤函数
*
*/
template <typename T>
BSTNode<T>* BSTree<T>::minimumNode(BSTNode<T>*&tree)
{
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。
发表评论