首页 > 代码库 > 二叉搜索树
二叉搜索树
二叉搜索树：
动态查找
a.非空左子树的所有值小于其根接点值
b.非空右子树的所有值大于其根接点值
c.左、右子树均为二叉搜索树
Position Find( ElementType X, BinTree BST ):
从二叉搜索树BST中查找元素X,返回其所在结点的地址
Position FindMin( BinTree BST ):
从二叉搜索树BST中查找并返回 最小元素所在结点的地址
Position FindMax( BinTree BST ) :
从二叉搜索树BST中查找并返回 最大元素所在结点的地址
BinTree Insert( ElementType X, BinTree BST )
BinTree Delete( ElementType X, BinTree BST )
查找操作：
始于根结点，若树为空，返回NULL
非空，则与关键字X比较：
a. X小于根节点值，只需再左子树继续搜索
b. X大，则在右子树中搜索
c. 相等，返回此结点指针
递归解决
Position Find(ElementType X, BinTree BST){ if (!BST) return NULL;//若树为空则返回NULL if (X > BST->Data) return Find(X,BST->Right); else if(X < BST->Data) return Find(X,BST->Left); else //X = BST->Data return BST;}
迭代解决
Position IterFind( ElementType X, BinTree BST){ while(BST){ if (X > BST->Data) BST = BST->Right; else if (X < BST->Data) BST = BST->Left; else return BST; } return NULL;}
查找的效率决定于树的高度
寻最大和最小元素
最大 → 最右分支的最右端结点
最小 → 最左分支的最左端结点
Position FindMin( BinTree BST){ if (!BST) return NULL; else if (!BST->Left) return BST; else return FindMin(BST->Left);}
亦可以用迭代来解决
Position FindMax( BinTree BST)
Position FindMax( BinTree BST){ if(!BST) while (BST->Right) BST = BST->Right; return NULL;}
二叉搜索树的插入
插入、搜索、删除，我觉得这几个地方的递归是属于难点
BinTree Insert (ElementType X, BinTree BST){ if ( !BST ){ BST = malloc(sizeof(struct TreeNode)); BST->Data = http://www.mamicode.com/X;>
这种算法是不能插入重复数据的...可以看到..
然后return 的BST是根的指针
同样可以想，是一个一个Stack叠加...每一个Stack有其自己的BST
最终return的BST就是根的指针
已写代码验证
二叉搜索树的删除
a. 叶结点 → 直接删除，修改其父接点指针为NULL
b. 只有一个孩子 → 修改其父结点的指针指向要删除结点的孩子结点
c. 有左、右两颗子树 → 用另一结点替代被删除结点:右子树的最小元素 或者 左子树的最大元素
取右子树中的最小元素必定位于最左边端点，有的话也只会有一个儿子，右边儿子
然后因为右边的都是大于根接点的结点，所以最小的用来替换好也刚好就是搜索二叉树
而左子树的最大元素也同理，只会有一个儿子
这样就简化为 ： 把结点替换掉之后再删除拿来替换的结点
替换的结点只有一个儿子/没有儿子，就简化为之前的a或者b状况
BinTree Delete(ElementType X, BinTree BST){ Position Tmp; if (!BST) printf("\nNode does not exist"); else if ( X < BST->Data) BST->Left = Delete(X,BST->Left); else if (X > BST->Right) BST->Right = Delete(X,BST->Right); else if ( BST->Right && BST->Left){ Tmp = FindMin(BST->Right); BST->Data = http://www.mamicode.com/Tmp->Data;>
这样一步步的return实际上是将要删除的节点啥再挂回原树
二叉搜索树