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###(#代表空)

這棵樹的圖為：

輸出的結果為：