树和二叉树不同，可以有0到n个孩子，所以实现起来很麻烦，但我们可以借助树的孩子兄弟表示法把树转换成二叉树。
在孩子兄弟表示法中，某个结点的第一个孩子结点的指针是二叉树中其左孩子结点指针，右兄弟结点指针是二叉树中右孩子结点指针。
树转换为二叉树过程：
（1）树中所有相同双亲结点的兄弟结点之间加一条连线；
（2）对树中不是双亲结点的第一个孩子的结点，只保留新添加的该结点与左兄弟结点之间的连线，删去该结点与双亲结点之间的连线；
（3）整理所有保留的连线，根据连线摆放成二叉树的结构，转换完成。
二叉树还原为树过程：
（1）若某结点是其双亲结点的左孩子，则把该结点的右孩子，右孩子的右孩子······都与该结点的双亲结点用线连起来；
（2）删除原二叉树中所有双亲结点与右孩子结点的连线；
（3）整理所有保留的连线，根据连线摆放成树的结构，转换完成。
树的遍历：
主要有先根遍历和后根遍历两种，先根遍历序列一定和该树转换的二叉树的前序遍历序列相同；后根遍历序列一定和该树转换的二叉树的中序遍历序列相同。
先根遍历过程：
（1）访问根结点；
（2）按照从左到右的次序先根遍历根结点的每一棵树。
后根遍历过程：
（1）按照从左到右的次序后根遍历根结点的每一棵子树；
（2）访问根结点。
图中先根遍历序列为：ABEJFCGKLDHI 后根遍历序列为：JEFBKLGCHIDA
奈斯
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) | 黑马程序员IT技术论坛 X3.2 |
