文档介绍:第六章****题
。
,分别写出前序、中序和后序遍历的序列。
,n2个度为2的结点,……,nk个度为k的
结点,则该树中有多少个叶子结点并证明之。
,中序序列为ABCDEFGHIJK,请画出该二叉树。
,则该二叉树的总结点数至少应有多少个?
:
①     前序和后序相同
②     中序和后序相同
③     前序和后序相同
7. n个结点的K叉树,若用具有k个child域的等长链结点存储树的一个结点,则空的Child域有多少个?
:
树的先根次序访问序列为GFKDAIEBCHJ;
树的后根次序访问序列为DIAEKFCJHBG。
,字母在电文中出现的频率分别为:
,,,,,,,
请为这8个字母设计哈夫曼编码。
,要求返回二叉树T的后序序列中的第一个结点指针,是否可不用递归且不用栈来完成?请简述原因.
11. 画出和下列树对应的二叉树:
 
 
 
 
 
 
 
 
 
 
,编写算法,计算二叉树中叶子结点的数目。
:对于二叉树中每一个元素值为x的结点,删去以它为根的子树,并释放相应的空间。
:在先序线索二叉树T中,查找给定结点*p在先序序列中的后继。在后序线索二叉树T中,查找给定结点*p在后序序列中的前驱。
,实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。
,对一棵以孩子-兄弟链表表示的树统计其叶子的个数。
-兄弟链表表示的树编写计算树的深度的算法。
,利用栈的基本操作写出后序遍历非递归的算法。
,写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指:在二叉树中不存在子树个数为1的结点。
。二叉树的最大宽度是指:二叉树所有层中结点个数的最大值。
,利用栈的基本操作写出先序遍历非递归形式的算法。
22. 证明:给定一棵二叉树的前序序列与中序序列,可唯一确定这棵二叉树;
给定一棵二叉树的后序序列与中序序列,可唯一确定这棵二叉树;
23. 二叉树按照二叉链表方式存储,编写算法,计算二叉树中叶子结点的数目。
24. 二叉树按照二叉链表方式存储,编写算法,将二叉树左右子树进行交换。
 
实****题
1.         [