文档介绍：第五章树和二叉树
一、名词解释
1、树
2、结点的度
3、叶子
4、分支点
5、树的度
6、父结点
子结点
7、兄弟
8、结点的层数
9、树的高度
10、二叉树
11、空二叉树
12、左孩子
右孩子
13、满二叉树
14、完全二叉树
15、哈夫曼树
16、先根遍历
17、中根遍历
18、后根遍历
二、下面是有关二叉树的叙述,请判断正误
( )1、若二叉树用二叉链表作存储结构,则在n个结点的二叉树链表中只有n—1个非空指针域。
( )2、二叉树中每个结点的两棵子树的高度差等于1。
( )3、二叉树中每个结点的两棵子树是有序的。
( )4、二叉树中每个结点有两棵非空子树或有两棵空子树。
( )5、二叉树中每个结点的关键字值大于其左非空子树(若存在的话)所有结点的关键字值,且小于其右非空子树(若存在的话)所有结点的关键字值。
( )6、二叉树中所有结点个数是2k-1-1,其中k是树的深度。
( )7、二叉树中所有结点,如果不存在非空左子树,则不存在非空右子树。
( )8、对于一棵非空二叉树,它的根结点作为第一层,则它的第i层上最多能有2i—1个结点。
( )9、用二叉链表法(link-rlink)存储包含n个结点的二叉树,结点的2n个指针区域中有n+1个为空指针。
(正确。用二叉链表存储包含n个结点的二叉树,结点共有2n个链域。由于二叉树中,除根结点外,每一个结点有且仅有一个双亲,所以只有n-1个结点的链域存放指向非空子女结点的指针,还有n+1个空指针。)
( )10 、具有12个结点的完全二叉树有5个度为2的结点。
( )11 、二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面。
( )12 、由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树
三、填空题
1、树(及一切树形结构)是一种“________”结构。在树上,________结点没有直接前趋。对树上任一结点X来说,X是它的任一子树的根结点惟一的________。
2、一棵树上的任何结点(不包括根本身)称为根的________。若B是A的子孙,则称A是B的________
3、一般的,二叉树有______二叉树、______的二叉树、只有______的二叉树、只有______
的二叉树、同时有______的二叉树五种基本形态。
4、二叉树第i(i>=1)层上至多有______个结点。
5、深度为k(k>=1)的二叉树至多有______个结点。
6、对任何二叉树,若度为2的节点数为n2,则叶子数n0=______。
7、满二叉树上各层的节点数已达到了二叉树可以容纳的______。满二叉树也是______二叉树,但反之不然。
8、具有n个结点的完全二叉树的深度为______。
9、如果将一棵有n个结点的完全二叉树按层编号,则对任一编号为i(1<=i<=n)的结点X有:
(1) 若i=1,则结点X是______;若i〉1,则X的双亲的编号为______。
(2) 若2i>n,则结点X无______且无______;否则,X的左孩子的编号为______。
(3) 若2i+1>n,则结点X无______;否则,X的右孩子的编号为______。
10、每个二叉链表的访问只能从______结点