C++实现二叉排序树

  1 #ifndef _TREENODE_H_
  2 #define _TREENODE_H_
  3 #define datatype int
  4 #include <iostream>
  5 using namespace std;
  6 class BSTNODE
  7 {
  8 public:
  9     datatype key;
 10     BSTNODE* leftchild;
 11     BSTNODE* rightchild;
 12 };
 13 typedef BSTNODE* BSTtree;
 14 BSTNODE* searchbst(BSTNODE* bst, datatype k)//查找非递归实现
 15 {
 16     BSTNODE* q;
 17     q = bst;
 18     while (q)//当次课二叉排序不为空的时候，开始查找
 19     {
 20         if (q->key == k){
 21             return q;//当根节点的datatype就是要找的时候直接返回。
 22         }
 23         if (k < q->key){
 24             q = q->leftchild;
 25         }
 26         else
 27             q = q->rightchild;
 28     }
 29 
 30     return nullptr;//没找到
 31 }
 32 
 33 /*
 34 BSTNODE* searchbst(BSTNODE* bst, datatype k)//查找的递归实现
 35 {
 36 if (!bst)return nullptr;//这棵树为空，不存在查找的必要
 37 else if (bst->key == k){
 38 return bst;
 39 }
 40 else if (bst->key > k){
 41 return searchbst(bst->leftchild, k);
 42 }
 43 else{
 44 return searchbst(bst->rightchild, k);
 45 }
 46 }
 47 */
 48 
 49 void insertbst(BSTtree* bst, datatype k)//二叉排序树的插入
 50 {
 51     BSTtree s;
 52     if ((*bst) == nullptr){
 53         s = (BSTtree)malloc(sizeof(BSTNODE));
 54         s->key = k;
 55         s->leftchild = nullptr;
 56         s->rightchild = nullptr;
 57         *bst = s;
 58     }
 59     else if (k < (*bst)->key){
 60         insertbst(&((*bst)->leftchild), k);
 61     }
 62     else{
 63         insertbst((&(*bst)->rightchild), k);
 64     }
 65 }
 66 
 67 void createbst(BSTtree *bst)//建立排序二叉树
 68 {
 69     datatype key;
 70     *bst = nullptr;
 71     cout << "输入8个数字构造二叉排序树: ";
 72     for (int i = 0; i < 8; i++)
 73     {
 74         cin >> key;
 75         insertbst(bst, key);
 76     }
 77 }
 78 
 79 BSTNODE* del(BSTNODE *bst, datatype k)//删除某一个节点
 80 {
 81     BSTNODE *p,*f,*q,*s;
 82     p = bst;
 83     f = nullptr;
 84     while (p){
 85         if (p->key == k)break;
 86         f = p;
 87         if (p->key < k)p = p->rightchild;
 88         else p = p->leftchild;
 89     }
 90 
 91                     
 92     if (p == nullptr){
 93         return bst;
 94     }
 95 
 96     if (p->leftchild == nullptr){
 97         if (f == nullptr){
 98             bst = p->rightchild;
 99         }
100         else if (f->leftchild == p)f->leftchild = p->rightchild;
101         else f->rightchild = p->rightchild;
102 
103         free(p);
104     }
105     else{
106         q = p;
107         s = p->leftchild;
108         while (s->rightchild){
109             q = s;
110             s = s->rightchild;
111         }
112         if (q == p){
113             q->leftchild = s->leftchild;
114         }
115         else{
116             q->rightchild = s->leftchild;
117         }
118         p->key = s->key;
119         free(s);
120     }
121     return bst;
122 }
123 
124 void visit(BSTtree root){
125     cout << root->key << " ";
126 }
127 
128 void preprint(BSTtree root){
129     if (root){
130         visit(root);
131         preprint(root->leftchild);
132         preprint(root->rightchild);
133     }
134 }
135 
136 void inprint(BSTtree root){
137     if (root){
138 
139         inprint(root->leftchild);
140         visit(root);
141         inprint(root->rightchild);
142     }
143 }
144 
145 void postprint(BSTtree root){
146     if (root){
147         
148         postprint(root->leftchild);
149         postprint(root->rightchild);
150         visit(root);
151     }
152 }
153 
154 
155 
156 #endif

tou.h

1、二叉排序树：是一种高效的数据结构。

性质：（1）若果他的左子树不为空，则左子树上的所有节点的值都小于根节点的值。

（2）若他的右子树不为空，则右子树上的所有节点的值都大于根节点的值。

（3）他的左右子树也分别是二叉排序树。

注意：（1）对一颗二叉排序树进行中序遍历，可以得到一个递增的有序序列。这也是二叉排序树的原由。

（2）由于二叉树可以看成一个有序表，所以在二叉排序树上进行的查找类似于折半查，就是逐步缩小查找范围的过程。

1、若给定值等于根节点的关键字，则查找成功。

2、若给定值小于根节点的关键字，则继续在左子树上进行查找。

3、若给定值大于根节点的关键字，则继续在右子树上进行查找。

bsttree search(bsttree bst,datatype){

bsttree q;
q = bst;
while(q){
if(q->key == k)return q;
if(q->key>k)q=q->leftchild;
else{q = q->rightchild;}
}  
return NULL;
}

2、二叉排序树的插入：

首先查找待插入的记录是否在树中，如果存在则不允许插入重复关键字。如果找到叶子节点人没有发现关键字，则把待插入节点作为新的叶子节点插入。

void insertbst(bstree *bst,datatype k){
bitree s;
if(*bst == NULL)
{
s = (bsttree)malloc(sizeof(bstnode));
s->key = k;
s->leftchild = NULL;
s->rightchild = NULL;
*bst = s;
}
else if(k<(*bst)->key)insert(&(*bst)->leftchild,k);
eles if(k>(*bst)->key)insert(&(*bst)->rightchild,k);
}

3、二叉排序树的建立：

二叉排序树的建立是基于插入算法进行的，根据给定的关键字的顺序依次插入得到的。

void createbst(bstree *bst)
{
datatype key;
*bst = NULL;
cout<<"输入二叉树元素"<<endl;
for(int i = 0;i<N;i++)
{
cin>>key;
instrtbst(bst,Key);
}
}

void createbst(bstree *bst)
{
datatype key;
*bst = NULL;
cout<<"输入二叉树元素"<<endl;
for(int i = 0;i<N;i++)
{
cin>>key;
instrtbst(bst,Key);
}
}

4、二叉排序树的删除：

二叉排序树要求关键字之间满足某种大小关系，这就使得从树中删除一个节点的算法相对复杂。首先在二叉排序树中查找待删除的节点，不存在不做操作，否则分三种情况讨论：

（1）待删除节点是叶子节点（2）待删除节点之后右/左子树（3）待删除节点有左右子树

看第三种情况：只需要将带删除节点的父亲节点的相应孩子域之为该孩子对应的左子树或右子树。

bstnode * del(bsttree bst,datatype k)
{
bstnode*p,*f,*s,*q;
p = bst;
f= NULL;
while(p){
if(p->key == k) break;
f = p;
if(p->key>k) p = p->lchild;
else p = p->rchild;
}
if(p == NULL) return bst;
if(p->lchild == NULL){
if(f == NULL){ bst = p->rchild;}
else if(f->lchild == p){f->lchild = p->rightchild;}
else {f->rchild = p->rchild;}
free(p);
}
eles{
q = p;
s = p->lchild;
while(s->rchild){
q = s;
s = s->rchild;
}
if(q == p)
{
q->lchild = s->lchild;
}
else{
q->rchild = s->lchild;
p->key = s->key;
free(s);
}
}
return bst;
}

5、二叉排序树的性能分析：

二叉排序树的最慢查找速度相当于顺序查找。

但是对于二叉排序树的删除和吵着来说，只需要修改某些节点的指针域，不需要大量的移动其他的记录，动态查找的效率更高！