树转二叉树

 我们要将一棵普通的树转为二叉树,要遵循这样的原则:孩子结点→左子树结点,兄弟结点→右子树结点。

根结点1还作为根结点,它有三个孩子结点2、3、4,那么这三个孩子结点都应该转为新二叉树的左子树部分(因为1没有兄弟结点,所以新二叉树没有右子树部分),我们选取最左边的孩子结点2作为新二叉树的左子树结点(左子树的根),而结点3和4为结点2的兄弟结点,所以3和4应该转为2的右子树部分。4是3的兄弟结点,所以4应该作为3的右子树部分。而5、6、7是3的孩子结点,所以对应为3的左子树部分,我们同样选取最左边的孩子结点5作为3的左子树的根,而6和7作为5的兄弟结点,应该转为5的右子树部分,再次选取最左边的孩子结点6作为5的右子树的根,而7作为6的兄弟,直接转为6的右子树部分即可。再来看3的右子树部分,4作为3的兄弟结点,应该转为3的右子树的根,而8和9是4的孩子结点,全部转为4的左子树部分,选取最左边的孩子结点8作为4的左子树的根,而9作为8的兄弟结点,直接转为8的右子树部分即可!!!

仔细观察中间下方的那棵树,我们每选取一个孩子结点,就将其余的孩子结点与父结点剪断(虚线),将选取的孩子结点与自己的兄弟结点相连(实线),最终实线连成的树就是我们需要转换的二叉树!!!


原文地址:https://www.cnblogs.com/zouhong/p/15352240.html