普通的树,结构太多,研究起来也很复杂。但是依据树的孩子兄弟表示法,可以将普通的树,转换为二叉树,就方便很多。
转换步骤:
1,加线:在所有兄弟之间连线
2,去线:对树中每个结点,只保留它与第一个孩子结点的连线,删除它与其他孩子结点之间的连线
3,层次调整:以树的根结点为轴心,将整棵树顺时针旋转一定的角度,使之结构分明。
森林转换二叉树步骤:
由于森林中的每棵树都是兄弟(同层次),可以按照兄弟的处理办法
1,将每棵树转化为二叉树
2,第一个二叉树不动,从第二棵二叉树开始,依次把后一颗二叉树的根结点作为,前一个二叉树的右孩子.
二叉树转换为树步骤:
即逆过程
1,加线
2,去线
二叉树转换为森林:
判断一棵二叉树能否转换成一颗树还是森林,那就是看根节点有没有右孩子,有为森林,无则为树。
再将每个分离的二叉树转换为树即可。
树和森林的遍历:
树:
1,先根遍历,先访问树的根结点,然后依次先根遍历每个子树。
2,后根遍历,先依次后跟遍历每个子树,再访问根结点。
森林:
1,前序遍历:先访问森林中的第一棵树的跟结点,而后再依次先根遍历每个子树,再依次访问每个树。
2,后序遍历:先访问森林中的第一棵树,再后根遍历的方式遍历每棵子树,然后再访问根结点,再依次访问每一棵树。
森林的前序遍历和二叉树的前序遍历结果相同,森林的后序遍历和二叉树的中序遍历结果相同。
标签:结点,遍历,转换,复习,访问,二叉树,森林 From: https://www.cnblogs.com/abwork-space/p/17062897.html