1.树的存储结构

1.双亲表示法（顺序存储）

使用数组，每个结点中保存指向双亲的“指针”。

例如：

1.优缺点

①优点:查指定结点的双亲很方便。
②缺点:查指定结点的孩子只能从头遍历。

2.孩子表示法（顺序+链式存储）

顺序存储各个节点，每个结点中保存孩子链表头指针。
找孩子方便，找双亲不方便。

3.孩子兄弟表示法（链式存储）

使用二叉链表实现，左兄弟，右孩子。

4.森林与二叉树的转换

森林是m (m≥0）棵互不相交的树的集合。
①森林和二叉树的转化：也就是“左孩子右兄弟”，各个树的根节点视为兄弟关系。

2.树的遍历

1.先根遍历

若树非空，先访问根结点,再依次对每棵子树进行先根遍历。
树的先根遍历序列与这棵树相应二叉树的先序序列相同。

2.后根遍历

若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点。
树的后根遍历序列与这棵树相应二叉树的中序序列相同。

3.层序遍历

用队列实现（广度优先遍历）：
①若树非空，则根节点入队
②若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队
③重复②直到队列为空

3.森林的遍历

1.先序遍历

若森林为非空，则按如下规则进行遍历:
①访问森林中第一棵树的根结点。
②先序遍历第一棵树中根结点的子树森林。
③先序遍历除去第一棵树之后剩余的树构成的森林。

效果等同于依次对各个树进行先根遍历。

2.中序遍历

若森林为非空，则按如下规则进行遍历:
①中序遍历森林中第一棵树的根结点的子树森林。
②访问第一棵树的根结点。
③中序遍历除去第一棵树之后剩余的树构成的森林。

效果等同于依次对各个树进行后根遍历。