【数据结构英文课件】BINARYTREES.pptVIP

Corollary 10.2 In the average case, on a randomly ordered list of length n, treesort performs comparisons of keys. First advantage of treesort over quicksort: The nodes need not all be available at the start of the process, but are built into the tree one by one as they become available. ?Second advantage: The search tree remains available for later insertions and removals. ?Drawback: If the keys are already sorted, then treesort will be a disaster-- the search tree it builds will reduce to a chain. Treesort should never be used if the keys are already sorted,or are nearly so. 5.Removal from a Binary Search Tree pg.455 从二叉查找(有哪些信誉好的足球投注网站/排序)树中删除一个结点，不能把以该结点为根的子树都删除，只能删掉该结点，并且还应该保证删除后得到的二叉树仍然满足二叉查找树的性质，即在二叉查找树中删除一个结点相当于删去有序序列中的一个结点。那么，如何在二叉查找树上删去一个结点呢? 如上页图所示：当被删结点是叶子或仅有一棵子树时，情况较简单，只是修改其双亲结点的指针就可以了；若被删结点既有左子树也有右子树时，应当如何处理呢？假设在二叉查找树上被删结点为P(指向结点的指针为p)，其双亲结点为F(结点指针为f)，且不失一般性，可设p是f的左指针，即被删结点P是F的左孩子。一种处理方法如下页图所示：以被删结点的左子树中最大结点S(必然是叶子)的数据代替被删结点P的数据，然后删除叶子S。 Auxiliary Function to Remove One Node: template class RecordError_code Search_treeRecord:: remove_root(Binary_nodeRecord* sub_root) { if(sub_root==NULL) return not_present; Binary_nodeRecord *to_delete=sub_root-left; if(sub_root-right==NULL) sub_root=sub_root-left; else if(sub_root-left==NULL) sub_root=sub_root-right; else // else(2) { to_delete=sub_root-left; Binary_nodeRecord *parent=sub_root; while(to_delete-right!=NULL) { parent=to_delete; to_delete=to_delete-right; } sub_root-data=to_delete-data; 注意：sub_root 一定是引用参数 sub_root只有左 子树,以左孩子做为 删除后子树的新根 sub_root只有右 子树,以右孩子做为 删除后子树的新根 sub_root既有左 子树,也有右子树. 搜寻它的左子树 中最大结点 令to_delete移动到 sub_root的左孩子 指针parent 保持跟踪to_delete 是它的双亲结点 在sub_root所指 结点的左子树中 搜寻最大结点 (此结点是它的前驱) 脱离循环to_delete 指向找到的结点 将to_delete所指结点 的数据域转移到 sub_root所指结点 If sub_root is NULL a code of not_present is returned. Otherwise, the root of