正如利用二进制可以表示许许多多的东西一样，通过是非关系可以表示无穷无尽的事物，合理地设置是非关系（比如海龟汤）就可以获取所有信息。
将任意树通过合适的算法转化为二叉树，利用前面已经学习过的二叉树算法，就可以实现树或森林的存储与遍历。
首先，我们先探讨表示一棵树。
Ⅰ双亲表示法
利用一个结点必定只有一个双亲的一对多性质，倘若我们能记录下每个结点的双亲，那我们一定可以自下而上地，确定一棵树
缺点：由于是自下而上建立的树，找妈容易找儿难，若要求结点的双亲，可以在常量时间迅速完成，但是如果要找结点的所有孩子，就需要对整个结构进行遍历。
//------树的双亲表示存储结构------typedefstructPTNode{TElemTypedata;intparent;//双亲顺序存储位置域}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];introot,n;//root：根的位置n：节点数}PTree;//解释：用一个结构体类型的数组表示了一个pairTElmtype，int//int用于记录双亲顺序存储中的位置，TElemtype存储数据//root记录根结点位置，n记录实际使用空间限
Ⅱ孩子表示法
由于一棵树可能有着许多个孩子，我们要使用孩子表示法从上往下地建立一棵树，可以作以下考虑：
①如何表示多个孩子？
我们可以用一个结构体表示一个结点的孩子们，例如采用如下的存储结构：
datachild1child2...childd其中d应该为树的度，这样才能确保每个结点都能被完全存储，但这里也看出了问题：对于树的度为k的树而言，必定有n(k-1)+1个链域被浪费，在构建一棵大树时，如此多的浪费是难以接受的。
那，能否尝试用变构的结构体来表示孩子们呢？例如
datadegreechild1...childd这似乎是可行的，不过操作起来就有些复杂，比如看到这里的你有思路吗？
我们可以记录data后使用某个函数建立degree为度的数组再往里面存放孩子，操作虽然繁琐但可以节省空间。
下面考虑一种单链表的方法：
将每个链表的孩子手牵起来，双亲结点牵着大兄弟，也可以表示出孩子们，在操作时比较方便直观。
如下树：
我们可以将其用孩子单链表表示的方法表示为：
既然与双亲都是顺序结构表示，我们还可以为孩子链表加上双亲位置，这样可以弥补查找双亲需要全部遍历的缺点。
//--------树的孩子链表存储表示----typedefstructCTNode{intchild;//孩子结点记录孩子相对位置structCTNode*next;//记录下一个孩子在哪里}*ChildPtr;typedefstruct{TElemTypedata;//intparent;加上这一结构，构建带双亲的孩子链表ChildPtrfirstchild;//孩子链表的头指针，注意ChildPtr是指针类型}CTBox;typedefstruct{CTBoxnodes[MAX_TREE_SIZE];intn,root;//结点数和根位置}CTree;
以上两种表示法都可以表示出一棵树，但是似乎并没有转化为二叉树，若要使用以上的数据结构进行遍历等操作，我们还需要另外写函数，是比较麻烦的，那应该怎样表示才能转换二叉树呢？
Ⅲ孩子兄弟表示法
//------树的孩子兄弟表示法---------typedefstructCSNode{TElemTypedata;structCSNode*firstchild,*nextsibling;}CSNode;
单个结点结构：
第一个孩子firstchild数据data下一个兄弟nextsibling左子右兄
这不就是一颗二叉树了吗？（和上例同树）
操作方法访问某节点第x个孩子沿着firstchild走一步，再沿着nextsibling走x-1步访问孩子的孩子沿着firstchild走两步访问parent可以增设parent域至此，我们知道了树可以转化为二叉树进行表示，如何将森林用二叉树表示呢？
森林其实就是去掉了根结点的树
我们可以将森林的根结点们视作兄弟进行二叉树的建立，例如：
这样其实就非常好理解了。
森林F={T1,T2,...,Tm}TO二叉树:
（1）如果F为空，m=0，二叉树为空树；
（2）如果F非空，m~=0；则B的根root为森林中第一棵树的ROOT（T1），左子树是T1结点的子树森林转换而成的二叉树，右子树是从去掉当前树的森林转化而成的二叉树。可以看出，建立森林2二叉树时采用递归定义。
二叉树B={root,LB,RB)TO森林F={T1,T2,..,Tm}
（1）如果B为空，F为空
（2）如果B非空，二叉树的root为T1的根，二叉树的左树构建T1，右树继续构建T2,T3,...,Tm的森林。依然是采用递归进行转化。
树和森林既然存储结构上可以转换为二叉树，那自然的，树和森林的操作也可以用二叉树的操作进行实现。
利用二叉树的遍历实现树和森林的遍历
树的先根遍历
先访问根节点，再依次先根遍历根的每棵子树
对于如图所示树，采用先根遍历得到的结果是
A B C D E
树的后根遍历
对于上图所示树，后根遍历为
B D C E A
如何理解？
与二叉树的遍历相同，当先被指或后被指时输出。
于是，我们有如下两种对森林进行遍历的方法：
先序遍历森林
（1）访问森林中第一棵树根节点
（2）先序遍历第一棵树子树森林
（3）先序遍历剩余子树森林
同样，也是用到了递归思想。
实际操作时：
（1）F2B
（2）先序遍历二叉树
中序遍历森林
（1）中序遍历第一棵树根节点子树森林
（2）访问第一棵树根结点
（3）中序遍历剩余子树森林
实际操作则为：
（1）F2B
（2）中序遍历二叉树
-----------
F2B算法应该根据具体题目的数据结构参照转换规则采用递归写出。
预览时标签不可点收录于话题#个上一篇下一篇