6.4 树和森林

01树的存储结构

1、在大量的应用中，人们曾使用多种形式的存储结构来表示树。

2、双亲表示法：假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。这种表示法中，求结点的孩子时需要遍历整个结构。

3、孩子表示法：由于树中每个结点可能有多棵子树，则可用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点。

4、孩子兄弟表示法：又称二叉树表示法，或二叉树表表示法。即以二叉链表作树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为firstchild域和nextsibling域。

02森林与二叉树的转换

1、由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。

2、给定一棵树，可以找到唯一的一棵二叉树与之对应，从物理结构来看，他们的二叉链表是相同的，只是解释不同而已。

03树和森林的遍历

1、由树结构的定义可引出两种次序遍历树的方法：一种是根（次序）遍历树，即：先访问树的根结点，然后依次先根遍历根的每棵子树；另一种是后根（次序）遍历，即：先依次后根遍历每棵子树，然后访问根结点。

2、先序遍历森林：若森林非空，则可按下述规则遍历之：

（1）访问森林中第一棵树的根结点。

（2）先序遍历第一棵树中根结点的子树森林。

（3）先序遍历除去第一棵树之后剩余的树构成的森林。

3、中序遍历森林：若森林非空，则可按下述规则遍历之：

（1）中序遍历森林中第一棵树的根结点的子树森林。

（2）访问第一棵树的根结点。

（3）中序遍历除去第一棵树之后剩余的树构成的森林。

C语言 | 用指针对10个数排序​ mp.weixin.qq.com

文章来源: zhuanlan.zhihu.com，作者：小林C语言，版权归原作者所有，如需转载，请联系作者。

原文链接：zhuanlan.zhihu.com/p/337457439