数据结构学习总结--树和二叉树算法设计题

2022-09-30 14:18:38

1.已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA,请画出这个棵二叉树。
\(\color{red}{中序序列}\)：BDCE A FHG (左根右)
\(\color{red}{后序序列}\)：DECB HGF A (左右根)
解答思路：由后序序列可知二叉树的根节点是A,再由中序序列可知BDCE是二叉树的左子树 FHG是二叉树的右子树
同理，在后序序列BDCE中B是根结点A的左孩子，HGF中F是根结点A的右孩子。由中序序列BDCE可知DCE是B根结点的右子树，HGF可知HG是其右子树。
同理，后序序列DEC中C是根结点B的的右孩子，由中序序列DCE知道D和E分别是C的左右孩子，由后序序列HG知道G是根结点,中序序列HG知道H是G的左孩子。

（2）把这棵二叉树变成树根据之前的口诀：二叉树转化为树：（左孩右右连双亲，去掉原来右孩线）

解答的思路：关于初态不用提将权值的结点依次写入数组1~8中，终态呐从i=9开始（依照哈夫曼树的构造方法选用二小造新树加个根结点，则i=9存储两个权值最小结点构成的新二叉树的根结点权值8，则可知其左右孩子即是两个权值小的3和5即对应结点i=7和i=1，则其左右孩子的父节点parent就是权值8对应的结点i=9; 同理i=10,11,,,,依次选取两个权值较小的构成新二叉树生成新的根结点。

（4）一个具有 1025 个结点的二叉树的高 h 为（）。
A．11 B．10 C．11 至 1025 之间 D．10至 1024 之间
答案：C
解释：若每层仅有一个结点，则树高 h 为 1025；且其最小树高
为 \(log2^{1025}\)取底整数+ 1=11，即 h 在 11 至 1025 之间
（3）一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是（）。
A．250 B． 500 C．254 D．501
答案：D
解释：设度为 0 结点（叶子结点）个数为 A，度为 1 的结点个数为 B，
度为 2 的结点个数为 C，有 A=C+1，A+B+C=1001，可得 2C+B=1000，
由完全二叉树的性质可得 B=0 或 1，又因为 C 为整数，所以 B=0，
C=500，A=501，即有 501 个叶子结点。
2.在一棵度为4的树T中，若有20个度为4的节点，10个度为3的节点，1个度为2的节点，10个度为1的节点，则树T的叶节点个数 答案：82

3.以二叉链表为二叉树的的存储结构，统计二叉树的叶子结点个数。

 `Int LeafNodeCount（BiTree T)
  {   if(T==null)
       return 0;    //如果是空树，则叶子结点个数为0；
     else if(T->lchild==null&&T->rchild==null)
          return 1;  //判断结点是否是叶子结点（左右孩子都为空)若是返回1
     else
          return 
        LeafNodeCount(T-lchild)+   LeafNodeCount(T-rchild);}`

4.以二叉链表为二叉树的的存储结构，判断两棵树是否相等。

   ` Int compareTree(TreeNode *tree1,TreeNode *tree2)  //采用分冶的方法，比较当前根 然后比较左子树和右子树
    {   bool tree1IsNull=(tree1==null);
        bool tree2IsNull=(tree2==null);
        if(tree1IsNull!=tree2IsNull)
           {  return 1;
              }
            if(tree1IsNull&&tree2IsNull)//如果两个都是Null 则相等
              {  
                 return 0;
                   }   //如果根节点不相等 直接返回不相等 否则看它们孩子相等不想等
             if(tree1->C!=tree2->C)
               {
                 return 1;     
               }
           return  (compareTree(tree1->left,tree2->left)&&compareTree(tree1->right,tree2->right))
           return  (compareTree(tree1->left,tree2->right)&&compareTree(tree1->right,tree2->left))
                }`

4.以二叉链表为二叉树的的存储结构,交换二叉树每个结点的左右孩子。

  `////如果结点左右子树为空，否则交换该结点左右孩子然后递归交换左右子树
    void changeLR(BiTree &T)
    {
      BiTree temp;
      if(T->lchild==null&&T->rchild==null)
          return;
      else
       {  temp=T->lchild;
          T->lchild=T->rchild;
          T->rchild=temp;
       }   //交换左右孩子
       changeLR(T->lchild);  //递归交换左子树
       changeLR(T->rchild);  //递归交换右子树
       
       } `

5.以二叉链表为二叉树的的存储结构,输出二叉树中从每个叶子结点到根结点的路径。

  `void AllPath(BTNode *b,ElemType path[],int pathlen)
    {  int i;
       if(b!=null)
       {  if(b->lchild==null && b->rchild==null)  //*b为叶子结点
         {count<<" "<<b->data<<"到根节点的路径："<<b->data;
             for(i=Pathlen-1;i>=0;i--)
             count<<endl;
            }
       else
           { path[pathlen]=b->data;  //当前结点放入路径中
             pathlen++;   //路径长度增1；
           AllPath(b->lchild,path,pathlen);  //递归扫描左子树
           AllPath(b->rchild,path,pathlen);  //递归扫描右子树
             pathlen--; //恢复环境
             }

          }
        }`

码农公寓

相关文章