Question

二叉树转化为森林时每次分解都会少一条边

Answer 1

问：二叉树转化为森林时每次分解都会少一条边

答：在树这一块的数据结构中最重要的就是二叉树，但是对于我们大部分人来说二叉树的基础掌握还是ok的，但是有时候我们也会忽略了树于森林（本人就是忽略了），今天就在这里总结总结数、森林与二叉树的转换树转换成二叉树1.加线：在所有的兄弟结点之间加线2.去线：对树中的每一个结点，只保留它与第一个结点的连线，删除与其他孩子结点之间的连线3.层次调整：调整成一颗二叉树（第一个孩子是二叉树的左孩子，兄弟转换过来是它的右孩子）森林转换成二叉树1.转换：把每一棵树转换成二叉树2.连线：第一棵二叉树不变，从第二棵二叉树开始，依次将后一棵二叉树的根节点作为前一棵二叉树根节点的右孩子，用线连起来二叉树转换成树就是树转换成二叉树的逆过程1.加线：若某结点的左孩子结点存在，则将左孩子的n个右孩子结点与此结点连接在一起2.去线：删除二叉树中所有结点与其右孩子之间的连线3.层次调整在做这幅图的时候犯了一个错误：当时对比树转换成二叉树图中的1，你会发现H在右边当你把二叉树转换成图的时候你会发现图中2的H在左边（当时就纳闷为什么会这样）原因：看了几分钟发现树是没有左右结点的（概念弄混淆了）树 的 遍 历：先根遍历：ABEFGCHD 后根遍历：EFGBHCDA二叉树的遍历： 先序遍历 ABEFGCHD 中序遍历：EFGBHCDA结论：当以二叉链表作为树的存储结构，树的先根遍历和后根遍历完全可以借用二叉树的前序遍历和中序遍历的算法实现二叉树转换成森林判断二叉树转换成森林还是树：二叉树的根节点是否有右孩子，若有是森林，否则是树1.从根节点开始，若有右孩子，则把与右孩子结点的连线删除，再看分离后的二叉树，若还有右孩子连线继续删除，则到没有为止2.将分离的二叉树转换成树森林的遍历： 前序遍历：ABCDEFGHJI 后序遍历：BCDAFEJHIG二叉树的遍历：前序遍历：ABCDEFGHJI 中序遍历：BCDAFEJHIG结论：当以二叉链表作为森林的存储结构，森林的先序遍历和后序遍历完全可以借用二叉树的前序遍历和中序遍历的算法实现综上我们找到了对树和森林这种复杂问题的简单解决办法

问：我是问你二叉树转化为森林时每次分解都会少一条边 这句话对吗

答：这句话是对的