二叉搜索树：对于任一节点x，其左子树上的数据值均不大于x.data，右子树上所有数据均不小于x.data。 若对二叉搜索树进行中序遍历输出结点的数值，就能得到从小到大排序的序列。
①查找操作：从树根一路比较往下找就是了，最小值在“最左边”，最大值在“最右边”
1 Position Find( BinTree BST, ElementType X ){ 2 if (!BST||BST->Data==X) return BST; 3 if (BST->Data>X) return Find(BST->Left,X); 4 if (BST->Data<X) return Find(BST->Right,X); 5 } 6 Position FindMin( BinTree BST ){ 7 if (!BST) return NULL; 8 while (BST->Left) BST=BST->Left; 9 return BST; 10 } 11 Position FindMax( BinTree BST ){ 12 if (!BST) return NULL; 13 while (BST->Right) BST=BST->Right; 14 return BST; 15 }
②插入操作：从树根一路向下判断插到左子树还是右子树，走到头就创建一个新结点。
1 BinTree Insert(BinTree BST,ElementType X){ 2 if (!BST){ 3 BST=(BinTree)malloc(sizeof(struct TNode)); 4 BST->Data=X; 5 BST->Left=NULL; 6 BST->Right=NULL; 7 } 8 else{ 9 if (X>BST->Data) BST->Right=Insert(BST->Right,X); 10 else BST->Left=Insert(BST->Left,X); 11 } 12 return BST; 13 }
③删除操作：同样从根节点往下找要删去的结点，找到以后分三种情况：
（i）这个节点是叶子结点——直接删去
（ii）只有左子树或只有右子树——直接删去，把下面的接上来就好，类似链表的删除
（iii）左右子树均不为空——为维持二叉搜索树的性质，把当前结点“替换”成左子树上的最大值（或者右子树上的最小值）
1 BinTree Delete( BinTree BST, ElementType X ){ 2 if (!BST) puts("Not Found"); 3 else if (BST->Data<X) BST->Right=Delete(BST->Right,X); 4 else if (BST->Data>X) BST->Left=Delete(BST->Left,X); 5 else{//当前结点就是要删去的结点 6 if (!BST->Left&&!BST->Right){ 7 BinTree Tmp=BST; 8 free(Tmp); 9 return NULL; 10 } 11 else if (BST->Left&&!BST->Right){ 12 BinTree Tmp=BST->Left; 13 free(BST); 14 return Tmp; 15 } 16 else if (!BST->Left&&BST->Right){ 17 BinTree Tmp=BST->Right; 18 free(BST); 19 return Tmp; 20 } 21 else{ 22 BinTree Tmp=FindMax(BST->Left); 23 BST->Data=Tmp->Data; 24 BST->Left=Delete(BST->Left,Tmp->Data); 25 } 26 } 27 return BST; 28 }
原文：https://www.cnblogs.com/hwh-since2019/p/12780476.html
