二叉树求深度的递归的详细分析

》数据结构：

typedef struct BINODE

{

       TELEMETYPE data;

       struct BINODE *lchild,*rchild;

}BiNode,*BiTtree;

》递归函数

int GetTreeDeep(BiTtree T)   //计算二叉树的深度

{

       if(T==NULL)

              return 0;

       else{

              int a = GetTreeDeep(T->lchild);

              int b = GetTreeDeep(T->rchild);

              return (a>b)?(a+1):(b+1);

       }

}

如(a)图，假设给出创建了这个二叉树，使用如上给出的递归实现的经典算法，这个递归过程是怎样的呢？

递归过程中GetTreeDeep这个函数被自身多次调用，让我们给它们标号：

函数 返回值 做什么？ 步骤

GetTreeDeep —-》进入函数 —-》访问A 0

int a = GetTreeDeep(T->lchild); 1 —-》访问B 1

int a = GetTreeDeep(T->lchild); 0 —-》访问B的左空节点 2

int b = GetTreeDeep(T->rchild); 0 —-》访问B的右空节点 3

此时标号2,3函数完成，得到a=0，由步骤2,3得到步骤1函数的a值为1，再由步骤1得到步骤0对应的返回值为2，此时计算到树的高度为2，这只是根节点左部的子树高度，此时运行到刚开始进入函数内的第二个GetTreeDeep，所以接下来该访问右部子树：

int b = GetTreeDeep(T->rchild); —— 》访问C 4

int a = GetTreeDeep(T->lchild); 2 ——》访问D 5

int a = GetTreeDeep(T->lchild); 1 ——》访问F 6

int a = GetTreeDeep(T->lchild); 0 ——》访问F的左空节点 7

int b = GetTreeDeep(T->rchild); 0 ——》访问F的右空节点 8

步骤7,8的返回值为0，由此得到步骤6的返回值为1，步骤4对应的返回值为2，接下来，运行到该访问C的右节点：

int b = GetTreeDeep(T->rchild); ——》访问E 9

int a = GetTreeDeep(T->lchild); 1 ——》访问G 10

int a = GetTreeDeep(T->lchild); 0 ——》访问G的左空节点 11

int b = GetTreeDeep(T->rchild); 0 ——》访问G的右空节点 12

以此类推：可知步骤8的返回值为1，现在该访问E的右节点：

int b = GetTreeDeep(T->rchild); 1 ——》访问H 13

int a = GetTreeDeep(T->lchild); 0 ——》访问H的左空节点 14

int b = GetTreeDeep(T->rchild); 0 ——》访问H的右空节点 15

现在开始返回，比较各个节点的返回值孰大孰小

1， 首先比较的是步骤13和步骤10的返回值，二者一样大，返回1+1，步骤9得返回值2

2， 比较步骤9和5，二者同样为2，故步骤4的返回值为2+1，为3

3， 比较步骤4和步骤1，前者为3，后者为1，取前者，所以最后返回3+1，得步骤0的返回值为4,，即为最终结果。

#include <stdio.h> 
#include <string.h>
#include <stdlib.h>
typedef struct BiTNode{  
char data; 
struct BiTNode *lchild,*rchild; 
}BiTNode,*BiTree; 

//二叉树的建立
BiTree Create(BiTree T)
{ 
	char ch;
	ch=getchar();
	if(ch=='#')
		T=NULL;
	else{
		if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
			printf("空间分配有误!");
		T->data=ch;
		T->lchild=Create(T->lchild);
		T->rchild=Create(T->rchild);
	}
	return T;
} 
//二叉树的前序递归遍历

void Preorder(BiTree T)
{ 
	if(T){
		printf("%c",T->data);
		Preorder(T->lchild);
		Preorder(T->rchild);
	}
} 
//统计二叉树的结点个数
int Sumleaf(BiTree T)
{       
    if(T==NULL){
		return 0;
	}else{
		return Sumleaf(T->lchild)+Sumleaf(T->rchild)+1;
	}
} 
//二叉树的中序递归遍历
void zhongxu(BiTree T)
{     
	if(T){
		zhongxu(T->lchild);
		printf("%c",T->data);
		zhongxu(T->rchild);
	}
} 
//二叉树的后序递归遍历
void houxu(BiTree T)
{     
	if(T){
		houxu(T->lchild);
		houxu(T->rchild);
		printf("%c",T->data);
	}
} 
//计算二叉树的深度
int Depth(BiTree T)
{     //每一层都是先找左再找右 
	int m,n;
	if(T==NULL){
		return 0;
	}else{
		m=Depth(T->lchild);
		n=Depth(T->rchild);
	    if(m>n)
			return (m+1);
		else
			return (n+1);
	}
} 
int main()
{ 
	BiTree T; 
	int sum,dep; 
	T=Create(T); 
	Preorder(T); 
	printf("\n"); 
	zhongxu(T); 
	printf("\n"); 
	houxu(T); 
	printf("\n"); 
	sum=Sumleaf(T); 
	printf("%d",sum); 
	dep=Depth(T); 
	printf("\n%d",dep);
	return 0; 
}

转载：https://blog.csdn.net/weixin_43838785/article/details/101711952