一、什么是二叉搜索树查找问题:
静态查找与动态查找
针对动态查找，数据如何组织？
二叉搜索树：
非空左子树的所有值小于根结点的值；
非空右子树的所有值大于根结点的键值；
左、右子树都是二叉搜索树；
PositionFind(ElementTypeX,BinTreeBST);/*从二叉搜索树BST中查找元素X，返回其所在结点的地址。*/PositionFindMin(BinTreeBST);/*从二叉搜索树BST中查找并返回最小元素所在结点的地址；*/PositionFindMax(BinTreeBST);/*从二叉搜索树BST中查找并返回最大元素所在结点的地址。*/BinTreeInsert(ElementTypeX,BinTreeBST);BinTreeDelete(ElementTypeX,BinTreeBST);
二、二叉搜索树的查找操作：Find
查找从根结点开始，如果树为空，返回NULL
若搜索树非空，则根结点关键字和X进行比较，并进行不同处理：
若X小于根结点键值，只需在左子树中继续搜索；
如果X大于根结点的键值，在右子树中进行继续搜索；
若两者比较结果是相等，搜索完成，返回指向此结点的指针
//递归查找PositionFind(ElementTypeX,BinTreeBST){if(!BST)returnNULL;/*查找失败*/if(XBST-Data)returnFind(X,BST-Right);/*在右子树中继续查找*/elseif(XBST-Data)returnFind(X,BST-Left);/*在左子树中继续查找*/else/*X==BST-Data*/returnBST;/*查找成功，返回结点的找到结点的地址*/}//循环查找PositionIterFind(ElementTypeX,BinTreeBST){while(BST){if(XBST-Data)BST=BST-Right;/*向右子树中移动，继续查找*/elseif(XBST-Data)BST=BST-Left;/*向左子树中移动，继续查找*/else/*X==BST-Data*/returnBST;/*查找成功，返回结点的找到结点的地址*/}returnNULL;/*查找失败*/}
三、查找最大和最小元素
最大元素一定是在树的最右分枝的端结点上
最小元素一定是在树的最左分枝的端结点上
PositionFindMin(BinTreeBST){if(!BST)returnNULL;//空的二叉搜索树，返回NULLelseif(!BST-Left)returnBST;//找到最左叶结点并返回elsereturnFindMin(BST-Left);//沿左分支继续查找}PositionFindMax(BinTreeBST){if(BST)while(BST-Right)BST=BST-Right;//沿右分支继续查找，直到最右叶结点returnBST;}
四、二叉搜索树的插入关键是要找到元素应该插入的位置，可以采用与Find类似的方法
BinTreeInsert(ElementTypeX,BinTreeBST){if(!BST){BST=malloc(sizeof(structTreeNode));//若原树为空，生成并返回一个结点的二叉搜索树BST-Data=X;BST-Left=BST-Right=NULL;}else{/*开始找要插入元素的位置*/if(XBST-Data)BST-Left=Insert(X,BST-Left);/*递归插入左子树*/elseif(XBST-Data)BST-Right=Insert(X,BST-Right);/*递归插入右子树*/}returnBST;}
五、二叉搜索树的删除考虑三种情况：
要删除的是叶结点：
直接删除，并再修改其父结点指针---置为NULL
要删除的结点只有一个孩子结点:
将其父结点的指针指向要删除结点的孩子结点
要删除的结点有左、右两棵子树：
用另一结点替代被删除结点：右子树的最小元素或者左子树的最大元素
BinTreeDelete(ElementTypeX,BinTreeBST){PositionTmp;if(!BST)printf("要删除的元素未找到");else{if(XBST-Data)BST-Left=Delete(X,BST-Left);/*左子树递归删除*/else{if(XBST-Data)BST-Right=Delete(X,BST-Right);/*右子树递归删除*/else{/*找到要删除的结点*/if(BST-LeftBST-Right){/*被删除结点有左右两个子结点*/Tmp=FindMin(BST-Right);//在右子树中找最小的元素填充删除结点*/BST-Data=Tmp-Data;BST-Right=Delete(BST-Data,BST-Right);//在删除结点的右子树中删除最小元素*/}else{/*被删除结点有一个或无子结点*/Tmp=BST;if(!BST-Left)/*有右孩子或无子结点*/BST=BST-Right;elseif(!BST-Right)/*有左孩子或无子结点*/BST=BST-Left;free(Tmp);}}}}returnBST;}预览时标签不可点收录于话题#个上一篇下一篇