数据结构【查找】—二叉树排序以及查找-蒲公英云

讲解：

　　总结一句话：

　　　　小的左边，大的放右边。

　　特点：　　　　

　　　　二叉排序树（Binary Sort Tree），又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。

　　　　若它的左子树不空，则左子树上所有结点的值均小于它的根结构的值；

　　　　若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；　　

　　　　它的左、右子树也分别为二又排序树。

二叉树创建代码：

1 //创建二叉树
 2 void InsertBST(BiTree* &T, int elem) {
 3     BiTree *p = new  BiTree;
 4     p->data = elem;
 5     p->lchild = NULL;
 6     p->rchild = NULL;
 7     if (!T) {
 8         T = p;//为空树        
 9         return;
10     }
11 
12     if (T->data == elem)
13         return;//此数已经存在
14 
15     while (true) {
16         if (elem > T->data) {
17             if (T->rchild != NULL)
18                 T = T->rchild;//走到最右端
19             else {
20                 T->rchild = p;//添加为右子树
21                 return;
22             }
23         }
24         else {
25             if (T->lchild != NULL)
26                 T = T->lchild;//走到最左端
27             else {
28                 T->lchild = p;//添加为左子树
29                 return;
30             }
31         }
32     }
33 
34 }

　　二叉树排序：

　　　　通过二叉树的中序遍历，得到的就是一个有序数组

　　代码：　　

1 void ShowTree(BiTree *T) {
2     //进行中序浏览
3     if (T) {
4         ShowTree(T->lchild);
5         cout << T->data << "—>";
6         ShowTree(T->rchild);
7     }
8 }

二叉树查找：

　　使用递归，通过比较大小来找到左子树或右子树。

　　二叉树查找代码：　　

1 //对二叉树进行查找工作
2 int SearchData(BiTree *T, int num) {
3     if (!T)return 0;
4     if (T->data == num)return 1;
5     if (num > T->data)SearchData(T->rchild,num);
6     else SearchData(T->lchild, num);
7 }

二叉树的删除是重点也是难点：

　　当要删除节点位于右端末，即无右子树，则用它的左子树接替他的位置；

　　当要删除节点位于左端末，即无左子树，则用它的右子树接替他的位置；

　　当要删除节点位于中间，即既有左子树，又有右子树，用左子树的最大数代替，即左子树的最右端末。

　删除代码：

1 //进行删除
 2 //重点，也是难点
 3 int Delete(BiTree* &T) {
 4     BiTree *p, *q;
 5     if (T->rchild == NULL) {
    //若该结点没有右子树，则将该节点的左子树代替其，并删除
 6         p = T;
 7         T = T->lchild;
 8         delete(p);
 9     }
10     else if (T->lchild == NULL) {
    //若该结点没有左子树，则将该节点的右子树代替其，并删除
11         p = T;
12         T = T->rchild;
13         delete(p);
14     }
15     else {
    //左右子树都存在
16         p = T;
17         q = T->lchild;
18         while (q->rchild) {
    //走到T左支的末端，此时他是左边最大的数
19             p = q;//记住前端点
20             q = q->rchild;
21         }
22         T->data = q->data;//前驱的数字用最右端数字代替
23         if (p != T)//将末端的左孩子连接，因为此时他是左端最大的数字
24             p->rchild = q->lchild;
25         else
26             p->lchild = q->lchild;//重接左子树
27         delete(q);//释放左端最大值
28     }
29     return 1;
30 }
31 
32 
33 //对二叉树进行删除操作
34 int DeleteBST(BiTree* &T, int num) {
35     if (!T)return false;
36     if (num == T->data) {
37         Delete(T);
38         return true;
39     }
40     else if (num > T->data)DeleteBST(T->rchild, num);
41     DeleteBST(T->lchild, num);
42 }

完整代码：

1 #include "000库函数.h"
  2 
  3 #define MAXSIZE 100
  4 
  5 
  6 //二叉树的结构
  7 struct BiTree
  8 {
  9     int data;
 10     BiTree *lchild, *rchild;
 11 };
 12 
 13 //创建二叉树
 14 void InsertBST(BiTree* &T, int elem) {
 15     BiTree *p = new  BiTree;
 16     p->data = elem;
 17     p->lchild = NULL;
 18     p->rchild = NULL;
 19     if (!T) {
 20         T = p;//为空树        
 21         return;
 22     }
 23 
 24     if (T->data == elem)
 25         return;//此数已经存在
 26 
 27     while (true) {
 28         if (elem > T->data) {
 29             if (T->rchild != NULL)
 30                 T = T->rchild;//走到最右端
 31             else {
 32                 T->rchild = p;//添加为右子树
 33                 return;
 34             }
 35         }
 36         else {
 37             if (T->lchild != NULL)
 38                 T = T->lchild;//走到最左端
 39             else {
 40                 T->lchild = p;//添加为左子树
 41                 return;
 42             }
 43         }
 44     }
 45 
 46 }
 47 
 48 void ShowTree(BiTree *T) {
 49     //进行中序浏览
 50     if (T) {
 51         ShowTree(T->lchild);
 52         cout << T->data << "—>";
 53         ShowTree(T->rchild);
 54     }
 55 }
 56 
 57 //对二叉树进行查找工作
 58 int SearchData(BiTree *T, int num) {
 59     if (!T)return 0;
 60     if (T->data == num)return 1;
 61     if (num > T->data)SearchData(T->rchild,num);
 62     else SearchData(T->lchild, num);
 63 }
 64 
 65 
 66 //进行删除
 67 //重点，也是难点
 68 int Delete(BiTree* &T) {
 69     BiTree *p, *q;
 70     if (T->rchild == NULL) {
    //若该结点没有右子树，则将该节点的左子树代替其，并删除
 71         p = T;
 72         T = T->lchild;
 73         delete(p);
 74     }
 75     else if (T->lchild == NULL) {
    //若该结点没有左子树，则将该节点的右子树代替其，并删除
 76         p = T;
 77         T = T->rchild;
 78         delete(p);
 79     }
 80     else {
    //左右子树都存在
 81         p = T;
 82         q = T->lchild;
 83         while (q->rchild) {
    //走到T左支的末端，此时他是左边最大的数
 84             p = q;//记住前端点
 85             q = q->rchild;
 86         }
 87         T->data = q->data;//前驱的数字用最右端数字代替
 88         if (p != T)//将末端的左孩子连接，因为此时他是左端最大的数字
 89             p->rchild = q->lchild;
 90         else
 91             p->lchild = q->lchild;//重接左子树
 92         delete(q);//释放左端最大值
 93     }
 94     return 1;
 95 }
 96 
 97 
 98 //对二叉树进行删除操作
 99 int DeleteBST(BiTree* &T, int num) {
100     if (!T)return false;
101     if (num == T->data) {
102         Delete(T);
103         return true;
104     }
105     else if (num > T->data)DeleteBST(T->rchild, num);
106     DeleteBST(T->lchild, num);
107 }
108 
109 int T032(void)
110 {
111     int i;
112     int a[10] = { 62,88,58,47,35,73,51,99,37,93 };
113     BiTree *T = new BiTree;
114     T = NULL;
115     BiTree *p;
116     for (i = 0; i < 10; i++) {
117         InsertBST(T, a[i]);
118         if (i == 0)
119             p = T;//记住头结点的位置
120         T = p;//仍然返回头结点，从头结点开始重新遍历
121     }
122     ShowTree(T);
123     cout << endl;
124     cout << "找到没？" << endl << SearchData(T, 99) << endl;
125     p = T;//记住头结点
126     DeleteBST(T, 93);
127     T = p;
128     ShowTree(T);
129     cout << endl;
130     p = T;//记住头结点
131     DeleteBST(T, 37);
132     T = p;
133     ShowTree(T);
134     cout << endl;
135     return 0;
136 }