⑴  假设在树中， 结点x是结点y的双亲时，用(x,y)来表示树边。已知一棵树的树边集合为 { (e,i), (b,e), (b,d), (a,b), (g,j), (c,g), (c,f), (h,l), (c,h), (a,c) } ，用树型表示法表示该树，并回答下列问题：
  ① 哪个是根结点? 哪些是叶子结点? 哪个是g的双亲? 哪些是g的祖先? 哪些是g的孩子? 那些是e的子孙? 哪些是e的兄弟? 哪些是f的兄弟?
先序中序后序遍历二叉树  ② b的层次各是多少? 树的深度是多少? 以结点c为根的子树的深度是多少?
根节点：a            叶子节点：i ,d , j, f , l          g 的双亲节点:c
g 的祖先：c , a        g 的孩子：j                  e 的子孙：i
e的兄弟：d          f的兄弟：g , h
b的层次：2          树的深度：4        以结点c为根的子树的深度：3
⑵  一棵深度为h的满k叉树有如下性质： 第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。 如果按层次顺序(同层自左至右)从1开始对全部结点编号，问：
① 各层的结点数是多少?
② 编号为i的结点的双亲结点(若存在)的编号是多少?
③ 编号为i的结点的第j个孩子结点(若存在)的编号是多少?
④ 编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少?
(1) 设层号为i的结点数目为m=k^(i-1)
(2) 编号为i的结点的双亲结点的编号是：[(i+k-2)/k](不大于(i+k-2)/k的最大整数。也就是(i+k-2)与k整除的结果.以下/表示整除。
(3) 编号为i的结点的第j个孩子结点编号是：k*(i-1)+1+j;
(4)编号为i的结点有右兄弟的条件是(i-1)能被k整除   右兄弟的编号是i+1.
⑶ 设有如图6-27所示的二叉树。
① 分别用顺序存储方法和链接存储方法画出该二叉树的存储结构。
② 写出该二叉树的先序、中序、后序遍历序列。
顺序存储结构：
链式存储结构
先序：abdehkcfgmn
中序：dbhekafcmgn
后序：dhkebfmngca
⑷ 已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和GDHBAECIF，请画出这棵二叉树，然后给出该树的后序遍历序列。
后序：GHDBEIFCA
⑸ 设一棵二叉树的中序遍历序列和后序遍历序列分别为BDCEAFHG和DECBHGFA ，请画出这棵二叉树，然后给出该树的先序序列。
先序遍历：ABCDEFGH
⑹ 已知一棵二叉树的中序遍历序列和后序遍历序列分别为dgbaekchif和gdbkeihfca，请画出这棵二叉树对应的中序线索树和后序线索树。
二叉树：
中序线索树：
后序线索树：
⑺ 以二叉链表为存储结构，请分别写出求二叉树的结点总数及叶子结点总数的算法
叶子节点数：
#define  MAX_NODE  50
int  search_leaves( BTNode  *T)
{  BTNode  *Stack[MAX_NODE] ,*p=T;
int  top=0, num=0;
if  (T!=NULL)
{  stack[++top]=p ;
while (top>0)
  {  p=stack[top--] ;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。