(21)--第6章 查找-二叉排序树数据结构.ppt
第7章 查找二叉排序树树表的查找二叉排序树平衡二叉树 B_树 B+树 1.二叉排序树的定义2.二叉排序树查找操作3.二叉排序树插入操作4.二叉排序树删除操作5.二叉排序树性能分析二叉排序树的定义二叉排序树或是空树，或是满足如下性质的二叉树：(1)若其左子树非空，则左子树上所有结点的值均小于根结点的值；(2)若其右子树非空，则右子树上所有结点的值均大于等于根结点的值；(3)其左右子树本身又各是一棵二叉排序树二叉排序树的定义判断二叉树是否为二叉排序树判断二叉树是否为二叉排序树练习中序遍历二叉排序树后的结果有什么规律中序遍历二叉排序树后的结果有什么规律？练习451253337241006190783，12，24，37，45，53，61，78，90，100递增得到一个关键字的递增有序序列思考二叉排序树判定思路？根据中序遍历是否有序进行判定若查找的关键字等于根结点，成功否则若小于根结点，查其左子树若大于根结点，查其右子树在左右子树上的操作类似12225030011020099105230216二叉排序树操作-查找、105查找122(1)若二叉排序树为空，则查找失败，返回空指针。(2)若二叉排序树非空，将给定值key与根结点的关键字T-data.key进行比较：若key等于T-data.key，则查找成功，返回根结点地址；若key小于T-data.key，则进一步查找左子树；若key大于T-data.key，则进一步查找右子树。查找算法思路BSTree SearchBST(BSTree T,KeyType key)if(!T)|key=T-data.key)return T;else if(keydata.key)return SearchBST(T-lchild,key);/在左子树中继续查找 else return SearchBST(T-rchild,key);/在右子树中继续查找/SearchBST二叉排序树查找算法描述对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（）。95,22,91,24,94,7192,20,91,34,88,3521,89,77,29,36,3812,25,71,68,33,34ABCD提交单选题2分插入的元素一定是叶结点若二叉排序树为空，则插入结点应为根结点否则，继续在其左、右子树上查找树中已有，不再插入树中没有，查找直至某个结点的左子树或右子树为空为止，则插入结点应为该结点的左孩子或右孩子二叉排序树的操作-插入4512533372410061907820插入结点20二叉排序树的操作-插入 10，18，3，8，12，2，710101810183101838101838 12101838 122101838 1227从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树练习将 32,2,15,65,28,10 依次插入初始为空的二叉排序树,并求等概率下查找成功时平均查找长度。作答正常使用主观题需2.0以上版本雨课堂主观题8分可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本二叉排序树的构造6分，查找长度2分。ASLsucc=8/3答案解析二叉排序树的操作-删除（1）被删除的结点是叶子；（2）被删除的结点只有左子树或者只有右子树；（3）被删除的结点既有左子树，也有右子树。可分三种情况讨论：50308020908540358832(1)被删除的结点是叶子结点被删关键字=2088其双亲结点中相应指针域的值改为“空”50308020908540358832(2)被删除的结点只有左子树或者只有右子树其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。被删关键字=408050308020908540358832(3)被删除的结点既有左子树，也有右子树4040以其前驱替代之，然后再删除该前驱结点被删关键字=50在二叉排序树上删除一个结点，然后再插入，则树形与未删除前的树形一样。正确错误AB提交单选题1分在二叉排序树上删除一个叶子结点，然后再插入，则树形与未删除前的树形一样。正确错误AB提交单选题1分已知二叉排序树如图所示，并分别给出依次执行下列操作后的二叉排序树（共画三棵树）（1）插入数据42和80；（2）删除数据30；（3）删除数据50。作答正常使用主观题需2.0以上版本雨课堂主观题10分不同插入次序的序列生成不同形态的二叉排序树不同插入次序的序列生成不同形态的二叉排序树4024551237122437405540，24，12，37，5512，24，37，40，55思考第i层结点需比较i次。在等概率的前提下，上述两图的平均查找长度为：40245512371224374055二叉排序树的性能分析由同一关键字集合构造的各棵二叉搜索树（）其形态均相同，但平均查找长度不一定相同其形态均相同，平均查找长度也都相同其形态不一定相同，但平均查找长度相同其形态不一定相同，平均查找长度也不一定相同ABCD提交单选题2分二叉排序树树形与初始序列有关平均查找长度和二叉树的树形有关，即，最好：log2n（形态匀称，与二分查找的判定树相似）最坏:（n+1)/2（单支树）结论总结1.熟练掌握二叉排序树的定义2.熟练掌握二叉排序树的查找，插入（构造）3.中序遍历是递增有序序列4.树形与初序有关
