数据结构（中国海洋大学） 第六章_智慧树知到答案2021年

第六章 树和二叉树：树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。6.1树的定义和基本术语:树是n个结点的有限集合，非空时必须满足：只有一个称为根的结点；其余结点形成m个不相交的子集，并称 根的子树。 根是开始结点；结点的子树数称度；度为0的结点称叶子（终端结点）；度不为0的结点称分支结点（非终端结 点）；除根外的分支结点称内部结点； 　有序树是子树有左，右之分的树；无序树是子树没有左，右之分的树；森林是m个互不相交的树的集合；
6.2二叉树:二叉树及其基本术语的定义，二叉树的基本性质及证明过程，二叉树的顺序存储及二叉链表、三叉链表的存储方法。
6.3遍历二叉树和线索二叉树:遍历二叉树的三种方法的定义及其实现的递归算法，以及中序遍历的非递归算法，线索二叉树的定义、存储结构、中序线索树的遍历算法、建立中序线索树的算法。
6.4树和森林:树的双亲表示法、孩子链表表示法、儿子-兄弟链表存储表示方法，森林与二叉树的转换方法，以及树和森林的遍历算法的描述。
6.5赫夫曼树及其应用:最优二叉树的定义，赫夫曼树的定义、构造方法、赫夫曼编码方法、及其算法描述。
6.6树的计数:树的计数的定义，二叉树的计数问题，树的计数问题。
6.1树的定义和基本术语:树是n个结点的有限集合，非空时必须满足：只有一个称为根的结点；其余结点形成m个不相交的子集，并称 根的子树。 根是开始结点；结点的子树数称度；度为0的结点称叶子（终端结点）；度不为0的结点称分支结点（非终端结 点）；除根外的分支结点称内部结点； 　有序树是子树有左，右之分的树；无序树是子树没有左，右之分的树；森林是m个互不相交的树的集合；
6.2二叉树:二叉树及其基本术语的定义，二叉树的基本性质及证明过程，二叉树的顺序存储及二叉链表、三叉链表的存储方法。
6.3遍历二叉树和线索二叉树:遍历二叉树的三种方法的定义及其实现的递归算法，以及中序遍历的非递归算法，线索二叉树的定义、存储结构、中序线索树的遍历算法、建立中序线索树的算法。
6.4树和森林:树的双亲表示法、孩子链表表示法、儿子-兄弟链表存储表示方法，森林与二叉树的转换方法，以及树和森林的遍历算法的描述。
6.5赫夫曼树及其应用:最优二叉树的定义，赫夫曼树的定义、构造方法、赫夫曼编码方法、及其算法描述。
6.6树的计数:树的计数的定义，二叉树的计数问题，树的计数问题。

[单选题]已知一棵树边的集合为{<I,M>, <I,N>, <E,I>, <B,E>, <B,D>, <A,B>, <G,J>, <G,K>, <C,G>, <C,F>, <H,L>, <C,H>, <A,C>},问这棵树中结点G的双亲结点为(   )

选项:[I, B, C, A]
[单选题]

一棵二叉树中，叶子的个数为10，则其度为2的结点的个数为 (    ) ；

选项:[10, 12, 9, 11]
[单选题]

假如一棵二叉树的中序遍历结果为ABCD，则结点A和结点D的关系一定不是（     ）； 

选项:[结点A是结点D的双亲结点, 结点A是结点D的右子树上的结点 , 结点A与结点D具有共同的双亲的右子树上的结点 , 结点A是结点D的左子树上的结点 ]
[单选题]

已知一棵树边的集合为{<I,M>, <I,N>, <E,I>, <B,E>, <B,D>, <A,B>, <G,J>, <G,K>, <C,G>, <C,F>, <H,L>, <C,H>, <A,C>},将此树转化为二叉树后，E的左孩子为（   ）；

选项:[C, A, B, I]
[单选题]一棵哈夫曼树有17个结点，则其叶子结点的个数是 _________ 。

选项:[9, 10, 7, 8]
[单选题]

写递归算法，将二叉树中所有结点的左、右子树相互交换。

Status ExchangeBiTree(BiTree& T)

{

     BiTreep;

     if(T){

          p=T->lchild;

          T->lchild=T->rchild;

          T->rchild=p;

          ExchangeBiTree(T->lchild);

       __________ }

     returnOK;

}

选项:[ExchangeBiTree(T);, ExchangeBiTree(T->rchild);, ExchangeBiTree(T->lchild->rchild), A.ExchangeBiTree(p); ]
[单选题]

试写一个算法，为一棵二叉树建立后序线索二叉树。

StatusPostOrderThreading(BiThrTree& T,BiThrTree& pre);//首先建立后序线索树

StatusFindNextInBiThrTree(BiThrTree& q,TElemType *p);//再进行查找

 

// 后序线索二叉树的算法

StatusPostOrderThreading(BiThrTree& Thrt,BiThrTree& T)

{

     BiThrTree pre;

     Thrt=new BiThrNode; // 为线索二叉树建立头结点

     if(!Thrt) exit(OVERFLOW);

     Thrt->LTag=Link;

     Thrt->RTag=Thread;

     Thrt->rchild=Thrt;// 右子树回指

     if(!T) Thrt->lchild=Thrt;// 若二叉树空，左子树回指

     else{

          Thrt->lchild=T;

          pre=Thrt;

          PostThreading(T,pre);// 后序遍历进行后序线索化

          pre->rchild=Thrt;//最后一个结点线索化

          pre->RTag=Thread;

          Thrt->rchild=pre;

     }

     return OK;

}

 

StatusPostThreading(BiThrTree& T,BiThrTree& pre)

{

     if(T){

          if(T->LTag==Link)PostThreading(T->lchild,pre);

          if(T->RTag==Link)PostThreading(T->rchild,pre);

          if(!T->lchild){

               T->LTag=Thread;

              ___________

          }

          if(pre &&!pre->rchild){

               pre->RTag=Thread;

               pre->rchild=T;

          }

          pre=T;

     }

     return OK;

}

选项:[T->lchild=pre; , pre->lchild=T, T->rchild=pre, pre->rchild=T]
[单选题]

1.编写递归算法，将二叉树中所有结点的左、右子树相互交换。

StatusExchangeBiTree(BiTree& T)

{

     BiTree p;

     if(T){

         p=T->lchild;

         T->lchild=T->rchild;

         T->rchild=p;

         ExchangeBiTree(T->lchild);

                      }

     return OK;

}

选项:[ ExchangeBiTree(T->rchild);, ExchangeBiTree(T);, ExchangeBiTree(p); , ExchangeBiTree(T->lchild->rchild);]
[单选题]

写递归算法，将二叉树中所有结点的左、右子树相互交换。

Status ExchangeBiTree(BiTree& T)

{

     BiTreep;

     if(T){

          p=T->lchild;

          T->lchild=T->rchild;

          T->rchild=p;

          ExchangeBiTree(T->lchild);

       __________ }

     returnOK;

}

选项:[ExchangeBiTree(T->rchild);, A.ExchangeBiTree(p); , ExchangeBiTree(T);, ExchangeBiTree(T->lchild->rchild)]
[单选题]

1.编写递归算法，将二叉树中所有结点的左、右子树相互交换。

StatusExchangeBiTree(BiTree& T)

{

     BiTree p;

     if(T){

         p=T->lchild;

         T->lchild=T->rchild;

         T->rchild=p;

         ExchangeBiTree(T->lchild);

                      }

     return OK;

}

选项:[ExchangeBiTree(p); , ExchangeBiTree(T->lchild->rchild);, ExchangeBiTree(T);, ExchangeBiTree(T->rchild);]
[单选题]已知一棵树边的集合为{<I,M>, <I,N>, <E,I>, <B,E>, <B,D>, <A,B>, <G,J>, <G,K>, <C,G>, <C,F>, <H,L>, <C,H>, <A,C>},问这棵树中结点G的双亲结点为(   )

选项:[A, I, B, C]
[单选题]

已知一棵树边的集合为{<I,M>, <I,N>, <E,I>, <B,E>, <B,D>, <A,B>, <G,J>, <G,K>, <C,G>, <C,F>, <H,L>, <C,H>, <A,C>},将此树转化为二叉树后，E的左孩子为（   ）；

选项:[C, I, A, B]
[单选题]

试写一个算法，为一棵二叉树建立后序线索二叉树。

StatusPostOrderThreading(BiThrTree& T,BiThrTree& pre);//首先建立后序线索树

StatusFindNextInBiThrTree(BiThrTree& q,TElemType *p);//再进行查找

 

// 后序线索二叉树的算法

StatusPostOrderThreading(BiThrTree& Thrt,BiThrTree& T)

{

     BiThrTree pre;

     Thrt=new BiThrNode; // 为线索二叉树建立头结点

     if(!Thrt) exit(OVERFLOW);

     Thrt->LTag=Link;

     Thrt->RTag=Thread;

     Thrt->rchild=Thrt;// 右子树回指

     if(!T) Thrt->lchild=Thrt;// 若二叉树空，左子树回指

     else{

          Thrt->lchild=T;

          pre=Thrt;

          PostThreading(T,pre);// 后序遍历进行后序线索化

          pre->rchild=Thrt;//最后一个结点线索化

          pre->RTag=Thread;

          Thrt->rchild=pre;

     }

     return OK;

}

 

StatusPostThreading(BiThrTree& T,BiThrTree& pre)

{

     if(T){

          if(T->LTag==Link)PostThreading(T->lchild,pre);

          if(T->RTag==Link)PostThreading(T->rchild,pre);

          if(!T->lchild){

               T->LTag=Thread;

              ___________

          }

          if(pre &&!pre->rchild){

               pre->RTag=Thread;

               pre->rchild=T;

          }

          pre=T;

     }

     return OK;

}

选项:[pre->lchild=T, T->lchild=pre; , T->rchild=pre, pre->rchild=T]
[单选题]

一棵二叉树中，叶子的个数为10，则其度为2的结点的个数为 (    ) ；

选项:[9, 11, 10, 12]
[单选题]一棵哈夫曼树有17个结点，则其叶子结点的个数是 _________ 。

选项:[8, 10, 7, 9]
[单选题]

假如一棵二叉树的中序遍历结果为ABCD，则结点A和结点D的关系一定不是（     ）； 

选项:[结点A是结点D的左子树上的结点 , 结点A是结点D的双亲结点, 结点A与结点D具有共同的双亲的右子树上的结点 , 结点A是结点D的右子树上的结点 ]