数据结构树简介
一、树简介
树(Tree)是一种抽象的数据结构，是一个数据的集合，集合中的数据组成了一个树状结构。例如上图，看起来像一棵倒挂的树，根朝上叶朝下。
树是由n(n>=0)个节点组成的具有层次关系的数据集合。当 n=0 时，树中没有节点，称为空树。当 n>0 时，有且仅有一个节点被称为根节点(Root)，如果 n=1 ，树只有根节点一个节点。如果 n>1 ，除根节点外，将其余的节点分成m(m>0)个互不相交的数据集合，这 m 个集合每一个都要满足树的结构(有且仅有一个根节点)，并且这 m 棵树都“挂”在根节点上，如此递归下去，直到所有节点都“挂”到这棵树上。其中，这 m 个集合构成的 m 棵树都被称为根节点的子树。
在理解树的结构和定义时，需要运用到递归的思想。以下图为例，树的节点集合为 {A,B,C,D,E,F,G,H} ，n=8，根节点为 A ，除根节点 A 外，其余节点组成了两个(m=2)集合(m1和m2)，m1集合为 {B,D,E} ，m2集合为 {C,F,G,H} 。在m1中，B 为m1的根节点，除 B本文来源gaodai#ma#com搞*!代#%^码$网! 以外，其余节点组成两个集合，集合 {D} 和集合 {E} ，{D} 和 {E} 都只有一个节点，分别构成一棵只有一个节点的树，它们“挂”在m1的根节点 B 上，是 B 的子树，m1构成一棵树，“挂”在根节点 A 上，m1是 A 的子树。同理，在m2中，C 为m2根节点，其余节点组成三个集合 {F} 、{G} 和 {H} ……
二、树的术语
要理解树这种数据结构，必须先理解一些常用的术语。
树由一个一个的节点组成，节点是构成复杂数据结构的基本组成单位。
1. 子节点：又称为孩子节点，一个节点所包含的子树的根节点被称为该节点的子节点。如下图中，节点 B 有两棵子树，这两棵子树的根节点为 D 和 E ，所以 D 和 E 都是 B 的子节点。
2. 父节点：又称为父亲节点，如果一个节点有子节点，则这个节点被称为其子节点的父节点。如下图中，节点 B 有两个子节点 D 和 E ，则 B 是 D 的父节点，也是 E 的父节点。
3. 兄弟节点：具有相同父节点的节点互称为兄弟节点。下图中的 D 和 E 就互为兄弟节点。
4. 堂兄弟节点：如果树的两个节点深度相同，但父节点不同，则它们互为堂兄弟节点。下图中的 D与F，D与G，D与H，D与I 都是堂兄弟节点关系。
5. 节点的祖先：从根节点开始，依次找到某节点所经路径上的所有节点都称为该节点的祖先。如下图中，节点 J 的祖先节点为 A,B,D 。
6. 节点的子孙：以某节点为根的子树中，任一节点都称为该节点的子孙。如下图中，节点 C 的子孙有 F,G,H,I,M,N,O 。
7. 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。如下图中，根节点 A 在第1层，节点 M 在第4层。
8. 节点的深度：一个节点所处的层次称为该节点的深度。如下图中，根节点 A 的深度为1，节点 M 的深度为4 。(上面解释堂兄弟节点时有用到节点的深度，现在可以回去看看)
转载请注明原文链接：数据结构之树的概念详解
