第6章  树和二叉树
一、基础知识题
1．列出右图所示二叉树的叶结点、分支结点和每个结点的层次。
[解答]二叉树的叶结点有⑥、⑧、⑨。分支结点有①、
②、③、④、⑤、⑦。结点①的层次为0；结点②、
③的层次为1；结点④、⑤、⑥的层次为2；结点⑦、
⑧的层次为3；结点⑨的层次为4。
2．使用（1）顺序表示和（2）二叉链表表示法，分别画出右图所示二叉树的存储表示。
[解答]
（1）顺序表示
0
1
2
3
4
5
6
7
8
9
①
②
③
④
⑤
⑥
⑦
1
16
17
⑧
⑨
（2）二叉链表表示
3．在结点个数为n（n>1）的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？
[解答]
结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1，有n层；它有1个叶结点，n-1个分支结点。
4．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
[解答]
    具有3个结点的树                          具有3个结点的二叉树
5．如果一棵树有n1个度为1的结点，有n2个度为2的结点，…，nm个度为m的结点，试问有多少个度为0的结点？试推导之。
[解答]
总结点数      n=n0+n1+n2+…+nm
总分支数      e=n-1= n0+n1+n2+…+nm-1
                =m×nm+(m-1)×nm-1+…+2×n2+n1
则有          n0=
6．试分别出满足以下条件的所有二叉树：
（1）二叉树的前序序列与中序序列相同；
（2）二叉树的中序序列与后序序列相同；
（3）二叉树的前序序列与后序序列相同。
[解答]
（1）二叉树的前序序列与中序序列相同：空树或缺左子树的单支树；
（2）二叉树的中序序列与后序序列相同：空树或缺右子树的单支树；
（3）二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。
先序中序后序遍历二叉树7．填空题
  （1）对于一棵具有n个结点的树，该树中所有结点的度数之和为  n-1    。
  （2）假定一棵三叉树的结点个数为50，则它的最小高度为 4    ，最大高度为  49 。
  （3）一棵高度为h的四叉树中，最多含有  (4h+1-1)/3 结点。
  （4）在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有  6  个。
  （5）一棵高度为5的满二叉树中的结点数为  63  个，一棵高度为3的满四叉树中的结点数为  85  个。
  （6）在一棵二叉树中，假定度为2的结点有5个，度为1的结点有6个，则叶子结点数有  6   个。
  （7）对于一棵含有40个结点的理想平衡树，它的高度为  5   。
（8）若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一堆数组a中，即编号为0的结点存储到a[0]中，其余类推，则a[i]元素的左子女结点为2×i+1  ，右子女结点为  2×i+2  ，双亲结点（i≥1）为。
9．n个结点可构造出多少种不同形态的二叉树？若有3个数据1，2，3，输入它们构造出来的中序遍历结果都为1，2，3的不同二叉树有哪些？
[解答]
有/ (n+1)种。当n=3时，中序遍历都为1，2，3的不同二叉树有5种：
10、判断下列叙述的对错。如果正确，在题前打“√”，否则打“×”。
（1）二叉树是树的特殊情形；
（2）若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点；
（3）若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点；
（4）若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点；
（5）若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。
[解答]
（1）√    （2）×    （3）×    （4）√    （5）×
二、算法设计题
1．若已知两棵二叉树B1和B2皆为空，或者皆不空且B1的左、右子树和B2的左、右子树分别相似，则称二叉树B1和B2相似。试编写算法，判别给定两棵二叉树是否相似。
[解答]
int Bitree_Sim(Bitree B1,Bitree B2)//判断两棵树是否相似的递归算法
{
  if(!B1&&!B2) return 1;
  else if(B1&&B2&&Bitree_Sim(B1->lchild,B2->lchild)&&Bitree_Sim(B1->rchild,B2->rchild))
    return 1;
  else return 0;
}//Bitree_Sim
2．试利用栈的基本操作写出先序遍历的非递归形式的算法。
[解答]
void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法
{
  InitStack(S);
  Push(S,T); //根指针进栈
  while(!StackEmpty(S))
  {
    while(Gettop(S,p)&&p)
    {
      visit(p->data);
      push(S,p->lchild);
    } //向左走到尽头
    pop(S,p);
    if(!StackEmpty(S))
    {
    pop(S,p);
    push(S,p->rchild); //向右一步
    }
  }//while
}//PreOrder_Nonrecursive
3．编写递归算法，计算二叉树中叶子结点的数目。
[解答]
int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目
{
  if(!T) return 0; //空树没有叶子
  else if(!T->lchild&&!T->rchild) return 1; //叶子结点
  else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数
}//LeafCount_BiTree

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