数据结构 树的结构

　　有没有一种情况，每个数据都可以连接多个数据呢?确实存在着这样的情况，当每个数据连接着多个数据的时候，就是图(后续文章会介绍)。当每个数据后面连接着0到多个数据，而前面指连接着一个数据的时候，就是树，就像这样：

　　树状图是一种数据结构，它是由n(n>=1)个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

　　关于树的结构

　　我们之前有谈到数据之间的关系，对于线性表而言，一个数据只会连接另一个数据，这样的关系我们称为的关系，也就是说，一个数据只会有一个后继节点。

　　对于数而说，一个数据后面可能会连接一个数据，也可能连接多个数据，甚至有可能一个数据都没有，这样的关系我们称为一对多的关系。

　　对于线性表而言，因为结构比较简单，所以数据之间互相称为前驱节点，后续节点，代表数据间的关系。而在树中，明显复杂得多。以下是对一颗数的结构描述(以下面的树状图为例)：

　　1、结点(Node)：表示树中的数据元素，由数据项和数据元素之间的关系组成。在图中，共有10个结点。

　　2、结点的度(Degree of Node)：结点所拥有的子树的个数，在图中，结点A的度为3(注意，E,F也符合树的定义(树的定义见下文)所以B的度为2)。

　　3、树的度(Degree of Tree)：树中各结点度的较大值(节点A和D的度都为较大值3)。上图中树的度为3。

　　4、叶子结点(Leaf Node)：度为0的结点，也叫终端结点。上图中，结点E、F、G、H、I、J都是叶子结点。

　　5、分支结点(Branch Node)：度不为0的结点，也叫非终端结点或内部结点。上图中，结点A、B、C、D是分支结点。

　　6、孩子(Child)：结点子树的根。上图中，结点B、C、D是结点A的孩子。

　　7、双亲(Parent)：结点的上层结点叫该结点的双亲。上图中，结点B、C、D的双亲是结点A。

　　8、祖先(Ancestor)：从根到该结点所经分支上的所有结点。上图中，结点E的祖先是A和B。

　　9、子孙(Descendant)：以某结点为根的子树中的任一结点。上图中，除A之外的所有结点都是A的子孙。

　　10、兄弟(Brother)：同一双亲的孩子。上图中，结点B、C、D互为兄弟。

　　11、结点的层次(Level of Node)：从根结点到树中某结点所经路径上的分支数称为该结点的层次。根结点的层次规定为1，其余结点的层次等于其双亲结点的层次加1。

　　12、堂兄弟(Sibling)：同一层的双亲不同的结点。上图中，G和H互为堂兄弟。

　　13、树的深度(Depth of Tree)：树中结点的较大层次数。上图中，树的深度为3。

　　14、无序树(Unordered Tree)：树中任意一个结点的各孩子结点之间的次序构成无关紧要的树。通常树指无序树。

　　15、有序树(Ordered Tree)：树中任意一个结点的各孩子结点有严格排列次序的树。二叉树是有序树，因为二叉树中每个孩子结点都确切定义为是该结点的左孩子结点还是右孩子结点。

　　16、森林(Forest)：m(m≥0)棵树的集合。自然界中的树和森林的概念差别很大，但在数据结构中树和森林的概念差别很小。从定义可知，一棵树由根结点和m个子树构成，若把树的根结点删除，则树变成了包含m棵树的森林。当然，根据定义，一棵树也可以称为森林。