【数据结构】18 二叉搜索树（查找，插入，删除）

定义

二叉搜索树也叫二叉排序树或者二叉查找树。它是一种对排序和查找都很有用的特殊二叉树。
一个二叉搜索树可以为空，如果它不为空，它将满足以下性质：

1. 非空左子树的所有键值小于其根节点的键值
2. 非空右子树的所有键值都大于其根结点的键值
3. 左、右子树都是二叉树

动态查找

查找操作Find

在二叉搜索树中查找关键字为X的结点，返回其所在结点的地址。查找过程如下：

1. 查找从树的根节点开始，若树为空，返回NULL
2. 搜索树非空，则根节点关键字和X比较，依据结果，需要进行不同的处理
   若根节点键值小于X，在根节点右子树中查找
   若根节点的键值大于X，在根节点的左子树中查找
   若两者比较结果相等，搜索完成。

递归代码

Position Find_RE(BinTree BT, ElementType X) {if (!BT) {return NULL;}if (X > BT->Data) {return Find_RE(BT->Right, X);}else if(X < BT->Data){return Find_RE(BT->Left, X);}else{return BT;}
}

迭代函数

Position Find_D(BinTree BT, ElementType X) {BinTree T = BT;while (T) {if (T->Data > X) {T = T->Left;}else if (T->Data < X) {T = T->Right;}else{return T;}}
}

查找最大和最小元素

根据二叉搜索树的性质，最大元素一定在最右分支的尾端，最小元素一定在最左分支的尾端。
递归函数

Position FindMin(BinTree BT) {if (!BT) {return NULL;}else if(!BT->Left){return BT;}else{return FindMin(BT->Left);}
}

迭代函数

Position FindMinD(BinTree BT) {BinTree T = BT;while (T->Left) {T = T->Left;}return T;
}

找最大值只需要把left换成right

插入

BinTree Insert(BinTree BT, ElementType X) {if (!BT) {BT = (BinTree)malloc(sizeof(struct TNode));BT->Data = X;BT->Left = BT->Right = NULL;}else {if (X > BT->Data) {BT->Right =  Insert(BT->Right, X);}else if (X < BT->Data) {BT->Left =  Insert(BT->Left, X);}}return BT;
}

删除

二叉搜索树的删除比较复杂，需要考虑节点的位置

1. 叶结点
   可以直接删除，将其父节点指针置空即可。
2. 只有一个孩子结点
   要修改其父节点的指针，指向要删除结点的孩子结点。
3. 有左、右两颗树
   究竟用哪颗子树的根结点来填充删除节点的位置？有两种选择方式：选择左子树的最大元素，或者选择右子树的最小元素。无论哪种方式，最后被选择的结点必定最多只有一个孩子。
   

采用右子树的最小元素的删除代替策略。
代码思路： 先找到要删除元素的位置，若其具有左右子树，找到该位置的右子树里面的最小元素，赋值到该位置上，在其右子树中删除最小元素（递归调用），若只有一个子树或者没有，易操作。

BinTree DeleteBT(BinTree BT, ElementType X) {Position p;if (!BT) {printf("can't find the node\n");}else {if (X > BT->Data) {BT->Right = DeleteBT(BT->Right, X);}else if (X < BT->Data) {BT->Left = DeleteBT(BT->Left, X);}else {if (BT->Left && BT->Right) {//FIND THE Min OF Right TREEp = FindMin(BT->Right);BT->Data = p->Data;BT->Right = DeleteBT(BT->Right, p->Data);}else {p = BT;if (!BT->Left) {BT = BT->Right;}else { BT = BT->Left; }free(p);}}}return BT;
}