树基本定义

树的定义

数是具有n个节点的有限集。如图即是一个树形结构。

节点分类

节点的度：一个节点拥有的子节点即成为节点的度，比如A节点，有B和C两个子节点，那么A节点的度=2。

叶节点（终端节点）：没有子节点的节点，比如G、H、I....

如图：

节点间关系

孩子节点：某一个节点的子节点称为孩子节点。比如B、C节点是A节点的孩子节点。

双亲节点：与孩子节点相反。比如，A节点是B、C的双亲节点。

兄弟节点：同一个双亲节点的孩子节点，之间称为兄弟节点。比如，B、C为兄弟节点。

如图：

树的存储结构

双亲表示法

双亲的含义我们上面讲述过了。下图中data代表各个节点，parent代表该节点对应双亲的下表地址。

这种结构对于查找双亲很方便，但是对于查找孩子节点就比较麻烦，需要遍历全树。

孩子表示法

孩子表示法，与双亲表示法恰恰相反，双亲节点记录自己的孩子节点，获取最大的数的度，本图中数的最大度为3，所以如图所示

双亲孩子表示法

基于孩子表示法演变，如图所示，将双亲表示法与孩子表示法进行了结合。

这样可以很方便的获取到某个节点的双亲节点及孩子节点。

但是对于获取某个几点的兄弟节点，还是要遍历全树。

孩子兄弟表示法

如图所示，双亲节点记录了，第一个孩子几点，第一个孩子节点记录他的孩子几点及兄弟节点。