首页 > 其他分享 >树,森林与二叉树的转换复习

树,森林与二叉树的转换复习

时间:2023-01-20 17:12:28浏览次数:35  
标签:结点 遍历 转换 复习 访问 二叉树 森林

普通的树,结构太多,研究起来也很复杂。但是依据树的孩子兄弟表示法,可以将普通的树,转换为二叉树,就方便很多。

转换步骤:

1,加线:在所有兄弟之间连线

2,去线:对树中每个结点,只保留它与第一个孩子结点的连线,删除它与其他孩子结点之间的连线

3,层次调整:以树的根结点为轴心,将整棵树顺时针旋转一定的角度,使之结构分明。

 

森林转换二叉树步骤:

由于森林中的每棵树都是兄弟(同层次),可以按照兄弟的处理办法

1,将每棵树转化为二叉树

2,第一个二叉树不动,从第二棵二叉树开始,依次把后一颗二叉树的根结点作为,前一个二叉树的右孩子.

 

二叉树转换为树步骤:

即逆过程

1,加线

2,去线

 

二叉树转换为森林:

判断一棵二叉树能否转换成一颗树还是森林,那就是看根节点有没有右孩子,有为森林,无则为树。

再将每个分离的二叉树转换为树即可。

 

 

树和森林的遍历:

树:

1,先根遍历,先访问树的根结点,然后依次先根遍历每个子树。

2,后根遍历,先依次后跟遍历每个子树,再访问根结点。

森林:

1,前序遍历:先访问森林中的第一棵树的跟结点,而后再依次先根遍历每个子树,再依次访问每个树。

2,后序遍历:先访问森林中的第一棵树,再后根遍历的方式遍历每棵子树,然后再访问根结点,再依次访问每一棵树。

 

森林的前序遍历和二叉树的前序遍历结果相同,森林的后序遍历和二叉树的中序遍历结果相同。

标签:结点,遍历,转换,复习,访问,二叉树,森林
From: https://www.cnblogs.com/abwork-space/p/17062897.html

相关文章

  • 线索二叉树
    线索二叉树的实现内涵,一棵n个结点的树中一定会存在n+1个空指针域,将此指针域给利用起来,实现指向前驱或后继。其线索二叉树,等于把一颗二叉树转化为一个双向链表。对二叉树......
  • 二叉树的最大宽度--google面试遇到过,他是要求求解所有路径path
    543.二叉树的直径难度简单1221收藏分享切换为英文接收动态反馈给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。......
  • 【DFS】LeetCode 951. 翻转等价二叉树
    题目链接951.翻转等价二叉树思路如果二叉树root1,root2根节点值相等,那么只需要检查他们的孩子是不是相等就可以了。如果root1或者root2是null,那么只有在他们都......
  • instanceof和类型转换
    1.instanceof:判断类型是否相似2.System.out.println(XinstanceofY);//能不能编译通过!取决于X和Y直接是否存在父子关系,有父子关系编译通过,无父子关系编译报错。X指......
  • 【DFS】LeetCode 101. 对称二叉树
    题目链接101.对称二叉树思路DFS递归解决代码classSolution{publicbooleanisSymmetric(TreeNoderoot){if(root==null){returnt......
  • 算法刷题 Day 20 | 654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二
    今日内容最大二叉树合并二叉树二叉搜索树中的搜索验证二叉搜索树详细布置654.最大二叉树又是构造二叉树,昨天大家刚刚做完中序后序确定二叉树,今天做这......
  • 【DFS】LeetCode 226. 翻转二叉树
    题目链接226.翻转二叉树思路将左右子树抽象为两个结点,直接进行交换。然后再递归左右子树。代码classSolution{publicTreeNodeinvertTree(TreeNoderoot){......
  • sql server CONVERT(VARCHAR(7),'2023-01-07 18:34:53.690',120)转换
    convert语法:sqlCONVERT(data_type[(length)],expression[,style])data_type目标数据的数据类型,包括xml,bigint,sql_variant。不能使用别名数据类型。......
  • 人民币大写转换
    CREATEORREPLACEFUNCTIONnum2rmb(jeNUMBER)RETURNVARCHAR2ISresultvarchar2(100);ipls_integer;snumvarchar2(20):=ltrim(replace(to_char(abs(je),'9999999......
  • 北邮工程硕士_数据库系统设计_考试复习答案
    考试范围:第一章第二章第三章第四章SQL 复习题1.      试述数据管理的发展阶段。手工管理阶段(50年代中期以前)文件系统阶段(50年代末-60年代末)数据库系统阶段(60年......