Question

数据结构中二叉树如何转化成深林

Answer 1

需要规定一下，比如左子树是儿子，右子树是弟弟，则遍历这棵二叉树，把每个节点复制到森林中，如果是二叉树父节点的左子树，就插在森林中对应二叉树父节点的左子树下，否则插入为该对应节点在森林中的父节点的子节点，刚好是该对应节点最大的弟弟。可以证明有多少个弟弟，这种顺序都不会变的。

Answer 2

将一棵二叉树还原为树或森林，具体方法如下：
（1） 若某结点是其双亲的左孩子，则把该结点的右孩子、 右孩子的右孩子……都与该结点的双亲结点用线连起来。
（2） 删掉原二叉树中所有双亲结点与右孩子结点的连线。
（3） 整理由（1）、（2）两步所得到的树或森林， 使之结构层次分明。
v