二叉搜索树

一、二叉搜索树的特点

二叉搜索树的特点：对于树中的每个节点X，它的左子树中所有关键字值小于X的关键字值，而它的右子树中所有关键字值大于X的关键字值。

根据这个性质，对一个二叉树进行中序遍历，如果是单调递增的，则可以说明这个树是二叉搜索树。

LeetCode题目98:验证二叉搜索树(https://leetcode-cn.com/problems/validate-binary-search-tree/)就可以对这个二叉树进行中序遍历，然后判断是否单调递增的，如果是单调递增的，说明是二叉搜索树。否则不是二叉搜索树。

二、二叉搜索树的查找

过程：首先和根节点进行比较，如果等于根节点，则返回。如果小于根节点，则在根节点的左子树进行查找。如果大于根节点，则在根节点的右子树进行查找。

 1 /* 查找以t为根节点的树中，是否包含x */
 2 Position Find(ElementType x, SearchTree t)
 3 {
 4     if (t == NULL) {
 5         return NULL;
 6     } else if (x < t->element) {
 7         return Find(x, t->left);
 8     } else if (x > t->element) {
 9         return Find(x, t->right);
10     } else {
11         return t;
12     }
13 }

View Code

三、查找最大值和最小值

查找最小值：从根开始，如果有左儿子，则向左进行。直到左儿子为空，则当前节点为最小值。

 1 Position FindMin(SearchTree t)
 2 {
 3     if (t == NULL) {
 4         return NULL;
 5     } else if (t->left == NULL) {
 6         return t;
 7     } else {
 8         return FindMin(t->left);
 9     }
10 }

View Code

查找最大值：从根开始，如果有右儿子，则向右进行。直到右儿子为空，则当前节点为最大值。

 1 Position FindMax(SearchTree t)
 2 {
 3     if (t == NULL) {
 4         return NULL;
 5     }
 6 
 7     while (t->right != NULL)
 8     {
 9         t = t->right;
10     }
11     return t;  
12 }

View Code

这里查找最小值运用了递归，而查找最大值运用了非递归实现。

四、二叉搜索树的插入

二叉搜索树的插入过程和查找类似。新插入的节点一般在遍历的路径上的最后一点上，即叶子节点。如果待插入的数据比当前节点的数据大，并且当前节点的右儿子为空，则将待插入的节点插到右儿子位置上。如果右儿子不为空，则再递归的遍历右儿子。如果小于当前节点，则对左儿子做类似的处理就行。

 1 SearchTree Insert(ElementType x, SearchTree t)
 2 {
 3     if (t == NULL) {
 4         /* 插入第一个节点 */
 5         t = (SearchTree)malloc(sizeof(struct TreeNode));
 6         if (t == NULL) {
 7             return NULL;
 8         }
 9         t->element = x;
10         t->left = NULL;
11         t->right = NULL;
12     } else if (x < t->element) {
13         t->left = Insert(x, t->left);
14     } else if (x > t->element) {
15         t->right = Insert(x, t->right);
16     }
17     return t;
18 }

View Code

五、二叉搜索树的删除

二叉搜索树的删除分为以下几个情况：

1、待删除的节点是一个叶子节点，即它没有左右儿子。此时只要将它的父节点指向NULL即可。

2、如果节点有一个儿子，则该节点可以在其父节点调整指针绕过该节点后删除。

3、如果有两个儿子，一般的删除策略是用其右子树中最小的数据代替该节点的数据并递归地删除那个节点。因为右子树中最小地节点不可能有左儿子(如果有，则说明不是最小的)，所以第二次删除更容易。(其实也就是将有两个儿子的情况转为容易处理的情况1或者2)。

 1 /* 删除策略
 2  * 1、如果待删除节点只有一个儿子，则将该节点的父节点的儿子节点指针指向该节点的儿子节点，
 3  * 然后删除该节点.
 4  * 2、如果待删除节点有两个儿子，用右子树中最小的数据代替该节点的数据并递归地删除那个节点。
 5  * 因为右子树中最小地节点不可能有左儿子，所以第二次删除更容易.
 6  */
 7  SearchTree Delete(ElementType x, SearchTree t)
 8  {
 9      Position tmp;
10      if (t == NULL) {  
11          return NULL;
12      }
13      if (x < t->element) {
14          t->left = Delete(x, t->left);
15      } else if (x > t->element) {
16          t->right = Delete(x, t->right);
17      } else if (t->left && t->right) {
18          tmp = FindMin(t->right);
19          t->element = tmp->element;
20          t->right = Delete(t->element, t->right);
21      } else {
22          tmp = t;
23          if (t->left) {
24              t = t->left;
25          } else if (t->right) {
26              t = t->right;
27          }
28          free(tmp);
29          tmp = NULL;
30      }
31      return t;
32  }

View Code

六、建立一棵空树

 1 SearchTree MakeEmpty(SearchTree t)
 2 {
 3     if (t != NULL) {
 4         MakeEmpty(t->left);
 5         MakeEmpty(t->right);
 6         free(t);
 7         t = NULL;
 8     }
 9     return NULL;
10 }

View Code

附录：

完整代码：

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 #define ElementType int
  5 struct TreeNode;
  6 typedef struct TreeNode *Position;
  7 typedef struct TreeNode *SearchTree;
  8 
  9 SearchTree MakeEmpty(SearchTree t);
 10 Position Find(ElementType x, SearchTree t);
 11 Position FindMin(SearchTree t);
 12 Position FindMax(SearchTree t);
 13 SearchTree Insert(ElementType x, SearchTree t);
 14 SearchTree Delete(ElementType x, SearchTree t);
 15 
 16 struct TreeNode
 17 {
 18     ElementType element;
 19     SearchTree left;
 20     SearchTree right;
 21 };
 22 
 23 SearchTree MakeEmpty(SearchTree t)
 24 {
 25     if (t != NULL) {
 26         MakeEmpty(t->left);
 27         MakeEmpty(t->right);
 28         free(t);
 29         t = NULL;
 30     }
 31     return NULL;
 32 }
 33 
 34 /* 查找以t为根节点的树中，是否包含x */
 35 Position Find(ElementType x, SearchTree t)
 36 {
 37     if (t == NULL) {
 38         return NULL;
 39     } else if (x < t->element) {
 40         return Find(x, t->left);
 41     } else if (x > t->element) {
 42         return Find(x, t->right);
 43     } else {
 44         return t;
 45     }
 46 }
 47 
 48 Position FindMin(SearchTree t)
 49 {
 50     if (t == NULL) {
 51         return NULL;
 52     } else if (t->left == NULL) {
 53         return t;
 54     } else {
 55         return FindMin(t->left);
 56     }
 57 }
 58 
 59 Position FindMax(SearchTree t)
 60 {
 61     if (t == NULL) {
 62         return NULL;
 63     }
 64 
 65     while (t->right != NULL)
 66     {
 67         t = t->right;
 68     }
 69     return t;  
 70 }
 71 
 72 SearchTree Insert(ElementType x, SearchTree t)
 73 {
 74     if (t == NULL) {
 75         /* 插入第一个节点 */
 76         t = (SearchTree)malloc(sizeof(struct TreeNode));
 77         if (t == NULL) {
 78             return NULL;
 79         }
 80         t->element = x;
 81         t->left = NULL;
 82         t->right = NULL;
 83     } else if (x < t->element) {
 84         t->left = Insert(x, t->left);
 85     } else if (x > t->element) {
 86         t->right = Insert(x, t->right);
 87     }
 88     return t;
 89 }
 90 
 91 /* 删除策略
 92  * 1、如果待删除节点只有一个儿子，则将该节点的父节点的儿子节点指针指向该节点的儿子节点，
 93  * 然后删除该节点.
 94  * 2、如果待删除节点有两个儿子，用右子树中最小的数据代替该节点的数据并递归地删除那个节点。
 95  * 因为右子树中最小地节点不可能有左儿子，所以第二次删除更容易.
 96  */
 97  SearchTree Delete(ElementType x, SearchTree t)
 98  {
 99      Position tmp;
100      if (t == NULL) {  
101          return NULL;
102      }
103      if (x < t->element) {
104          t->left = Delete(x, t->left);
105      } else if (x > t->element) {
106          t->right = Delete(x, t->right);
107      } else if (t->left && t->right) {
108          tmp = FindMin(t->right);
109          t->element = tmp->element;
110          t->right = Delete(t->element, t->right);
111      } else {
112          tmp = t;
113          if (t->left) {
114              t = t->left;
115          } else if (t->right) {
116              t = t->right;
117          }
118          free(tmp);
119          tmp = NULL;
120      }
121      return t;
122  }
123 
124  void PrintfTree(SearchTree t)
125  {
126      if (t == NULL) {
127          return;
128      }
129      printf("%d ", t->element);
130      PrintfTree(t->left);
131      PrintfTree(t->right);
132      return;
133  }
134 
135  int main()
136  {
137      ElementType i;
138      SearchTree binary_tree = NULL;
139 
140      /******** Insert *********/
141      for (i = 1; i < 11; i++) {
142          binary_tree = Insert(i, binary_tree);
143      }
144      PrintfTree(binary_tree);
145      printf("
");
146 
147     /******** Find *********/
148      Position pos = NULL;
149      pos = Find(6, binary_tree);
150      if (pos != NULL) {
151          printf("find %d
", pos->element);
152      } else {
153          printf("Not find 6
");
154      }
155      pos = Find(11, binary_tree);
156      if (pos != NULL) {
157          printf("find %d
", pos->element);
158      } else {
159          printf("Not find 11
");
160      }
161 
162     /******** FindMin *********/
163      Position min = NULL;
164      min = FindMin(binary_tree);
165      if (min) {
166          printf("find min, min: %d
", min->element);
167      } else {
168          printf("not find min
");
169      }
170 
171     /******** FindMax *********/
172      Position max = NULL;
173      max = FindMax(binary_tree);
174      if (max) {
175          printf("find max, max: %d
", max->element);
176      } else {
177          printf("not find max
");
178      }
179 
180 
181     Position del = NULL;
182     del = Delete(8, binary_tree);
183     PrintfTree(binary_tree);
184     printf("
");
185 
186     binary_tree = MakeEmpty(binary_tree);
187     PrintfTree(binary_tree);
188     return 0;
189  }

View Code