二叉排序树长度计算方法

A. 二叉排序树的平均查找长度怎样计算

要是哪举粗里看尘档不懂可以评论！正兄镇

B. 二叉树的深度怎么算

1. 一颗树只有一个节点，它的深度是1；

2. 根节点只有左子树而没有右子树，那么二叉树的深度应该是其左子树的深度加1；

3. 根节点只有右子树而没有左子树，那么二叉树的深度应该是其右树的深度加1；

4. 根节点既有左子树又有右子树，那么二叉树的深度应该是其左右子树的深度较大值加1

C. 二叉树的深度算法怎么算啊

二叉树的深度算法：
一、递归实现基本思想：
为了求得树的深度，可以先求左右子树的深度，取二者较大者加1即是树的深度，递归返回的条件是若节点为空，返回0
算法：
1
int
FindTreeDeep(BinTree
BT){
2
int
deep=0;
3
if(BT){
4
int
lchilddeep=FindTreeDeep(BT->lchild);
5
int
rchilddeep=FindTreeDeep(BT->rchild);
6
deep=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1;
7
}
8
return
deep;
9
}
二、非递归实现基本思想：
受后续遍历二叉树思想的启发，想到可以利用后续遍历的方法来求二叉树的深度，在每一次输出的地方替换成算栈S的大小，遍历结束后最大的栈S长度即是栈的深度。
算法的执行步骤如下：
（1）当树非空时，将指针p指向根节点，p为当前节点指针。
（2）将p压入栈S中，0压入栈tag中，并令p执行其左孩子。
（3）重复步骤（2），直到p为空。
（4）如果tag栈中的栈顶元素为1，跳至步骤（6）。从右子树返回
（5）如果tag栈中的栈顶元素为0，跳至步骤（7）。从左子树返回
（6）比较treedeep与栈的深度，取较大的赋给treedeep，对栈S和栈tag出栈操作，p指向NULL，并跳至步骤（8）。
（7）将p指向栈S栈顶元素的右孩子，弹出栈tag，并把1压入栈tag。（另外一种方法，直接修改栈tag栈顶的值为1也可以）
（8）循环（2）~（7），直到栈为空并且p为空
（9）返回treedeep，结束遍历
1
int
TreeDeep(BinTree
BT
){
2
int
treedeep=0;
3
stack
S;
4
stack
tag;
5
BinTree
p=BT;
6
while(p!=NULL||!isEmpty(S)){
7
while(p!=NULL){
8
push(S,p);
9
push(tag,0);
10
p=p->lchild;
11
}
12
if(Top(tag)==1){
13
deeptree=deeptree>S.length?deeptree:S.length;
14
pop(S);
15
pop(tag);
16
p=NULL;
17
}else{
18
p=Top(S);
19
p=p->rchild;
20
pop(tag);
21
push(tag,1);
22
}
23
}
24
return
deeptree;
25
}

D. 二叉树路径长度问题

因为肢雀裂每个节点都只有一个父岁芹节点，所以二叉树的路径是唯一的，历闭那么计算的时候最简单的方法就是数“桥”的个数，也就是一个路径上所有节点个数减1，”桥“指连接两个相邻节点的线。

E. 如何用C语言或C++语言实现二叉排序树的平均查找长度的计算

main()
{
int x,y,z,t;
scanf("%d%d%d",&x,&y,&z);
if (x>y)
{t=x;x=y;y=t;} /*交换x,y的值*/
if(x>z)
{t=z;z=x;x=t;}/*交换x,z的蔽大困值*/
if(y>z)
{t=y;y=z;z=t;}/*交换z,y的值*/
printf("宏念仿皮small to big: %d %d %d\n",x,y,z);
}

F. 分块查找平均查找长度计算公式是什么顺序查找和折半

顺喊族序查找：O(n)
折半查找：O(log2n)
分块查找：大致 O(n^0.5)
二叉排序树：介于O(log2n)和O(n)之间
平衡二叉树：O(log2n)
m阶B-树：O(logmn)
散列或者音译哈希平均查找长度与结点锋蔽个数无关的查找方法，ASL的理论值只与装填因子银渗州有关

G. 最差适配的平均查找长度

n个节点的二叉排序树在最坏的情况下的平均查找长度为（n+1）/2。

二叉排序树每个嫌芹陪结点的C（i）为该结点的层次数。最坏情况下，当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树，树的深度为芹蠢其平均查找长度（n+1）/2（和顺序查找相同），最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log 2 （n）成正比。

计算方法

最差适应算法（Worst Fit）为首改适应此算法，空闲分区表（空闲区链）中的空闲分区要按大小从大到小进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留小的空闲区，尽量减少小的碎片产生。

最差适应算法，也称最差适配算法，它从全部空闲区中找出能满足作业要求的、且大小最大的空闲分区，从而使链表中的结点大小趋于均匀，适用于请求分配的内存大小范围较窄的系统。

H. 二叉搜索树的平均查找长度及时间复杂度

推导过程如下:

假设有一颗二叉排序树, 总结点数没姿是n, 高度是h, 根结点的高度是1,
假设也是满二叉树, n与h的关系, 有公式: n = (2^h) - 1
也就是: h = log2(n+1)

对于高度为2,总结点数是3的二叉排序树(满二叉树),查找成功的平均查找长度为:

对于高度为3,总结点数是7的二叉排序树(满二叉树),查找成功的平均查找长度为:

对于高度为h,总结点数是n的二叉排序树(满二叉树),查找成功的平均查找长度为:

对于[等式1]里的1*1 + 2*2 + 3*4 + ... + h*2^(h-1)
该数列有h项: 1*2^0, 2*2^1, 3*2^2, ... , h*2^(h-1)
其总和:

等式两边同乘以2,有:

用[等式3]减去[等式2]有:

其中(2^0 + 2^1 + 2^2 + 2^3 + ... + 2^(h-1))是等比数列求和,设:

等式两边同乘以2,有: 2*M = (2^1 + 2^2 + 2^3 + ... + 2^h)
两个等式相减,有: M = 2^h - 1
将M代入[等式4]有:

因为 h = log2(n+1),将h代入[等式5],有:

也就是

将上述S代入[等式1],有:

所以,二叉排序树查找成功的平均查找长度为:

其时间复杂度是: O(log2(n))

假设有一颗平衡的二叉排序树,高度h=4,总结点数n=11,不是满二叉树:

根据[公式1],查找成功的平均查找长度为:
ASL = [(n+1)/n] * log2(n+1) - 1 = [(11+1)/11] * log2(11+1) - 1 约等于 2.91

逐个伏灶结点计数,平均查找长度为:
ASL = (1*1 + 2*2 + 3*4 + 4*4) / 11 = 33 / 11 = 3

假设有一颗平衡的二叉排序树,高度h=4,总结点数n=15,是满二叉树:

根据[公式1],查找成缺察扮功的平均查找长度为:
ASL = [(n+1)/n] * log2(n+1) - 1 = [(15+1)/15] * log2(15+1) - 1 = 49/15

逐个结点计数,平均查找长度为:
ASL = (1*1 + 2*2 + 3*4 + 4*8) / 15 = 49/15

I. 数据结构中二叉排序树的平均查找长度

先构造二叉排序树,然后计算就行了:
（2×3+2×2+2）/7=1.7

J. 二叉排序树的不成功的平均查找长度怎么求

查找不成功就是从查找位置开始直到一个位置为空需要比较的次数。

比如：

62

/

30 74

/

15 56

/

48

找到所有的外结点，也就是查找失败的点，然后计算ASL

就你的BST，结果败老如下：

15的左右子树都为空，也就是左右子树都是外结点，失败时需要比较62、30、15一共3次

48的左右子树都为空，也就是左右子树都是外结点，失败时需要比较62、30、15、48一共4次

56的右昌枯棚子树为空，也就是右子树是外结点，失败时需要比较62、30、56一共3次

74的左右子树都为空，也就是左右子树都是外结点，失败时需要比较62、74一共2次

因此外结点总数为2 *3 + 1 = 7 （其实这个数量一定是关键字个数加1）

所以ASL = (2 * 3 + 2 * 4 + 1 * 3 + 2 * 2) / 7 = 21 / 7 = 3。

(10)二叉排序树长度计算方法扩展阅读：

查找步骤：

二叉树

若根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，递归查左子树。若大于根结点的关键字值，递归查右子树。若子树为空，查找不成功。

平均情况分析（在成功查找两种的情况下）：

在一般情况下，设 P（n，i）为它的左子树的结点个数为 i 时的平均查找长度。如图的结点个数为 n = 6 且 i = 3; 则 P（n,i）= P（6, 3） = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6

注意：这里 P(3)、P(2) 是具有 3 个结点、2 个结点的二叉分类树的平均查找长度。 在一般情况，P（i）为具有 i 个结点二叉分类树的平均查找长度。平均查找长度= 每个结点的深度的总和 / 总结点数

参考耐则资料来源：网络-二叉排序树