首页 > 操作系统 >

算法学习记录搜索-二叉树（Binary Sort Tree）

电脑杂谈　发布时间：2020-07-14 20:29:41　来源：网络整理

平衡二叉树是排序树吗_树与二叉树的转换_二叉排序树排序

二进制排序树也称为二进制搜索号.

它具有以下属性:

如果其左子树不为空，则左子树上所有节点的值均小于其根节点的值.

如果其右子树不为空，则右子树上所有节点的值都大于其根节点的值.

左右子树也是二进制排序树.

上一个搜索，半个搜索，斐波那契搜索和插值搜索的前提条件是该序列是有序的并且是顺序存储结构. 正如我们在搜索一章中提到的，还有动态搜索，例如插入和删除操作，

对于顺序存储结构，这些操作效率不高. 静态搜索效率和动态搜索效率都可以同时存在吗？

在联想进行堆排序之前，人们创建了类似堆的结构来提高排序效率. （我很欣赏他们的想法）堆结构是建立在一棵二叉树上的，我还不知道二叉树是如何使用的，

在这里看到二叉树的作用，我们定义二叉排序树以实现具有高动态和静态搜索效率的结构.

首先举个例子:

让我们看看以无序顺序排列的二进制排序树:

在上图中，上面的数组是原始数组，下面的二进制排序树是根据上面的原始数组构造的.

二叉排序树排序_平衡二叉树是排序树吗_树与二叉树的转换

1. 如果我们以中间顺序遍历，则结果是序列的顺序. {0，1，2，3，4，5，6，7，8，9}

2. 我们实施静态搜索以找到关键字8:

从根节点开始，根节点（6）8大于6，向右（到节点（7））.

当前节点（7）8大于该节点二叉排序树排序，并向右（到节点（8））.

找到8.

这里类似于减半，斐波那契和插值搜索的想法. 因此，其静态搜索效率较高.

3. 动态搜索（插入和删除）

如果要在该序列中插入记录10，则只需为其找到合适的位置. 顺序遍历插入的二叉树时，它仍然是顺序列表.

在右边（节点7处）插入比根节点（6）大的10.

比当前节点（7）大（在节点8右边）

比当前节点（8）大（在节点9右边）

它比当前节点（9）大，在右边，没有子节点，然后创建一个子节点并分配值为10.

完成后，树的中阶遍历仍然是序列表，对原始树几乎没有影响，因此其插入操作也非常有效.

二叉排序树排序_树与二叉树的转换_平衡二叉树是排序树吗

要删除:

由于二进制排序树需要确保删除记录时顺序的遍历顺序不受影响，因此需要将操作分为几种情况，这会有些麻烦，下面将对此进行描述以后.

总的来说，这样的二进制排序树对于静态和动态操作基本上是有效的，从而避免了在插入和删除有序列表时大量记录的移动.

在这里，我看到了二进制排序数字的好处，

问题来了！

如何从无序序列构造这样的二进制排序树？

二叉排序树排序_平衡二叉树是排序树吗_树与二叉树的转换

通过上述过程，您基本上可以看到从无序列表到二进制排序树的构建过程.

本质是搜索和插入操作. 首先检查节点是否存在，然后进行比较，然后插入.

只要知道了主意，就可以编写程序.

插入算法如下:

 1 bool SearchBST(pBinNode T,myDataType key,pBinNode *pNode)//pNode是指针，需要修改，所以用二级指针,该指针用来记录要查找结点，若不存在则返回将插入结点的父结点。
 2 {                //根结点指针，寻找的值，记录父节点值
 3     if (T == NULL)//如果是空树，则父结点指向NULL
 4     {
 5         *pNode = NULL;
 6         return false;
 7     }
 8     pBinNode crntNode = T;
 9 
10     while(crntNode)//找到要插入结点的父结点
11     {
12         if (crntNode->data == key)
13         {
14             return true;
15         }
16         else if(crntNode->data > key)
17         {
18             *pNode = crntNode;
19             crntNode = crntNode->lchd;
20         }
21         else if (crntNode->data < key)
22         {
23             *pNode = crntNode;
24             crntNode = crntNode->rchd;
25         }
26     }
27     return false;
28 }
29 
30 bool insertBSTNode(pBinNode *T,int key,int index)//第一个参数之所以为二级指针，因为在该函数中有malloc生成的是指针，而要将该指针的值在函数中赋给另一个指针，所以要用指针的指针才能接收
31 {
32     pBinNode n=NULL;
33     pBinNode p=NULL;
34     if (false == SearchBST(*T,key,&p))//找到要插入的结点的父结点p
35     {
36         n = (pBinNode)malloc(sizeof(BinNode));
37         if (n == NULL)
38         {
39             printf("error:no more memery!\n");
40             return false;
41         }
42         (*n).data = key;
43         (*n).index = index;
44         (*n).lchd = NULL;
45         (*n).rchd = NULL;
46 
47         if (p == NULL)
48         {
49             *T = n;
50         }
51         else if(key < p->data)
52         {
53             p->lchd = n;
54         }
55         else if (key > p->data)
56         {
57             p->rchd = n;
58         }
59         return true;
60     }
61     else
62     {
63         return false;
64     }
65 }

请仔细考虑这种搜索是否可以使用递归调用方法.

删除操作，有以下三种删除情况:

要删除的节点是叶节点. 由于删除操作不会破坏树结构，因此只需要修改父节点以使其指向NULL，然后释放要删除的节点即可. 要删除的节点只有左子树或只有右子树. 您只需要将要删除的节点的父节点的子指针指向其（左/右）子树，然后释放要删除的节点. 要删除的节点同时具有左子树和右子树. 在这种情况下，无法将其作为上述两种方法进行处理.

最简单的方法是对他的左右子树重新排序，根据二进制排序树条件形成一个新的子树，然后连接到该树. 这将非常复杂. 如果根节点被删除，则意味着将重建整个树.

我们考虑二进制排序树的中序遍历，其中遍历是无序序列的有序集合.

我们删除其中一个节点二叉排序树排序，并通过调整方法尽可能减少对树结构的破坏. 只要可以确保调整后的树遍历仍然是调整后的有序集，那么这种调整就可以成功.

举几个例子:

树与二叉树的转换_平衡二叉树是排序树吗_二叉排序树排序

代码:

 1 void DeleteNode(pBinNode *fNode,pBinNode *sNode)//参数分别为 父亲 和 孩子
 2 {
 3     pBinNode q = NULL;
 4     pBinNode s = NULL;
 5     if ((*sNode)->rchd == NULL)//右子树为空，只要把它的左子树直接连上就行
 6     {
 7         q = *sNode;
 8         (*fNode)->rchd = (*sNode)->lchd;
 9         free(q);
10     }
11     else if((*sNode)->lchd == NULL)//左子树为空，只要把它的右子树直接连上就可以了。
12     {
13         q=*sNode;
14         (*fNode)->rchd = (*sNode)->rchd;
15         free(q);
16     }
17     else //左右都不为空！
18     {
19         q = *sNode;
20         s = (*sNode)->lchd;//其前驱一定是在左子树上的最后一个右分支
21         while(s->rchd)
22         {
23             q = s;
24             s=s->rchd;
25         }
26         (*sNode)->data = s->data;
27         if (q != *sNode)
28         {
29             q->rchd = s->lchd;
30         }
31         else
32         {
33             q->lchd= s->lchd;
34         }
35         free(s);
36 
37     }
38 }
39 
40 bool DeleteBST(pBinNode *T,int key)//找是否存在关键字
41 {
42     if (!(*T))
43     {
44         return false;
45     }
46 
47     pBinNode s = *T;//son
48     pBinNode f = NULL;//father
49 
50     while(s)
51     {
52         if(key == s->data)
53         {
54             //删除
55             DeleteNode(&f,&s);
56             return true;
57         }
58         else if (s->data > key)
59         {
60             f = s;
61             s = s->lchd;
62         }
63         else if (s->data < key)
64         {
65             f = s;
66             s = s->rchd;
67         }
68     }
69     return false;//no value in array
70 }

完整程序:

  1 #include <stdlib.h>
  2 
  3 typedef int myDataType;
  4 //myDataType src_ary[10] = {9,1,5,8,3,7,6,0,2,4};
  5 //myDataType src_ary[10] = {1,2,3,4,5,6,7,8,9,10};
  6 //myDataType src_ary[10] = {10,9,8,7,6,5,4,3,2,1};
  7 
  8 myDataType src_ary[10] = {6,1,7,5,3,8,9,0,2,4};
  9 
 10 //****************树结构***********************//
 11 typedef struct BTS{
 12     myDataType data;
 13     int index;
 14     struct BTS *lchd,*rchd;
 15 }BinNode,*pBinNode;
 16 
 17 void prt_ary(myDataType *ary,int len)
 18 {
 19     int i=0;
 20     while(i < len)
 21     {
 22         printf(" %d ",ary[i++]);
 23     }
 24     printf("\n");
 25 }
 26 
 27 bool SearchBST(pBinNode T,myDataType key,pBinNode *pNode)//pNode是指针，需要修改，所以用二级指针,该指针用来记录要查找结点，若不存在则返回将插入结点的父结点。
 28 {                //根结点指针，寻找的值，记录父节点值
 29     if (T == NULL)//如果是空树，则父结点指向NULL
 30     {
 31         *pNode = NULL;
 32         return false;
 33     }
 34     pBinNode crntNode = T;
 35 
 36     while(crntNode)//找到要插入结点的父结点
 37     {
 38         if (crntNode->data == key)
 39         {
 40             return true;
 41         }
 42         else if(crntNode->data > key)
 43         {
 44             *pNode = crntNode;
 45             crntNode = crntNode->lchd;
 46         }
 47         else if (crntNode->data < key)
 48         {
 49             *pNode = crntNode;
 50             crntNode = crntNode->rchd;
 51         }
 52     }
 53     return false;
 54 }
 55 
 56 bool insertBSTNode(pBinNode *T,int key,int index)//第一个参数之所以为二级指针，因为在该函数中有malloc生成的是指针，而要将该指针的值在函数中赋给另一个指针，所以要用指针的指针才能接收
 57 {
 58     pBinNode n=NULL;
 59     pBinNode p=NULL;
 60     if (false == SearchBST(*T,key,&p))//找到要插入的结点的父结点p
 61     {
 62         n = (pBinNode)malloc(sizeof(BinNode));
 63         if (n == NULL)
 64         {
 65             printf("error:no more memery!\n");
 66             return false;
 67         }
 68         (*n).data = key;
 69         (*n).index = index;
 70         (*n).lchd = NULL;
 71         (*n).rchd = NULL;
 72 
 73         if (p == NULL)
 74         {
 75             *T = n;
 76         }
 77         else if(key < p->data)
 78         {
 79             p->lchd = n;
 80         }
 81         else if (key > p->data)
 82         {
 83             p->rchd = n;
 84         }
 85         return true;
 86     }
 87     else
 88     {
 89         return false;
 90     }
 91 }
 92 
 93 
 94 
 95 void DeleteNode(pBinNode *fNode,pBinNode *sNode)//参数分别为 父亲 和 孩子
 96 {
 97     pBinNode q = NULL;
 98     pBinNode s = NULL;
 99     if ((*sNode)->rchd == NULL)//右子树为空，只要把它的左子树直接连上就行
100     {
101         q = *sNode;
102         (*fNode)->rchd = (*sNode)->lchd;
103         free(q);
104     }
105     else if((*sNode)->lchd == NULL)//左子树为空，只要把它的右子树直接连上就可以了。
106     {
107         q=*sNode;
108         (*fNode)->rchd = (*sNode)->rchd;
109         free(q);
110     }
111     else //左右都不为空！
112     {
113         q = *sNode;
114         s = (*sNode)->lchd;//其前驱一定是在左子树上的最后一个右分支
115         while(s->rchd)
116         {
117             q = s;
118             s=s->rchd;
119         }
120         (*sNode)->data = s->data;
121         if (q != *sNode)
122         {
123             q->rchd = s->lchd;
124         }
125         else
126         {
127             q->lchd= s->lchd;
128         }
129         free(s);
130 
131     }
132 }
133 
134 bool DeleteBST(pBinNode *T,int key)//找是否存在关键字
135 {
136     if (!(*T))
137     {
138         return false;
139     }
140 
141     pBinNode s = *T;//son
142     pBinNode f = NULL;//father
143 
144     while(s)
145     {
146         if(key == s->data)
147         {
148             //删除
149             DeleteNode(&f,&s);
150             return true;
151         }
152         else if (s->data > key)
153         {
154             f = s;
155             s = s->lchd;
156         }
157         else if (s->data < key)
158         {
159             f = s;
160             s = s->rchd;
161         }
162     }
163     return false;//no value in array
164 }
165 
166 int _tmain(int argc, _TCHAR* argv[])
167 {
168     int i;
169     pBinNode T=NULL;//排序树的根结点
170 
171     for (i=0;i<10;i++)//创建树
172     {
173         if (false == insertBSTNode(&T,src_ary[i],i))
174         {
175             printf("error:src_ary[%d]=%d\n",i,src_ary[i]);
176         }
177     }
178     DeleteBST(&T,6);//删除6
179     //DeleteBST(&T,8);
180     getchar();
181     return 0;
182 }