数据结构作业11—二叉树（函数题）

6-1 二叉树求深度和叶子数 （20 分）

编写函数计算二叉树的深度以及叶子节点数。二叉树采用二叉链表存储结构

函数接口定义：

int GetDepthOfBiTree ( BiTree T);
int LeafCount(BiTree T);

其中 T是用户传入的参数，表示二叉树根节点的地址。函数须返回二叉树的深度（也称为高度）。

裁判测试程序样例：

//头文件包含
#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>

//函数状态码定义
#define TRUE       1
#define FALSE      0
#define OK         1
#define ERROR      0
#define OVERFLOW   -1
#define INFEASIBLE -2
#define NULL  0
typedef int Status;

//二叉链表存储结构定义
typedef int TElemType;
typedef struct BiTNode{
    TElemType data;
    struct BiTNode  *lchild, *rchild; 
} BiTNode, *BiTree;

//先序创建二叉树各结点
Status CreateBiTree(BiTree &T){
   TElemType e;
   scanf("%d",&e);
   if(e==0)T=NULL;
   else{
     T=(BiTree)malloc(sizeof(BiTNode));
     if(!T)exit(OVERFLOW);
     T->data=e;
     CreateBiTree(T->lchild);
     CreateBiTree(T->rchild);
   }
   return OK;  
}

//下面是需要实现的函数的声明
int GetDepthOfBiTree ( BiTree T);
int LeafCount(BiTree T);
//下面是主函数
int main()
{
   BiTree T;
   int depth, numberOfLeaves;
   CreateBiTree(T);
   depth= GetDepthOfBiTree(T);
	 numberOfLeaves=LeafCount(T);
   printf("%d %dn",depth,numberOfLeaves);
}

/* 请在这里填写答案 */

输入样例：

1 3 0 0 5 7 0 0 0

输出样例：

3 2

int GetDepthOfBiTree ( BiTree T)//3
{
    int d1=0, d2=0, d; //递归求左右两个子树的深度取最大的+1
    if(!T)
        return 0;
    else
    {
        d1=GetDepthOfBiTree(T->lchild)+1;
        d2=GetDepthOfBiTree(T->rchild)+1;
    }
     if(d1>d2)
            d=d1;
        else
            d=d2;
    return d;
}

int LeafCount(BiTree T)//2
{
    int n=0;
    if(!T)
        return 0;
    else
    {
        if(T->lchild==NULL && T->rchild==NULL)//条件
            n++;
        else   //分别遍历左右子树
            n=LeafCount(T->lchild)+LeafCount(T->rchild);
    }
    return n;
}
/*       [1]  
        /   
       /     
     [3]     [5]
            /   
           /
         [7]      */

最后

以上就是合适康乃馨为你收集整理的数据结构作业11—二叉树（函数题）的全部内容，希望文章能够帮你解决数据结构作业11—二叉树（函数题）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。