二叉树实验报告

问题描述

（1）问题描述：①用先序递归过程建立二叉树 (存储结构：二叉链表)。

输入数据按先序遍历所得序列输入，当某结点左子树或右子树为空时，输入‘*’号，如输入abc**d**e**得到的二叉树为：

  

②编写递归算法，计算二叉树中叶子结点的数目。

③按凹入表方式输出该二叉树。

（2）分析：①此题要求用二叉链表作为存储结构，首先要定义二叉链表：

 typedef  struct BiTNode {

            char  data;

            struct BiTNode *lchild, *rchild;

   }BiTNode, * BiTree;

struct BiTNode *lchild, *rchild中lchild，rchild分别表示该结点的左右孩子。

②输入时，按先序遍历所得序列输入，当某结点左子树或右子树为空时，输入‘*’号。

③输出以凹入表的形式输出。

算法思想

（1）按照要求，这道题采用二叉链表来存储矩阵的有关信息。

存储结构定义为：

typedef  struct BiTNode {

            char  data;

            struct BiTNode *lchild, *rchild;

   }BiTNode, * BiTree;

题中共有四个函数，包括主函数main()，创建二叉树函数Status preorder(BiTree &T)，计算叶子结点函数Status calLeaf(BiTree &T)，输出函数Status output(BiTree &T,int)。其中，主函数首先调用preorder()创建二叉树，然后调用函数calLeaf()。最后调用函数output()，输出二叉树。

（2）算法描述：

 main()

   {

         BiTree T;

         int depth = 0;

       

        // 打印提示语

         //输入先序序列

         preorder(T);//调用函数，先序创建二叉树

        

         calLeaf(T);//调用函数calLeaf()计算叶子结点数并打印

         output(T,depth);//调用函数凹入输出

        

         system("pause");

         return 0;

   }

   //创建

   Status preorder(BiTree &T)

   {

          char ch;

         

          scanf("%c",&ch);//读入数据

          if(ch == '*')  

               T=NULL; //读到*号，表明该结点无孩子

          else{

               if ( ! (T=(BiTNode *)malloc(sizeof(BiTNode))) )//动态申请

                     exit(OVERFLOW);

               T-＞data=ch;//将数据计入结点的数据域

               //递归调用

          }

   }//CreatBiTree

   //计算叶子结点数

   Status calLeaf(BiTree &T)

   {

         if(空树,无叶子)      

              return ERROR;

         else if(只有左孩子或右孩子)

              return 1;         /

         else

              递归调用

   }

  

   Status output(BiTree &T,int depth)

   {

          int i;

         

          if(当前结点不为空){

                depth ++;//深度加1

                //打印元素前空格

                //打印数据

                if (左孩子)

                       if (! output(T-＞lchild,depth)) return ERROR;//递归

                if (右孩子)

                  if  (! output(T-＞rchild,depth) )  return ERROR;//递归

                return OK;

          }

          else return ERROR;

   }

源程序

   已提交

测试结果

（1）用户使用说明：

①运行环境：visual C++ 6.0

               Dev-c++

②程序启动：Ctrl+F10

③操作步骤：按照提示输入

④输入：abc**d**e**

           图 1

打印提示语，运行正常。

按要求输入先序遍历序列，按该序列得到的二叉树为图1所示二叉树，叶子结点数为3，a在第一层，b，e在第二层，c，d在第三层。运行正常。

心得体会

（1）Status calLeaf(BiTree &T)

   {

         if(!T)      

              return ERROR;      //空树,无叶子

         else {

              if(!(calLeaf(T-＞lchild)))

                      num ++;

              else if(!(calLeaf(T-＞lchild)))

                      num ++;//递归调用

         }

         return num;

   }

这种算法的思想是递归调用函数，当调用到没有孩子的叶子结点时，num数加1。这样依次计算，最终找到所有的叶子结点。

但是，这种算法在调用时，不能统计右子树上的叶子结点，导致出现下面的错误：

所以改成了现在的算法：

Status calLeaf(BiTree &T)

   {

         if(!T)      

              return ERROR;      //空树,无叶子

         else if(!T-＞lchild && !T-＞rchild)

              return 1;         //只有左孩子或右孩子

         else

              return (calLeaf(T-＞lchild) + calLeaf(T-＞rchild));//递归调用

   }

当T为空时，是空树，叶子结点数为0；当左孩子或右孩子有一个不存在时，叶子结点数为1；当左右孩子都存在时，递归调用，知道找到所有的叶子结点，返回左右子树上叶子结点数之和即为所求。

（2）心得体会：这道题用二叉链表存储二叉树，二叉链表由数据元素，左孩子指针和右孩子指针组成。用二叉链表存储二叉树比较简单，但是不足是不能存储该节点的双亲，这种情况下，用线序序列建立二叉树比较方便。虽然是用二叉链表这种较为简单的方式存储二叉树，但对于初次接触树的概念的我还是一个很好的锻炼机会，增强了对于二叉树孩子与双亲的关系的理解，有助于更好的了解二叉树的结构。

输入数据后，循环调用创建函数，依次读入数据并保存。创建二叉树，计算叶子结点数和打印凹入表都要用到递归函数。可以说，对树和操作都主要是对递归函数的调用，复习了对二叉链表的应用。对于递归算法，现在的理解一直比较模糊，通过这道题在一定程度上增加了对递归函数的理解。

选做

   （1）用先序和中序遍历建立二叉树。用户分别输入一个二叉树的先序遍历序列和中序遍历序列，通过两个遍历序列建立二叉树。

   （2）解决方法：二叉树存储方式不变，但在程序中增加两个字符数组pre[]和in[]分别用于存放两个遍历序列。用递归的算法解决问题。不难发现，pre[]中的第一个元素即为根节点对应的元素。而在in[]数组中，若第i个元素等于pre[0]，那么从第一个到第i-1个元素即为根节点的左子树。按照这个方法，用递归的算法即可构建一棵完整的二叉树。

（3）算法描述：

    Status creatTree(BiTree &T,char pre[],char in[],int p,int q)

   {

         int i = 0; //i表示根节点在中序中的位置

         动态申请

         T-＞data = pre[p];    //根节点

        

         i = q;

         while(in[i] != pre[p])

                   i++;

        

         if(构建左子树){

              //确定左子树的先序序列指针

              creatTree(T-＞lchild,pre,in,p,q); //递归生成左子树

         }

         if(构建右子树){

              //确定右子树的先序序列指针

              //确定右子树的中序序列指针

              creatTree(T-＞rchild,pre,in,p,q);//递归生成右子树

         }

          return OK;

   }