多插树转为二叉树

在搞清楚多叉树转换为二叉树之前,我们有必要想清楚,为什么要这样转换?多叉树哪里有缺点需要我们转换为二叉树使用?我们来考虑一个问题:“如果我们将一个多叉树存放在一个数组中,然后删除了整个多叉树。我们能否通过这个仅有的数组恢复原来的多叉树呢?”

答案是不能的,如下图:

2015-06-01_192026

我们可以将一个多叉树,按顺序写入到一个一维的空间中去,但是,如果我们要根据这个一维的空间还原这个多叉树是做不到的,至少我们在还原的时候无法想象,根节点下面到底有多少个子树。所以我们就考虑了文章开头提到的问题,将一个多叉树转换为二叉树。

多叉树转换为二叉树只需要遵循一个原则:左连孩子、右连兄弟。

下面两幅图就是一个将多叉树转换为二叉树的案例:

【多叉树】
2015-06-01_191820

【转换后的二叉树】
2015-06-01_191826

拿 A 节点举例,我们将 A 的左侧指向了其子节点 B,右侧因为他没有兄弟节点所以没有指向。再看 B 节点,左侧指向了其子节点 E ,右侧指向了其兄弟节点 C,经过左孩子、右兄弟的规则转换后,我们就可以成功的得出一个二叉树。

再细节的看一下,实际就是我们让每一个节点都有两个指针,一个指向了子节点,一个指向了兄弟节点。如下图:

2015-06-01_193125

以上便是多叉树转换为二叉树的方法,那对于二叉树储存到一个一维的空间后,如何再次还原回来,我们将在下一篇文章介绍。

发表评论