10、数据结构与算法实战：树-程序员快看-教程，程序员编程资料站

学习笔记：数据结构与算法（十）：树（1）

树
- 一些概念
树的存储结构
- 双亲表示法
- 孩子表示法
- 双亲孩子表示法

树

一些概念

结点拥有的子树数称为结点的度（degree）
度为0的结点称为叶节点（Leaf）或终端结点。
度不为0的结点称为分支结点或非终端结点，除根结点外，分支结点也称为内部结点。

结点的子树的根称为结点的孩子，相应的，该结点称为孩子的双亲，同一双亲的孩子之间互称为兄弟（Silbling）
结点的祖先是从根到该结点所经分支上的所有结点。

图中，A是B和C的双亲，B和C是兄弟。

结点的层次从根开始定，根为第一层，根的孩子为第二层。其双亲在同一层的结点互为堂兄弟。
树中结点的最大层次称为树的深度（depth）或高度。下图深度为3

有序树：树中结点的各子树看成从左至右是有次序的，不能互换的。否则称为无序树
**森林（forest）**是m（m>=0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。

树的存储结构

双亲表示法

以双亲作为索引的关键词的一种存储方式。
一组连续空间存储树的结点，同时在每个节点中附设一个指示其双亲结点在数组中位置的元素。

#define MAX_TREE_SIZE 100
typedef int ElemType;
typedef struct PTNode
{
   
     
	ElemType data;
	int parent;
}PTNode;
typedef struct
{
   
     
	PTNode node[MAX_TREE_SIZE];
	int r; //根的位置
	int n; //结点的数目
}PTree;

一共11个结点，采用前序遍历的方法。看A没有父母-1。B的父母是0。E的父母是B，所以是1（指向B）。
优点：可以根据某结点的parent指针找到双亲结点，时间复杂度为O(1)。索引到-1时，表示找到了树节点的根。
缺点：如果是想找某结点的孩子，则需要遍历整个树结构。

改进：

孩子表示法

树中每个结点可能有多棵子树，考虑用多重链表来实现。
方案一：
根据树的度，声明足够的空间存放子树指针的结点。
缺点：造成了浪费

方案二：

在后面加一个数据，表示需要多少个指针
缺点：克服了浪费，但每个结点的度不同，初始化和维护起来难度很大。

方案三：

数组+链表的结合。ABCDE前面的数据代表数组的下标0，1，2，3等。然后A之后的指针代表自己的孩子，有123，分别代表BCD。

双亲孩子表示法

每个数据后面多了一个元素，代表自己的双亲。

#define MAX_TREE_SIZE 100
typedef char Elemtype;
typedef struct CTNode
{
   
     
	int child ; //孩子结点的下标
	struct CTNode *next;// 指向下一个孩子结点的指针
}*ChildPtr;

//表头结构
typedef struct
{
   
     
	Elemtype data;  //存放在树中结点的数据
	int parent;   //存放双亲的下标
	ChildPtr firstchild;  //指向第一个孩子的指针
}CTBox;

//树结构
typedef struct Tree
{
   
     
	CTBox nodes[MAX_TREE_SIZE];
	int r,n;
}