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

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--; //恢复环境
             }

          }
        }`
上一篇:2021-2022-diocs-Linux C语言编程基础(必做)


下一篇:C/C++数据结构-完整代码(四)队列【Queue】(树和二叉树)(二叉树代码实现)