1.孩子-兄弟表示法
一棵树的父亲结点可以有任意个孩子,为了让其像二叉树一样进行遍历,将其转化为二叉树形态。
树转化为二叉树:
- 将每个结点的第一个孩子置为树中的左孩子;
- 将同层级中相邻的第一个兄弟值为树中的右孩子
这种表示方法称之为孩子-兄弟表示法,又称树的二叉链表表示。
1.1树 → 二叉树

1.2二叉树 → 树

1.3 数据结构

typedef int ElemType; typedef struct CSNode { ElemType data; // 数据域 struct CSNode* firstchild; // 第一个孩子 struct CSNode* nextsibling; // 第一个孩子的右兄弟 }CSNode, *CSTree;
2.树的遍历
在树中一个父亲节点可以有多个孩子节点,无左右子树的概念,也无法确定同意层级结点遍历的顺序,即不存在中根遍历方式。

2.1 先根遍历
算法思想
先访问根结点,然后依次先根遍历每棵子树;
上图中,获得先根遍历序列:{1,2,4,5,6,3,7}
孩子兄弟链表表示的二叉树的先序遍历等价于树的先根遍历。
代码
void preOrderTree(CSTree T) { // 树为空,退出 if (T == NULL) return; // 访问根结点 printf("%d ", T->data); CSNode* pCurChild = T->firstChild; // 访问T的每一棵子树根结点 while (pCurChild != NULL) { // 先根遍历子树 preOrderTree(pCurChild); // 指向T的下一棵子树根 pCurChild = pCurChild->nextSibling; } }
2.2 后根遍历
算法思想
先依次后根遍历每棵子树,最后访问根结点;
上图中,获得后根遍历的序列:{4,5,6,2,6,3}
孩子兄弟链表表示的二叉树中的根结点不存在右子树,二叉树的左子树包含了树中所有子树的结点。因此,中序遍历二叉树的左子树等价于遍历树中根结点的所有子树。当中序遍历完所有子树后,最后访问根结点,这与树的后跟遍历相同。
代码
void postOrderTree(CSTree T) { // 树为空,退出 if (T == NULL) return; CSNode* pCurChild = T->firstChild; // 访问T的每一棵子树根结点 while (pCurChild != NULL) { // 后根遍历子树 postOrderTree(pCurChild); // 指向T的下一棵子树根 pCurChild = pCurChild->nextSibling; } // 访问根结点 printf("%d ", T->data); }
3.森林的遍历
森林也可以看成一颗树,每棵树的根结点都可以看作一个虚拟结点,只不过该虚拟结点不出现在转换后的二叉树中。
3.1 森林 < - > 二叉树

3.2 先序遍历森林
- 先访问森林的第一棵树的根结点,
- 然后访问该树的每一棵子树,
- 最后先序遍历森林中待访问的树。
效果等同于依次对各树的先根遍历
3.3 中序遍历森林
- 中序遍历森林中的第一棵树的所有子树;
- 然后再访问第一棵树的根结点;
- 最后中序遍历森林中其余带访问的树。
效果等同于依次对各树的后根遍历