数据结构与算法-树（树 森林 树的三种储存结构）_数据结构 树与森林 使用场景

小孱弱弱又来了，终于到树了，等不及了，在这里，有众多以树为基础的数据结构和算法，绝对能令你们折服，这精妙的算法，注定令人收获颇丰，请继续往下看我们在重头戏之前的基本概念吧！
我们的主题是树，那什么是树呢？树就是一对多的形式，只有一个根节点，有根节点向下蔓延，不断连接，构成的，每一个点我们称之为结点，最初的那个节点称为根节点，注意：根节点是唯一的，每个节点向下所指的结点称该节点的孩子，顺势我们称上结点为相连下节点的双亲，注意：每个节点都会有双亲（根节点除外）有且只有一个双亲，一个双亲可以有多个孩子，最下一层节点称为叶子结点，从根节点开始，一直到最远的叶节点的距离成为树的深度或高度，我们的树结构其实就是现实中的树的反转，这样就好理解了吧，树的的术语一定要牢牢记住哦，这些只是我们研究树的基础。
下面简单介绍森林的概念：森林就是多棵树的集合！简单吧！注意：树与树之间不能有相交！！
我们能看到的树说完了，面临了一个问题：我们能看懂，计算机看不懂，这可真头疼，别怕，前辈都帮我们想好了，树的存储方式有三种，双亲表示法，孩子表示法，孩子兄弟表示法。

——首先是双亲表示法，思想很简单，我们对每一个结点旁边加上一个指向它的双亲的指针（根节点指向-1），我们根据结点的指针指轻松找到，他们的双亲，不过也是面临一些问题，给我们一个节点，不能很快找到它的孩子，这就很头疼，于是我门想对他进行改进，除了双亲指针，再加上一个左孩子指针，就能从双亲找到左孩子，不过对于左孩子的兄弟，依然要遍历整棵树才能找到，于是我们打算再加上一个指向兄弟的指针，问题似乎解决了，但是，三个指针，空间代价是巨大的，这个缺陷注定了双亲表示法不常用。
——然后是孩子表示法，孩子表示法其实和双亲表示法相反，在每一个结点旁边加上指向孩子的指针，每一个孩子都有有位置，如果各节点孩子数目相差比较大，这样带来巨大的空间浪费，于是对他进行改进，这次我们利用链表，有一个节点加有一个指针域，用链表把他们串起来，这样对空间利用率大大提高了，我们引入-度的概念，节点的度等于它的孩子数，也就是每个节点将会有度数目的指针域，还是因为它的孩子个数可通大不相同，后期节点的度很难维护，没事，在改进，我们把树的所有节点组成一个线性表，线性表里设置数据域和长子域，长子域指向长子的下标，然后长子记住次子，次子记住……这样就把所有孩子表示完美了，但是问题来了，孩子的双亲是谁？这是个大问题，在改进，在线性表上加上双亲，来记住双亲的下标，堪称完美~
——最后来了我们的最后一种表示方法： 孩子兄弟表示法，这就很简单啦，每个节点设置一个长子域和一个兄弟域，用来指向它的孩子和兄弟，没有兄弟指向NULL，你们肯定就会说，双亲就不好找了，问题有了，那就解决呀，每个节点设置一个双亲域不就得了，最后这种表示方法，其实就是我们以后要说的二叉树结构了，这个可是重头戏，拭目以待吧！！
上代码，供参考：

//双亲表示法
typedef struct PTNode//定义节点 
{
 	int data;
 	
 	int parent;
 	
}OTNode;
typedef struct //树结构 
{
	PTNode nodes[MAXN];
	
	int r,n;//根结点的位置和结点数 
	
}PTtree;
//孩子表示法
typedef struct CTNode//孩子结点 
 {
 	int child;
 	
 	struct CTNode *next;
 	
} *ChildPtr;
typedef struct//表结构 
{
  	int data;
	  
	ChildPtr firstchild;
	
}CTBox;
typedef struct//树结构 
{
	CTBox nodes[MAXN];
	
	int r,n;//根节点位置和结点数 
	
}CTree;
//孩子兄弟表示法
typedef struct CSNode
{
	int data;
	
	struct CSNode*firstchild,*ringhtsib;
	
}CSNode,*CSTree;
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