二叉排序树的建立_怎么建立二叉排序树_二叉排序树的创建(24)

索引顺序表

分块，块间有序 + 块内无序，对应索引表有序 + 顺序表（无序）。

索引顺序表的查找性能介于顺序查找与折半查找之间。

分块的最佳长度是多少？规定条件：每块的大小相同，对块索引表和块内查找均采用顺序查找。

设表长为n，等分成b块，采用顺序查找确定块需要比较(b+1)/2次，块内顺序查找比较(n/b+1)/2次，总共C(b)=(b+1)/2+(n/b+1)/2，要使C(b)最小，有b?。

二叉排序树

二叉排序树

二叉排序树或为空树；或者是这样一棵二叉树，若左子树不空，则左子树上所有结点均小于根结点，若右子树不空，则右子树上所有结点均大于根结点，其左、右子树也是二叉排序树。 技巧：如果中序遍历二叉排序树，得到的结果将从小到大有序。手工判别二叉排序树的方法之一。

例：判断对错：二叉排序树或是空树，或是这样一棵二叉树，若左子树不空，则左孩子小于根结点，若右子树不空，则右孩子大于根结点，左、右子树也是这样的二叉排序树。（×）请自己举反例。

查找

思路：①若二叉树为空，则找不到，②先与根比较，相等则找到，否则若小于根则在左子树上继续查找，否则在右子树上继续查找。

递归算法：

BstTree BstSearch ( BstTree bst, DataType x )

{

if ( bst==NULL )

return NULL;

else if ( bst->data==x )

return bt;

else if ( x<bst->data )

return BstSearch ( bst->lchild, x);

else

return BstSearch ( bst->rchild, x);

}

非递归算法:

BstTree BstSearch ( BstTree bst, DataType x )

{

p = bst;

while ( p ) {

if ( p->data==x )

return p;

else if ( x<p->data )

p = p->lchild;

else

p = p->rchild;

}

return NULL; // not found

}

插入

思路：先查找，若找不到则插入结点作为最后访问的叶子结点的孩子。

新插入的结点总是叶子。

建立

经过一系列插入操作可以建立二叉排序树。

给定关键字序列，建立二叉排序树。方法：①开始二叉树为空，②对每一个关键字，先进行查找，如果已存在，则不作任何处理，否则插入。

22一句话，“从空树开始，每次插入一个关键字”。

例：给定关键字序列{53，45，12，24，90，45，80}，建立二叉排序树。 22 不准确的说法，只为便于理解和记忆，不要在正式场合引用。

删除

叶子

直接删除即可。

删除左子树或右子树为空

“移花接木”：将左子树或右子树接到双亲上。

删除左右子树都不空 “偷梁换柱”：借左子树上最大的结点替换被删除的结点，然后删除左子树最大结点。（或者借用右子树上最小结点然后删除之亦可。）

删除分析

判定树和二叉排序树相同。结点的层次等于查找时比较关键字的个数。

等概率情况下查找成功时

1n1?2?2?3?3?4ASL??h

i??2.5

i?1

若按照关键字有序的顺序插入结点建立二叉排序树，将得到一棵单支树，对其进行查找也退

化为顺序查找，平均查找长度为(1+n)/2。一般地，如果在任一关键字k之后插入二叉排序树的关键字都大于或都小于k，则该二叉排序树是单分支的，深度是n，查找效率和顺序查找相同。 平衡二叉树

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25557-24.html