二叉搜索树（BST树)
什么是二叉搜索树
二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树
二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质：
- 非空左子树的所有键值小于其根结点的键值。
- 非空右子树的所有键值大于其根结点的键值。
- 左、右子树都是二叉搜索树。
举个栗子：
二叉搜索树：
非二叉搜索树：
二叉搜索树的特别函数
Find函数
从二叉搜索树BST中查找元素X，返回其所在结点的地址
实现逻辑：
⏩从根节点开始，树为空，返回NULL
⏩若树不为空，将根节点和传入的数据X进行比较：
- 若X小于根节点的键值，进入左子树继续搜索
- 若X大于根节点的键值，进入右子树继续搜索
- 若两者比较结果相等，搜索完成，返回此结点的指针
常言道：一图值前言
所需结构体
//为了简化后文重复代码的书写，用typedef对指向树结构的指针取两个别名位置类型的"Position"和搜索二叉树类型的"SearchTree" typedef struct TreeNode *Position; typedef struct TreeNode *SearchTree; struct TreeNode{ ElementType Element; SearchTree Left; SearchTree Right; };
具体实现的参考代码
Position Find(ElementType X, SearchTree T) { if(T == NULL) return NULL; if(X < T->Element) return Find(X,T->Left);//带着X进入左子树 if(X > T->Element) return Find(X,T->Right);//带着X进入右子树 else return T;//搜索成功 }
Find函数的性质挖掘
从二叉搜索树的特性来看，它的左子树总是比根节点的键值小，所以最小值只能出现在左子树，一个结点它下面没有比它小的左子树了，那它就是最小的了。最大值同理，右子树总是比根节点的键值大，一个结点它下面没有比它大的右子树了，那它就是最大的了。
FindMin函数
从二叉搜索树BST中查找并返回最小元素所在结点的地址。
具体实现的参考代码
Position FindMin(SearchTree T) { if(T == NULL) return NULL; else { if(T->Left == NULL) return T;//搜索成功，没有比它小的了 else return FindMin(T->Left);//继续到左子树的左子树中查找 } }
FindMax函数
从二叉搜索树BST中查找并返回最大元素所在结点的地址。
具体实现的参考代码
上述两份代码都是使用的递归的方式实现的。这里变一下~。用函数迭代法
//函数迭代法 Position FindMax(SearchTree T) { if(T == NULL) return NULL; while(T->Right) return T->Right; return T; }
闲谈一刻
递归常常被称为—— “一种优雅的解决问题的方式”。对于它的态度，分为了三种阵营，恨之入骨，爱不释手，恨了又爱
因为递归写代码可以让方案更整洁喔。比如在dfs中，只用写好当前这一步的逻辑，下一步则递归进去，实现和当前这步一样的操作就好。但是递归在性能上是不及循环的喔~！
每个递归函数都有两部分，基线条件和递归条件。递归条件是指函数自己调用自己，而基线条件(⊙o⊙)…，则是指函数不再自己调用自己了，可以获得其他值回溯回去了，从而避免形成无限循环。典型例子：斐波那契数列
Insert函数
因为二叉搜索树独特的性质，导致了插入一个数据以后，仍然要保证左子树比根节点小，右子树比根节点大。所以对于插入而言，最主要的确认插入的位置
具体实现的参考代码
SearchTree Insert(ElementType X,SearchTree T) { //如果树为空，生成并返回一个有一个结点的二叉搜索树 if(T ==NULL) { T = malloc(sizeof(struct TreeNode)); T->Element = X; T->Left = T->Right = NULL; }else { if(X < T->Element) T->Left = Insert(X,T->Left);//如果比根节点小，就向左子树的方向进行插入 else if(X > T->Element) T->Right = Insert(X,T->Right);//如果比根节点大，就向右子树的方向进行插入 } return T; }
Delete函数(难点)
情况一
要删除的是叶结点：直接删除，并再修改其父结点指针—置为NULL
情况二
要删除的结点只有一个孩子结点: 将其父结点的指针指向要删除结点的孩子结点
情况三
要删除的结点有左、右两棵子树： 用另一结点替代被删除结点：用 右子树的最小元素 或者 左子树的最大元素
具体实现的参考代码
SearchTree Delete(ElementType X, SearchTree T) { Position TmpCell; //找到要删除的位置在哪里 if(T == NULL) printf("Element not found\n"); else if(X < T->Element) T->Left = Delete(X,T->Left); else if(X > T->Element) T->Right = Delete(X,T->Right) ; //具体的开始执行删除操作了 //两个儿子都存在的情况 else if(T->Left && T->Right) //两个孩子 { TmpCell = FindMin(T->Right) ;//找到右子树的最小值或者左子树的最大值来代替那个要被删除的节点 T->Element = TmpCell->Element; //删除右边那个被抽上去替代的节点 T->Right = Delete(T->Element,T->Right); }else //一个或者没有孩子 { TmpCell = T; if(T->Left == NULL) T = T->Right;//结合上图，只有一个孩子的时候，是让这孩子挪到要删除结点的位置，也就实现了 将其父结点的指针指向要删除结点的孩子结点 } else if(T->Right == NULL) T = T->Left; free(TmpCell); } return T; }
