1、树转换为二叉树
由于二叉树是有序的,为了避免混淆,对于无序树,我们约定树中的每个结点的孩子结点按从左到右的顺序进行编号。
将树转换成二叉树的步骤是:
(1)加线。就是在所有兄弟结点之间加一条连线;
(2)抹线。就是对树中的每个结点,只保留他与第一个孩子结点之间的连线,删除它与其它孩子结点之间的连线;
(3)旋转。就是以树的根结点为轴心,将整棵树顺时针旋转一定角度,使之结构层次分明。
树转换为二叉树的过程示意图
2、森林转换为二叉树
森林是由若干棵树组成,可以将森林中的每棵树的根结点看作是兄弟,由于每棵树都可以转换为二叉树,所以森林也可以转换为二叉树。
将森林转换为二叉树的步骤是:
(1)先把每棵树转换为二叉树;
(2)第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点,用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。
森林转换为二叉树的转换过程示意图
3、二叉树转换为树
二叉树转换为树是树转换为二叉树的逆过程,其步骤是:
(1)若某结点的左孩子结点存在,将左孩子结点的右孩子结点、右孩子结点的右孩子结点……都作为该结点的孩子结点,将该结点与这些右孩子结点用线连接起来;
(2)删除原二叉树中所有结点与其右孩子结点的连线;
(3)整理(1)和(2)两步得到的树,使之结构层次分明。
二叉树转换为树的过程示意图
4、二叉树转换为森林
二叉树转换为森林比较简单,其步骤如下:
(1)先把每个结点与右孩子结点的连线删除,得到分离的二叉树;
(2)把分离后的每棵二叉树转换为树;
(3)整理第(2)步得到的树,使之规范,这样得到森林。
根据树与二叉树的转换关系以及二叉树的遍历定义可以推知,树的先序遍历与其转换的相应的二叉树的先序遍历的结果序列相同;树的后序遍历与其转换的二叉树的中序遍历的结果序列相同;树的层序遍历与其转换的二叉树的后序遍历的结果序列相同。由森林与二叉树的转换关系以及森林与二叉树的遍历定义可知,森林的先序遍历和中序遍历与所转换得到的二叉树的先序遍历和中序遍历的结果序列相同。
- 大小: 115 KB
- 大小: 92.9 KB
- 大小: 91.3 KB
分享到:
相关推荐
树与二叉树相互转化 树的前根遍历和后根遍历 源代码
树的存储结构、森林及与二叉树的转换树的存储结构、森林及与二叉树的转换
简单的实现了树与二叉树的转换功能!很实用
森林转换成二叉树c语言实现的数据结构算法
树与二叉树_习题树与二叉树_习题树与二叉树_习题
森林(树)的括号表示法←→森林(树)←→二叉树←→遍历序列 ↓ 遍历序列
递归方法实现、树与二叉树的转化及树的遍历
数据结构里面的树与二叉树和森林间的相互转化教程,有图有真相!!!很好理解的!
5.6 树、森林与二叉树的转换 1.树转换为二叉树 将一棵树转换为二叉树的方法为: (1)加线——树中所有相邻的兄弟结点之间加一条线; (2)去线——对树中的每个节点,只保留它与第一个孩子结点之间的连线,删去它与...
树与二叉树的详细算法,很全 以二叉树表示算术表达式 建立二叉树算法 以及一些习题
5.5 树、森林与二叉树的转换.doc5.5 树、森林与二叉树的转换.doc5.5 树、森林与二叉树的转换.doc
很好的一个课件,详细,基础的讲述了数据结构中最难理解的部分,帮助理解树与二叉树。。
详细的树和二叉树的教程,还附有源代码 部分代码如下: 二叉树头文件.h //二叉树的二叉链表存储表示 typedef struct BiTNode {TElemType data; //二叉树结点数据域 struct BiTNode *lchild,*rchild; //左右孩子指针...
数据结构树与二叉树数据结构树与二叉树数据结构树与二叉树
课程设计 二叉树的遍历及树与二叉树的转换 报告并能按照树的形式打印出来。
树和二叉树的实验报告
树和二叉树课件,主要内容有树的逻辑结构;树的存储结构;二叉树的逻辑结构;二叉树的存储结构及实现;树、森林与二叉树的转换;哈夫曼树
森林树和二叉树的转换PPT学习教案.pptx
6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树 6.4 线索二叉树 6.5 树和森林 6.6 哈夫曼树