树、森林与二叉树的相互转换

  继续小结:

  树向二叉树的转换,树的根节点还是二叉树的根节点,根的子树森林构成一棵树二叉树作为根节点的左子树。

  二叉树向树的转换则需要一些条件,这个条件是什么呢?就是这颗二叉树没有右子树。要明白一点,右子树都是兄弟,左子树都是孩子(左子右兄)。同时也能知道如果树用二叉链表存储的话,如果结点没有左子树则意味着其没有孩子,则意味这其是叶子节点。

  森林向二叉树的转换,二叉树的根节点是第一棵子树的根节点,第一棵子树的子树森林构成一棵二叉树作为根节点的左子树,其余的树(也就是森林中除了第一棵树外其他的树)构成一棵二叉树,作为根节点的右子树。

  二叉树向森林的转换,二叉树的根和其右子树转换成第一棵树。(这个过程就是上面提到的二叉树向树转化)。二叉树的右子树按照前面的方法转化成森林。

  二叉树与森林的相互转换用到的基础是二叉树与树的相互转换。

  一棵没有右子树的二叉树可以转化成一棵树,一棵带有右子树的二叉树可以转化成一个森林。

  上面的总结都没有严格的形式定义,如果要写其相互转换的算法,看其定义会更容易写出。

原文地址:https://www.cnblogs.com/wangaohui/p/2819842.html