统计二叉树系统的设计与实现

统计二叉树系统的设计与实现 6.1问题的描述

建立二叉树，统计二叉树中度为2的结点个数和叶子结点个数（ 用递归或非递归的方法都可以，先序、中序或后序均可）

6.2问题分析和任务定义

(1) 要求能够输入树的各个结点；

(2) 要求能输出中度为2的结点及个数的函数、输出叶子结点及个数的函数；

6.3 数据类型和系统设计

（1）存储结构设计

运用先序遍历，通过累加的方法统计度为2的结点个数和叶子结点个数。

（2）系统功能设计

(1) 建立一个二叉树；

(2) 统计二叉树中的结点数；

(3) 输出所有叶子结点；

6.4 编码实现

#include

#include

#include

typedef struct Node{        //二叉树的链式存储结点

         char data;

         struct Node *Lchild;

         struct Node *Rchild;

}BiTNode,*BiTree;

（1）创建整个二叉树

void CreateBiTree(BiTree *root){      //形参采用二级指针，实参为结点孩子域地址

         char ch;

         ch=getchar();             //‘#’为子节点为空，保存整个二叉树

         if(ch=='#')    *root=NULL;

         else{

                  *root=(BiTree)malloc(sizeof(BiTree));

             (*root)->data=ch;

             CreateBiTree(&((*root)->Lchild));

             CreateBiTree(&((*root)->Rchild));

         }

}

void Visit(char data){

         printf("%c",data);

}

int zero=0,one=0,two=0;

（2）统计二叉树中的结点数

void Statistics(BiTree T){   

 if(T){

        if(T->Lchild!=NULL&&T->Rchild!=NULL) two++;

        else if(T->Lchild==NULL&&T->Rchild==NULL) zero++;

        else one++;

        Statistics(T->Lchild);

        Statistics(T->Rchild);

        /*采用先序递归遍历的方法*/

 }

}

（3）输出所有叶子结点

void Printf_Leaf(BiTree T){         //输出所有叶子结点

         if(T){

             if(T->Lchild==NULL&&T->Rchild==NULL)

                 printf("%c",T->data);

             Printf_Leaf(T->Lchild);

                  Printf_Leaf(T->Rchild);       

         }

}

void Printf_Two(BiTree T){   //输出度为2的结点

         if(T){

             if(T->Lchild!=NULL&&T->Rchild!=NULL)

                 printf("%c",T->data);

             Printf_Two(T->Lchild);

                  Printf_Two(T->Rchild);       

         }

}

int main(){

         BiTree T;

         printf("请输入结点序列构造二叉树:");

         CreateBiTree(&T);

         Statistics(T);

         printf("度为0的结点数为%d;度为1的结点数为%d;度为2的结点数为%d\n",zero,one,two);

         printf("度为0的结点是:");

         Printf_Leaf(T);

         printf("\n");

         printf("度为2的结点是:");

         Printf_Two(T);

         printf("\n");

         return 0;

}

6.5 测试结果