数据结构数据结构DataStructuresinC++DataStructuresinC++第第77章章动态集和搜索树动态集和搜索树7
1二叉搜索树7
2二叉平衡树7
1二叉搜索树二叉搜索树7
1二叉搜索树的定义二叉搜索树的定义定义定义7
1设结点由关键字值表征，假定所有结点的关键字值各不相同，二叉搜索树或者是一棵空二叉树，或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的关键字值均小于根结点的关键字值；（2）若右子树不空，则右子树上所有结点的关键字值均大于根结点的关键字值；（3）左、右子树也分别是二叉搜索树
1若以中序遍历一棵二叉搜索树，将得到一个以关键字值递增排列的有序序列
例：对图对图7
1所示所示二叉搜索树，按中序遍历后得到的序列为：23、35、45、54、63、69、76、87二叉搜索树也称二叉排序树二叉搜索树类二叉搜索树类templatetemplateclassBSTree:publicDynamicSetclassBSTree:publicDynamicSet{{public:public:BSTree(){root=NULL;}ResultCodeSearch(T&x)const;ResultCodeInsert(T&x);ResultCodeRemove(T&x);protected:BTNode*root;private:private:ResultCodeSearch(BTNode*p,T&x)const;};};7
2二叉搜索树的搜索•二叉搜索树搜索递归算法templateResultCodeBSTree::Search(T&x)const{returnSearch(root,x);}templateResultCodeBSTree::Search(BTNode
