Question

【数据结构】树的定义和树的三种存储结构

Answer 1

树（Tree）是n（n>=0）个结点的有限集。n=0时称为空树。在任意一颗非空树中：

假设以一组连续空间存储数的结点，同时在每个结点中， 附设一个指示器指示其双亲结点到链表中的位置 。

把每个结点的孩子结点排列起来，以 单链表作为存储结构 ，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后 n个头指针又组成一个线性表，采用顺序存储结构 ，存放进一个一维数组中。

孩子表示法有两种结点结构： 孩子链表的孩子结点 和 表头数组的表头结点

对于孩子表示法，查找某个结点的某个孩子，或者找某个结点的兄弟，只需要查找这个结点的孩子单链表即可。但是 当要寻找某个结点的双亲时 ，就不是那么方便了。所以可以将双亲表示法和孩子表示法结合，形成 双亲孩子表示法 。

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟存在也是唯一的。因此，设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。