数据结构习题课-二元树.ppt

文档介绍：数据结构习题课-2
一棵二元树的先序、中序和后序序列分别如下,其中一部分未显示出来,试求出空格处的内容,并画出该二元树。
先序:_B_F_ICEH_G
中序:D_KFIA_EJC_
后序:_K_FBHJ_G_A
先序:ABDFKICEHJG
中序:DBKFIAHEJCG
后序:DKIFBHJEGCA
A
B
C
D
E
F
G
H
I
J
K
二元树中序序列为:ABCEFGHD,后序序列为:ABFHGEDC
画出此二元树
假设先根次序遍历某棵树的结点次序为SACEFBDGHIJK,
后根次序遍历该树的结点次序为CFEABHGIKJDS,请画出
这棵树。
A
B
C
D
E
F
G
H
E
S
C
I
J
G
B
D
A
H
K
F
完全二元树的某结点若无左孩子结点,则它必是叶结点?
前序遍历和中序遍历相同的二元树?
前序遍历和后序遍历相同的二元树?
中序遍历和后序遍历相同的二元树?
试举出:
一棵有124个叶子结点的完全二元树,最多有? 个结点。
n0=n2+1
n=n0+n1+n2
n=n1+2n0-1
但在完全二元树中,n1不是 0 就是 1
只有n1=1时,n 取最大值为2n0
题:设n0为哈夫曼树的叶子结点数目,
简要推出该哈夫曼树有多少个结点?
总结点数n=n0+n1+n2
而根据二元树性质有:n0=n2+1
又因哈夫曼树的n1=0
所以: n=n0+n2 = 2n0-1
证明题:
任意一棵有n个结点二元树,已知它有m个叶子结点,
试证明非叶子结点有(m-1)个度为2,其余度为1。
证明:
设n1为二元树中度为1的结点数,n2为度为2的结点数,
则总结点数n=n1+n2+m
又设分支数B,有n=B入+1
而 B出=n1+2n2
由B入=B出,所以有:
n=n1+2n2+1
n1+n2+m=n1+2n2+1
所以: n2=m-1
证明任一棵满二元树T中的分支数B满足:
B=2(n0-1) ,其中 n0为叶子结点数
证明:
满二元树中不存在度为1的节点,设度为2的结点数为n2
则: n=n0+n2
又: n=B+1
所以有: B=n0+n2-1 , 而 n0=n2+1, n2=n0-1
B=n0+n0-1-1=2(n0-1)
具有n个结点的满二元树,其叶子结点的个数为多少?
C 语言程序设计
C 语言程序设计
具有n个结点的完全二元树,其叶子结点的个数为多少?
方法一:设满二元树的高度为h,
则根据二元树的性质,叶子结点数为2h-1
二元树总结点数n=2h-1
可导出:2h-1=(n+1)/2
方法二:结点总数:n=n0+n1+n2
但对满二元树,除有n0=n2+1外,还有n1=0
故有: n=n0+n0-1
n0=(n+1)/2
设高为h的二元树只有度为0和度为2的结点,则此类二元树
的结点树至少为,至多为。
答案: 2h-1 和 2h-1
给定一棵用链表表示的二元树,其根节点为Root,试写出求各结点的层数的算法。
给定一棵用链表表示的二元树,其根节点为Root,试写出求二元树的深度的算法。
在二元树中查找值为x的结点,轻编写算法,打印值为x的结点的所有祖先。假设值为x的结点不多于一个。
在左右链表示的二元树中,查找值为x的结点,并求x结点所在的层数。
算法设计: