树的介绍（C语言版）

前言

在数据结构中树是一种很重要的数据结构，很多其他的数据结构和算法都是通过树衍生出来的，比如：堆，AVL树，红黑色等本质上都是一棵树，他们只是树的一种特殊结构，还有其他比如linux系统的文件系统就是一棵树。下面让我们一起来学习一下树的结构和特点吧！

1.树的概念

树是一种非线性的数据结构，它是由n（n >= 0）个有限的节点组成的具有层次结构的集合，把它叫做树，是因为它看起来像一颗倒挂的树，也就是说它根朝上，而叶子朝下的。

》有一个特殊的节点称为根节点，根节点没有前驱节点

》除了根节点外，其余节点被分为M（M>0）个相互不想交的集合T1，T2，T3,...Tm,其中每一个集合Ti（1 <= i <=m）又是一颗结构与树类似的子树。每棵子树的根节点有且只有一个前驱，可以有多个后继。

》因此树是递归定义的

注意：树的结构中，子树之间不能有交集，否则就不是树形结构

2.与树相关

节点的度：一个节点含有子树的个数，例如上图中A的度为6，D的度为1。

叶子节点或者终端节点：度为零的节点被称为叶子结点。例如H，I，P，Q。

非终端节点或者分支节点：度不为零的节点，上图中的：B，C，D,E...

双亲节点或者父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父节点。

孩子节点或者子节点： 一个节点含有的子树的根节点称为该节点的子节点，如上图的B是A的孩子节点。

兄弟节点：具有相同父亲节点的节点互称为兄弟节点。

树的度：一棵树中，最大节点的度称为树的度，如上图树的度为6.

节点的层次：从根节点开始，根为第一层，根的子节点为第二层，以此类推。

树的高度或者深度：树中节点的最大层次，如上图树的高度为4.

堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H，I互为堂兄弟。

节点的祖先：从根到该节点所经分支上的所有节点，如上图，A是所有节点的祖先。

子孙：以某节点为根的子树中的任意一节点都称为该节点的子孙。如上图A节点是所有节点的子孙。

森林：由M棵互不相交的树的集合称为森林。