数据结构——树、森林和二叉树的转换

在介绍树的存储结构时,就说到了树的孩子兄弟表示法可以将一棵树用二叉链表进行存储,所以借助二叉链表,树和二叉树可以互相转换。从物理结构上来看,它们的二叉链表也是相同的,只是介绍不太一样而已。因此,只要我们设定一定的规则,用二叉树来表示树,甚至表示森林都是可以的,森林和二叉树也可以互相进行转换。

树转换为二叉树

将树转换为二叉树的步骤如下:

  1. 加线:在所有的兄弟结点之间加一条连线;
  2. 去线:对树中的每个结点,只保留它与第一个孩子结点的连线,删除它与其他孩子结点之间的连线;
  3. 层次调整:以树的根结点为轴心,将整棵树顺时针旋转一定角度,使之结构层次分明。注意第一个孩子是二叉树结点的左孩子,兄弟转换过来的孩子是结点的右孩子。

森林转换为二叉树

森林是由若干棵树组成的,所以可以完全理解为,森林中的每一棵树都是兄弟,可以按照兄弟的处理办法来操作。步骤不如:

  1. 把每棵树转换为二叉树;
  2. 第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一刻二叉树的根结点的右孩子,用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。

二叉树转换为树

二叉树转换为树是树转换为二叉树的逆过程,也就是反过来做而已。

  1. 加线:若某结点的左孩子结点存在,则将这个左孩子的右孩子结点、右孩子的右孩子结点…就是左孩子的n个右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来;
  2. 去线:删除原二叉树中所有结点与其右孩子结点连线;
  3. 层次调整:使之结构层次分明。

二叉树转换为森林

判断一棵二叉树能够转换为一棵树还是森林,标准很简单,那就是只要看这棵二叉树的根结点有没有右孩子,有的就是森林,没有的就是一棵树。二叉树转换为森林步骤如下:

  1. 从根结点开始,若右孩子存在,则把与右孩子结点的连线删除,再查看分离后的二叉树,若右孩子存在,则连线删除…直到所有右孩子连线都删除为止,得到分离的二叉树;
  2. 再将每一个二叉树转换为树即可。

树、森林看似复杂,其实它们都可以转换为二叉树来处理,我们研究了树、森林和二叉树的互相转换的办法,这样就使得面对树和森林的数据结构时,编码实现称为了可能。

原文发布于微信公众号 - Android机动车(JsAndroidClub)

原文发表时间:2018-06-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习从入门到成神

数据结构之树、森林和二叉树的转换

树转换为二叉树 (1)加线。在所有兄弟结点之间加一条连线。 (2)去线。树中的每个结点,只保留它与第一个孩子结点的连线,删除它与其它孩子结点之间的连线。...

21320
来自专栏编程微刊

一个简易的选择小时(时分秒)的插件

32310
来自专栏编程理解

数据结构(一):二叉树

二叉树( binary tree )是有限节点集合构成的结构,其结构的递归定义为:

14920
来自专栏Android机动车

数据结构——二叉树的定义和性质

在一些电视节目中,会猜测商品价格,有的人是一点一点的数字累加,这样的策略效率太低了。其实有一种经典的折半查找算法,就类似于我们今天要说的二叉树。

13920
来自专栏C/C++基础

求二叉树的深度和宽度

题目: 输入一个二叉树的根节点,求该树的深度。从根节点到叶子节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度包含的节点数为为树的深度,即二...

26920
来自专栏青玉伏案

算法与数据结构(十一) 平衡二叉树(AVL树)(Swift版)

今天的博客是在上一篇博客的基础上进行的延伸。上一篇博客我们主要聊了二叉排序树,详情请戳《二叉排序树的查找、插入与删除》。本篇博客我们就在二叉排序树的基础上来聊聊...

28370
来自专栏小文博客

小文’s blog — 平衡二叉树构造方法

11530
来自专栏软件开发 -- 分享 互助 成长

二叉排序树和平衡二叉树

二叉排序树又称二叉查找树或二叉搜索树。 它一棵空树或者是具有下列性质: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,...

224100
来自专栏郭耀华‘s Blog

数据结构二叉树知识点总结

术语  1. 节点的度:一个节点含有的子树的个数称为该节点的度; 2. 叶节点或终端节点:度为零的节点;  3. 非终端节点或分支节点:度不为零的节点;  4....

340130
来自专栏WD学习记录

哈夫曼树(Huffman Tree)

给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带...

25140

扫码关注云+社区

领取腾讯云代金券