以孩子兄弟链作为树的存储结构设计一个求树t的高度的递归算法_孩子兄弟表示法求树的高度

一、左孩子右兄弟存储结构思想

1.1左孩子右兄弟存储结构

如上图所示是一个树的结构，如何将这个树使用左孩子右兄弟的存储方式将其保存到内存中呢？

其实，将这棵树分为两部分左边只连接孩子，并且只能是长子；右边只连兄弟，但要注意在树中只有亲兄弟才算兄弟，如E与F是兄弟，而F与G不是兄弟。只要遵循这一原则，那么就可以以此将上面的树以左孩子右兄弟的方式存储起来。实际上，这种存储方式就是将该树转换成二叉树。由于二叉树结构简单且固定，因此转换成二叉树后续使用递归函数。

左孩子右兄弟存储可表示如下图所示

如上图所示清晰的展示了使用该结构存储后在内存中的逻辑结构，题目中的树已经被转化成二叉树的结构，方便我们进行下一步操作。

思考

这一步操作结束以后大家是否会产生这样的疑问，是不是只能是左孩子右兄弟，难道左兄弟右孩子不可以吗？

关于这个问题在构建递归函数时就会有答案了

二、递归函数模块架构

2.1五大常用算法——分治算法

分治算法顾名思义就是分而治之，将一个大问题分解成多个小问题，再将各个小问题分解，直到不可再分。而递归实际上也是以这种分治的思想来解决问题。

在上一步操作中，我们已经将该树转变成二叉树类型的结构。在二叉树中不管这个二叉树有多高只需要关注三个东西根节点、左子树和右子树。为什么只需要关注这个东西呢？其实我们仔细观察上面的逻辑图就很容易发现不管多复杂的二叉树都是有这三个基本的东西堆积而成的。

如下图：

取上述图中的一部分来看，这就是一个最简单的二叉树只有上述所说的三个结构。通过分治算法的思想我们可以看出B还可以在往下分成根节点、左子树和右子树，直到左子树和右子树都为NULL，说明已经达到不可再分。这就是编写递归函数模块的思想。

三、多文件编写程序

有了上述的分治算法的思想后，就可以多文件编写程序。

头文件（TreeHeigh.h）

#pragma once

#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;

typedef struct TreeNode
{
	ElemType data;
	struct TreeNode* kid;
	struct TreeNode* bro;
}TN;


int TreeHeigh(TN* t);//求出树的高度

void DeleTree(TN* root);//释放malloc函数开辟的空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

子函数模块（TreeHeigh.c）

#include "TreeHeigh.h"

int TreeHeigh(TN* t)
{
	TN* p = NULL;
	int h = 0;
	int maxh = 0;

	if (t == NULL)//判断是否为空树
	{
		return 0;
	}
	else
	{
		p = t->kid;			//p指向第一个孩子结点
		while (p != NULL)	//遍历t的所有子树
		{
			h = TreeHeigh(p);	//通过递归求出子树高度
			if (maxh < h)
			{
				maxh = h;
			}
			p = p->bro;			//继续处理其他子树
		}
		return (maxh + 1);
	}
}

void DeleTree(TN* root)
{
	if (root)
	{
		DeleTree(root->kid);//先往左子树一直寻找

		DeleTree(root->bro);//再往右子树一直寻找

		free(root); //找不到了free返回上一级

		root = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

主函数模块（Text.c）

#include "TreeHeight.h"

int main()
{
	//以下是为了直观的看到该结构是怎样连接，因此是分别开辟空间。
	//也可以自行编写函数调用，此处不再展示
	TN* A = (TN*)malloc(sizeof(TN));
	A->data = 'A';
	A->kid = NULL;
	A->bro = NULL;

	TN* B = (TN*)malloc(sizeof(TN));
	B->data = 'B';
	B->kid = NULL;
	B->bro = NULL;

	TN* C = (TN*)malloc(sizeof(TN));
	C->data = 'C';
	C->kid = NULL;
	C->bro = NULL;

	TN* D = (TN*)malloc(sizeof(TN));
	D->data = 'D';
	D->kid = NULL;
	D->bro = NULL;

	TN* E = (TN*)malloc(sizeof(TN));
	E->data = 'E';
	E->kid = NULL;
	E->bro = NULL;

	TN* F = (TN*)malloc(sizeof(TN));
	F->data = 'F';
	F->kid = NULL;
	F->bro = NULL;

	TN* G = (TN*)malloc(sizeof(TN));
	G->data = 'G';
	G->kid = NULL;
	G->bro = NULL;

	TN* H = (TN*)malloc(sizeof(TN));
	H->data = 'H';
	H->kid = NULL;
	H->bro = NULL;

	//将树之间按照左兄弟右孩子规则连接
	A->kid = B;
	B->kid = D;
	B->bro = C;
	D->bro = E;
	E->kid = H;
	E->bro = F;
	C->kid = G;

	int height = TreeHeigh(A);
	printf("这棵树的深度为：%d", height);

	DeleTree(A);

	return 0;

 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

运行程序后，结果如下图所示

在本段代码中，最为核心的就是递归的调用。如果难以理解递归，也可以将递归展开图画出。在上述中留下了一个问题，即左孩子右兄弟，能否换成左兄弟右孩子。理论上是不可以，我们在使用递归函数时采用先根遍历，也就是说要左子树遍历完之后才去遍历右子树，如果交换位置逻辑上就会出错。