Question

这样的树怎么转换成二叉树？

如图是一颗有序树（结点C只有右孩子D）
怎么用数据结构书上说的孩子兄弟表示法转换成另外一棵二叉树？
虽然这棵树本身也是二叉树，但是按照定义这也是有序树。。。
你们怎么不回复啊，有木有其他人来帮帮我啊？

Answer 1

孩子兄弟表示法一般是将森林或不规则N叉树转换为二叉树的；由于计算机中只有01两个符号；所以使用二叉树是容易硬件操作的。但是呢，原来的森林或者多叉树人家是有规则和顺序的，你为了存储和操作方便把他转换成二叉树存储，但是还必须保存下原来的意义。比方说三叉树中A结点下边有三个孩子分别为BCD，好，你给人家转为二叉树了，但是你至少应该将来能从这个二叉树中恢复出原有的信息--那就是A是根，底下有BCD三个点这个事实吧。由此产生了孩子兄弟表示法--即任何森林或树按照左孩子为第一个实际孩子，又孩子为该节点的右侧第一个实际兄弟结点的方式表示，如果仔细推敲的话，这种方式恰好能够用二叉树的形式表示原来森林或多叉树的结构。此题目中形成的二叉树为

追问

那这个转换后再转换回去怎么知道d结点是c的左孩子还是右孩子？

Answer 2

左子树是第一个孩子，右子树是其第一个兄弟（sibling)，递归定义。

追问

那么如果是要转换这棵树怎么办？

追答

树的兄弟节点通常是没有次序的。追加的只能是树，不能是二叉树。

追问

没有次序的?那为什么书上说的是有序树啊？