什么是树

树是由n (n≥0)个结点构成的有限集合， n=0的树称为空树；当n≠0时，树中的结点应该满足以下两个条件：

1. 有且仅有一个特定的结点称之为根；
2. 其余结点分成m(m≥0)个互不相交的有限集合T1,T2,……Tm，其中每一个集合又都是一棵树，称T1, T2,……Tm为根结点的子树。

如上图所示，A是整个树的根节点，B,C,D是A下面的子树。

树形结构与线形结构有什么区别

结合我们前面所讲的线性结构，两者的区别如上图所示。其中叶子结点表示该树的尾结点，即第一张图的K,L,M

树的相关术语

• 结点的度：结点所拥有的子树的个数。
• 树的度：树中各结点度的最大值。

• 叶子结点：度为0的结点，也称为终端结点。
• 分支结点：度不为0的结点，也称为非终端结点、非叶子结点、分支点或内结点。

• 孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点（子结点），这个结点称为它孩子结点的双亲结点（父结点）；
• 兄弟：具有同一个双亲的孩子结点互称为兄弟。

• 路径：如果树的结点序列n1 , n2 , …, nk，有如下关系：结点ni是ni+1的双亲（1 ≤ i<k），则把n1 , n2 , …, nk称为一条由n1至nk的路径；
• 路径上经过的边的个数称为路径长度。

• 祖先：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点。
• 子孙：某一结点的子树中的所有结点是这个结点的子孙。
• 或者说：在树中，如果有一条路径从结点x到结点y，则x称为y的祖先，而y称为x的子孙。

• 结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。
• 树的深度：树中所有结点的最大层数，也称高度。

• 有序树、无序树。如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树

• 森林m (m>0)棵互不相交的树的集合。一棵树也是一个森林

树的存储结构

首先我们先看下树类存储双亲表示法的基本思想

双亲表示法：

用一维数组来存储树的各个结点（一般按层序存储），数组中的一个元素对应树中的一个结点，包括结点的数据信息以及该结点的双亲在数组中的下标。

data：存储树中结点的数据信息；

parent：存储该结点的双亲在数组中的下标。

如下图所示

上图中F的双亲结点是B，而B的下标是1，所以F的parent的数据就是1。

代码示例

typedef struct node
{ 
  datatype data; // 树中结点的数据信息
	int parent; // 该结点的双亲在数组中的下标
} node;
node treelist[MAXSIZE];
int length, root ; //root根结点的下标

孩子表示法：

树中每个结点除了存储其自身的值之外，还必须指出其所有子女的位置，即整棵树中所有结点的相互关系是通过指明结点子女的位置来体现的，称这种表示法为孩子表示法。

根据子女位置的实现方法不同，孩子表示法分为三种：

1. 数组方式的孩子表示法
2. 指针方式的孩子表示法
3. 链表方式的孩子表示法

数组方式的孩子表示法：

将树中的所有结点存储在一个一维数组中，数组中的每个结点包括一个数据域和多个下标域。每个结点子女的位置通过数组的下标来体现。

下标域的个数等于树的度m

• data：数据域，存放该结点的数据信息；
• child[0]~child[m-1]：下标域，存放该结点的孩子所在的下标。

上图中data[1]的数据域为B,下标域存放B的孩子结点的下标即4，5，-1。

代码示例

typedef struct node{
datatype data;
	int child[m];
} treenode;
treenode tree[MAXSIZE];
int root ,length;

指针方式的孩子表示法:

指针方式的孩子表示法中每个结点通常包含两个域：一个是元素的值域data，另一个为指针数组，数组中的每个元素均为一个指向该结点子女的指针。

指针域的个数等于树的度m

• data：数据域，存放该结点的数据信息；
• child[0]~child[m-1]：指针域，存放该结点的孩子指针。

如下图所示

代码示例

typedef struct node /*结点的类型*/
{
	datatype data;
	struct node *child[m]; /*指向子女的指针数组*/
} node,*tree;
tree root; /*其中root表示指向树根结点的指针。 */

链表方式的孩子表示法:

链表方式的孩子表示法：把每个结点的子女排列起来形成一个单链表，这样n个结点就形成n个单链表；而n个单链表的头指针又组成一个线性表，为了查找方便，使用数组加以存储

代码示例

typedef struct chnode {
	int child; /*孩子结点编号*/
	struct chnode *next; /*指向下一个子女的指针*/
} chnode
typedef chnode * chpoint;

typedef struct
{ /* 树中每个结点的类型 */
	datatype data;
	chnode * firstchild; /*指向第一个子女的指针*/
} node;
node treelist [MAXSIZE];
int length, root；

从上图可以看出，每个结点都是一个链表

• data：数据域，存放该结点的数据信息；
• chnode *：链表，存放该结点的孩子结点。

孩 子 兄 弟 表 示 法：

某结点的第一个孩子是唯一的，某结点的右兄弟也是唯一的。设置两个分别指向该结点的第一个孩子和右兄弟的指针

• data：数据域，存储该结点的数据信息；
• firstchild：指针域，指向该结点第一个孩子；
• rightsibbling：指针域，指向该结点紧挨的右兄弟结点。

typedef struct node {/ *树中每个结点的类型*/
	datatype data;
	struct node * firstchild, *rightsibling;
} node, * pnode;
pnode root; /*指向树根结点的指针*/

以上就是树的基本知识点，希望对小伙伴们有所帮助