DS之求解二叉树的叶子结点和深度

DS之求解二叉树的叶子结点和深度

这一次需要用到的是二叉树的相关知识，具体的解释会在后面的博客讲述。

如果实现上面的功能就先要构造二叉树以及创造二叉树，还需要求解叶子结点个数函数以及深度函数，这都需要自己去在数据结构的要求中实现。

首先来看二叉树的二叉链表的存储表示：

typedef struct BiTNode//重新定义二叉树的二叉链表的结构
{
   TElemType   data;
   struct  BiTNode   *lchild,*rchild; //左右孩子指针
}BiTNode,*BiTree;

这个结构表示二叉链表的数据域和左右孩子指针域。

再来看看需要实现功能的前期准备：

//0前期准备
#include 
#include 
using namespace std;
#define OK 1
#define FALSE 0
#define TRUE 1
#define ERROR 0
#define OVERFLOW -2
typedef char TElemType;//重新定义char为TElemType
typedef int Status;//重新定义int为Status
typedef struct BiTNode//重新定义二叉树的二叉链表的结构
{
   TElemType   data;
   struct  BiTNode   *lchild,*rchild; //左右孩子指针
}BiTNode,*BiTree;

再者就是需要二叉树的二叉链表的基本操作1：

Status CreateBiTree(BiTree &T)//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树
{
	int i=0;
	char a[100];//定义的字符数组
    cin>>a[i];
    if(a[i]=='#') 
	{
       T=NULL;
	}
    else
	{
        if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) 
		{
			exit(OVERFLOW);
		}
        T->data=a[i];//生成根结点
        CreateBiTree(T->lchild);//构造左子树
        CreateBiTree(T->rchild);//构造右子树
     }
     return OK;
}

然后就是要定义求解叶子结点个数的函数：

int leafcount(BiTree T)//计算树的叶子结点的个数
{
	if(!T)
	{
		return 0;
	}
    else
	{
        if(!T->lchild&&!T->rchild) 
		{
			return 1;
		}
        else 
		{
			return leafcount(T->lchild)+ leafcount(T->rchild);
		}
     }
}

再然后就是要定义求解树深度的函数(两个)：

int get_depth(BiTree T)
{
	int m,n;
	if(!T)
	{
		return 0;
	}
    else
    {
		m=get_depth(T->lchild);
        n=get_depth(T->rchild);
        return (m>n?m:n)+1;
	}
}
void get_sub_depth(BiTree T,char x)//返回二叉树深度的函数
{
    if(T->data==x) 
    {
		cout<lchild)
		{
			get_sub_depth(T->lchild,x);
		}
        if(T->rchild)
		{
			get_sub_depth(T->rchild,x);
		}
     }
}

最后就是主函数中的处理。

完整的求解代码为：

#include 
#include 
using namespace std;
#define OK 1
#define FALSE 0
#define TRUE 1
#define ERROR 0
#define OVERFLOW -2
typedef char TElemType;//重新定义char为TElemType
typedef int Status;//重新定义int为Status
typedef struct BiTNode//重新定义二叉树的二叉链表的结构
{
   TElemType   data;
   struct  BiTNode   *lchild,*rchild; //左右孩子指针
}BiTNode,*BiTree;

Status CreateBiTree(BiTree &T)//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树
{
	int i=0;
	char a[100];//定义的字符数组
    cin>>a[i];
    if(a[i]=='#') 
	{
       T=NULL;
	}
    else
	{
        if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) 
		{
			exit(OVERFLOW);
		}
        T->data=a[i];//生成根结点
        CreateBiTree(T->lchild);//构造左子树
        CreateBiTree(T->rchild);//构造右子树
     }
     return OK;
}
int leafcount(BiTree T)//计算树的叶子结点的个数
{
	if(!T)
	{
		return 0;
	}
    else
	{
        if(!T->lchild&&!T->rchild) 
		{
			return 1;
		}
        else 
		{
			return leafcount(T->lchild)+ leafcount(T->rchild);
		}
     }
}
int get_depth(BiTree T)
{
	int m,n;
	if(!T)
	{
		return 0;
	}
    else
    {
		m=get_depth(T->lchild);
        n=get_depth(T->rchild);
        return (m>n?m:n)+1;
	}
}
void get_sub_depth(BiTree T,char x)//返回二叉树深度的函数
{
    if(T->data==x) 
    {
		cout<lchild)
		{
			get_sub_depth(T->lchild,x);
		}
        if(T->rchild)
		{
			get_sub_depth(T->rchild,x);
		}
     }
}
int main()
{
    BiTree T;//定义二叉树
    CreateBiTree(T);//先序构造二叉树
    cout<<"这棵树叶子的结点个数为：";
	cout<

输入的数据：先序输入ABC##DE#G##F###(#代表空)

这棵树的图为：

输出的结果为：