1.假设在树中,结点x是结点y的双亲时,用(x,y)来表示树边。已知一棵树的树边集合为{(e,i),(b,e),(b,d),(a,b),(g,j),(c,g),(c,f),(h,l),(c,h),(a,c)},用树型表示法表示该树,并回答下列问题:

(1)哪个是根结点?哪些是叶子结点?哪个是g的双亲?哪些是g的祖先?哪些是g的孩子?哪些是e的子孙?哪些是e的兄弟?哪些是f的兄弟?

(2)b和h的层次各是多少?树的深度是多少?以结点c为根的子树的深度是多少?

  树型表示法表示该树如图:

  (1)根结点:a ;
     叶子结点:d、i、f、j、l ;
     g的双亲:c ;
     g的祖先:a、c ;
     g的孩子:j ;
     e的子孙:i ;
     e的兄弟:d ;
     f的兄弟:g、h。
  (2)b的层次:2 ;
     h的层次:3 ;
     树的深度:4 ;
     以结点c为根的子树的深度:3。

2.一棵深度为h的满k叉树有如下性质:第h层上的结点都是叶子结点,其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号,问:

(1)各层的结点数是多少?

(2)编号为i的结点的双亲结点(若存在)的编号是多少?

(3)编号为i的结点的第j个孩子结点(若存在)的编号是多少?

(4)编号为i的结点的有右兄弟的条件是什么?其右兄弟的编号是多少?

  (1)第 $i$ 层的结点数为 $k^{i-1}$。
  (2)编号为 $i$ 的结点的双亲结点的编号为 $\lceil \frac{i-1}{k}\rceil$。
  (3)编号为 $i$ 的结点的第 $j$ 个孩子结点的编号为 $(i-1)k+j+1$。
  (4)编号为 $i$ 的结点有右兄弟的条件是 $i \% k \neq 1$,其右兄弟的编号为 $i+1$。

3.设有如图1所示的二叉树。

(1)分别用顺序存储方法和链接存储方法画出该二叉树的存储结构。

(2)写出该二叉树的先序、中序、后序遍历序列。


图1

  (1)顺序存储方法可以采用双亲数组表示法。

index012345678910
informationabcdefghkmn
parent-10011224466

     链接存储方法可以采用二叉链表。每个结点的信息如下。
     根结点作为链表的head,各个结点按照树图中的关系进行连接即可。

struct node {
    node* leftchild; //存储左孩子结点的地址
    elemtype data; //存储当前结点的值
    node* rightchild; //存储右孩子结点的地址
}

     或者采用孩子兄弟表示法。

firstchildbdf^h^m^^^^
informationabcdefghkmn
nextsibling^c^e^g^k^n^

  (2)先序遍历:abdehkcfgmn;中序遍历:dbhekafcmgn;后序遍历:dhkebfmngca。

4.已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和GDHBAECIF,请画出这棵二叉树,然后给出该树的后序遍历序列。

  该二叉树如图所示:

  该树的后序遍历序列:GHDBEIFCA。

5.设一棵二叉树的中序遍历序列和后序遍历序列分别为BDCEAFHG和DECBHGFA,请画出这棵二叉树,然后给出该树的先序序列。

  该二叉树如图所示:

  该树的先序遍历序列:ABCDEFGH。

6.已知一棵二叉树的中序遍历序列和后序遍历序列分别为dgbaekchif和gdbkeihfca,请画出这棵二叉树对应的中序线索树和后序线索树。

  红色虚线表示前驱/后继。
  中序线索树:

  后序线索树:

7.设有一棵树,如图2所示。

(1)请分别用双亲表示法、孩子表示法、孩子兄弟表示法给出该树的存储结构。

(2)请给出该树的先序遍历序列和后序遍历序列。

(3)请将这棵树转换成二叉树。


图2

  (1)双亲表示法:

index012345678910
informationabcmdehkgfn
parent-10001122233

     孩子表示法:

|index|information|children| |:---:|:---------:|:------:| |0|a|→1→2→3→^| |1|b|→4→5→^| |2|c|→6→7→8→^| |3|m|→9→10→^| |4|d|→^| |5|e|→^| |6|h|→^| |7|k|→^| |8|g|→^| |9|f|→^| |10|n|→^|

     孩子兄弟表示法:

firstchildbdhf^^^^^^^
informationabcmdehkgfn
nextsibling^cm^e^kg^n^

  (2)先序遍历序列:abdechkgmfn;后序遍历序列:debhkgcfnma。
  (3)如图所示:

8.设二叉树t的存储结构如图3所示。其中t为树根结点的指针,Left和Right分别为结点的左、右孩子指针域,data为结点的数据域,请完成下列各题:

(1)画出二叉树t的逻辑结构。

(2)写出按前序、中序和后序遍历二叉树t所得到的结点序列。


图3

  (1)如图所示:

  (2)前序遍历:abcedfhgij;中序遍历:ecbhfdjiga;后序遍历:echfjigdba。

9.表1中m,n分别是一棵二叉树中的两个结点,行号i=1,2,3,4分别表示四种m,n的相对关系,列号j=1,2,3分别表示在前序、中序和后序遍历中m,n之间的先后次序关系,要求在i,j所表示的关系能够同时发生的方格内打“√”。


表1

10.假设二叉树采用二叉链表存储,编写一个后序遍历二叉树的非递归算法。

struct node{
    elemtype data;
    node *left, *right;
}; //采用二叉链表存储方式存储的二叉树结点

void PostOrder(node *tree){
    node *p = tree; //当前操作指针
    node *r = NULL; //记录最近访问过的结点的辅助指针
    stack<node*> s;
    while(p != NULL || !s.empty()){
        if(p != NULL){
            s.push(p);
            p = p->left;
        } //p指针一直走到最左边
        else{
            p = s.top();
            if(p->right != NULL && p->right != r){ //右子树存在,且未被访问
                p = p->right; //p指针访问右子树
            }
            else{
                cout << p->data << " "; //当前访问结点
                s.pop(); //出栈,表示结点已访问过
                r = p; //记录最近访问过的结点
                p = NULL; //重置p指针
            }
        }
    }
}

11.在二叉树中查找值为X的结点,设计打印值为X的结点的双亲的算法。

struct node{
    elemtype data;
    node *left, *right;
}; //采用二叉链表存储方式存储的二叉树结点

//now:当前结点  p:当前结点的双亲   X:需要寻找的值
void PrintXsParent(node *now, node *p, elemtype X){
    if(now == NULL) return; //空结点返回
    PrintXsParent(now->left, now, X); //寻找左孩子
    PrintXsParent(now->right, now, X); //寻找右孩子
    if(now->data == X){ //当前结点值为X
        if(!p) cout << p->data; //若双亲存在,打印双亲
    }
    return;
}

12.以下列顺序插入数据元素,并用边建立边平衡的方式建立AVL二叉排序树。

(1)A,V,L,T,R,E,I,S,O,K

(2)A,Z,B,Y,C,X,D,W,E,V,F

  (1)如下图所示

  (2)如下图所示

13.以A-N为关键字,建立AVL树,并对建立好的树,图示依次删除G,D,N结点。

  AVL树:

  删除G:

  删除D:

  删除N:

14.将下列元素以给定的顺序插入到初始为空的阶为3,7的B-树中。

a g f b k d h m j e s i r x c l n t u p

15.当以适当的次序插入元素时,产生的高度为3(即为3层)的5阶B-树的最少元素数目是多少?

  $3+3+3=9$

16.设给定权值集合w={3,5,7,8,11,12},请构造关于w的一棵huffman树,并求其加权路径长度WPL。

   $WPL=(12+8+11)×2+7×3+(5+3)×4=115$

17.假设用于通信的电文是由字符集{a,b,c,d,e,f,g,h}中的字符构成,这8个字符在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}。

(1)请画出对应的huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构造)。

(2)求出每个字符的huffman编码。

  (1)huffman树如下

  (2)a 0010
     b 10
     c 00000
     d 0001
     e 01
     f 00001
     g 11
     h 0011