当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

一般树和二叉树的转换,森林一搬树的转换

发表于: 2014-04-07   作者:超超超哥2010   来源:转载   浏览:
摘要: 一般树和二叉树的转换: 就是将森林用二叉树的方式来存储,将所有节点都看成只有两个指针域的节点,son和next节点,son节点指向它的左边第一个节点,next指向它的兄弟节点。到此为止形成的就是一颗二叉树。 也可以通过以下方式来转换:首先将同一双亲的兄弟节点从左至右地连接起来,然后将双亲节点的孩子节点的分支中,除与长子节点的分值保留外,其他的全部去掉,最后将兄弟相连的横线旋转45°
一般树和二叉树的转换:
就是将森林用二叉树的方式来存储,将所有节点都看成只有两个指针域的节点,son和next节点,son节点指向它的左边第一个节点,next指向它的兄弟节点。到此为止形成的就是一颗二叉树。
也可以通过以下方式来转换:首先将同一双亲的兄弟节点从左至右地连接起来,然后将双亲节点的孩子节点的分支中,除与长子节点的分值保留外,其他的全部去掉,最后将兄弟相连的横线旋转45°

一般树转换成二叉树后,二叉树是没有右子树的,没有右子树的二叉树也可以转换成森林。

将森林转换成一颗一般树:首先将每棵树都转化成对应的二叉树表示,然后从转化后的树中任选一棵树,作为森林转化为一般树的根,最后,在剩下的树中再任选一棵树,将其根与上一棵树相连,作为上一棵树的右孩子,重复这一步,知道所有的树都连在一起。

一般树的遍历:
①前序遍历:
  访问树的根节点
  遍历第一课子树
  从左到右遍历其余的子树
②后序遍历:
  遍历第一颗子树
  从左到右遍历其余子树
  最后访问根节点

一般树和转换成二叉树之后的一般树的遍历的对应结果:

  一般树            对应的二叉树
    前序               前序
    后序               中序

所以当以二叉链式方式存储一颗一般树时,这颗一般树的前序遍历和后序遍历可以借用相应的二叉树的前序和和中序遍历算法来实现。


一般树二叉链存储方式下层次遍历:
说道按层次遍历,那就肯定得用到队列,前序,后序中序就得用到栈:
当一个节点被访问的同时,还要检查该节点有无左子树,如果非空即表示该节点有下一层,这颗左子树的根就是下一层节点中的最左孩子。将这颗左子树的根进队,然后,继续访问右单支所有节点,并对访问的节点做左子树检查和相应的操作。当一个右单支上的左右节点全部被访问后,就从队列中出队一个节点的指针,该指针正好是下一层中最左的一个节点。再从该出队节点开始,像右单支访问,并重复以上的整个过程。

一般树和二叉树的转换,森林一搬树的转换

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
树、森林与二叉树的转换 1、树转换为二叉树 由于二叉树是有序的,为了避免混淆,对于无序树,我们约
天气太热,只能蜗在宿舍。在收拾邮箱的时候无意间看到了数据结构Z老师发的09年研究生入学计算机统考
一、树转换为二叉树: 1. 加线:所有兄弟节点之间加线 2. 去线:保留树中每个结点与它第一个孩子(左
1、基本术语: 度:有两种度“结点的度”与“树的度”。结点的度指的是一个结点子树的个数;树的度是
1 前言 这篇文章主要介绍了线索二叉树,树,森林与二叉树的转换以及赫夫曼树的相关内容。 转载请注
1 前言 这篇文章主要介绍了线索二叉树,树,森林与二叉树的转换以及赫夫曼树的相关内容。 转载请注
1、树转换为二叉树 由于二叉树是有序的,为了避免混淆,对于无序树,我们约定树中的每个结点的孩子
是什么 树是n个结点的有限集合,树的定义是递归的,表明了树本身的固有特性,也就是一棵树由若干棵
平衡二叉树:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平
一、树的遍历 1、先根(次序)遍历树 先访问树的根节点,然后依次先根遍历根的每棵子树 2、后根(次
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号