数据结构——树

1.概念：
结点的度：结点拥有的子树的数称为度。度为0的结点称为叶子结点或终端结点。树的度是结点的度的最大值。
结点的层次：根为第一层，根的孩子为第二层。树中结点的最大层次称为树的深度或高度。
2.树的表示
2.1双亲表示法：使用数据和指针表示：指针代表的的父亲的数据的角标，但是存在局限，无法找到孩子。
2.2孩子表示法：找父节点不好找。
最终方案：将每个结点的子结点排列起来，以单链表做存储结构，n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存储在数组中。

image.png

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

image.png
image.png