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

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

森林转换为二叉树 (1)把每棵树转换为二叉树。 (2)第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子,用线连接起来。

二叉树转换为树 是树转换为二叉树的逆过程。 (1)加线。若某结点X的左孩子结点存在,则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点…,都作为结点X的孩子。将结点X与这些右孩子结点用线连接起来。 (2)去线。删除原二叉树中所有结点与其右孩子结点的连线。 (3)层次调整。

二叉树转换为森林 假如一棵二叉树的根节点有右孩子,则这棵二叉树能够转换为森林,否则将转换为一棵树。 (1)从根节点开始,若右孩子存在,则把与右孩子结点的连线删除。再查看分离后的二叉树,若其根节点的右孩子存在,则连线删除…。直到所有这些根节点与右孩子的连线都删除为止。 (2)将每棵分离后的二叉树转换为树。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

二叉树性质

•【性质1】在二叉树的第i层上最多有2i-1个结点(i>=1)。 【性质2】深度为k的二叉树至多有2k –1个结点(k>=1)。 •【特别】一棵深度为k且有2k...

26960
来自专栏菩提树下的杨过

spring-boot 速成(12) - 如何注入多个redis StringRedisTemplate

默认情况下,spring-boot的redis自动配置,只能注册一个StringRedisTemplate实例,如果希望注入多个,比如:1个读写database...

1K100
来自专栏编程微刊

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

32310
来自专栏编程理解

数据结构(四):平衡二叉树(AVL树)

。影响时间复杂度的因素即为二叉树的高,为了尽量避免树中每层上只有一个节点的情况,这里引入平衡二叉树。

68130
来自专栏lgp20151222

解决Spring Boot 使用RedisTemplate 存储键值出现乱码 \xac\xed\x00\x05t\x00

spring-data-redis的RedisTemplate<K, V>模板类在操作redis时默认使用JdkSerializationRedisSerial...

85910
来自专栏用户画像

4.5.2 平衡二叉树

为了避免树的高度增长过快,降低二叉排序树的性能,我们规定在插入和删除二叉树结点时,要保证任意结点的左、右子树高度差的绝对值不超过1,将这样的二叉树称为平衡二叉树...

9220
来自专栏小文博客

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

11530
来自专栏郭耀华‘s Blog

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

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

340130
来自专栏郭耀华‘s Blog

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

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

二叉排序树和平衡二叉树

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

224100

扫码关注云+社区

领取腾讯云代金券