开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【数据结构】树、二叉树、森林间的互转 -> 正文阅读

[数据结构与算法]【数据结构】树、二叉树、森林间的互转

💟作者简介：大家好呀！我是路遥叶子，大家可以叫我叶子哦！???? ?
📝个人主页：【路遥叶子的博客】
🏆博主信息：四季轮换叶，一路招摇胜！
??????? 专栏

?????? 【安利Java零基础】

?????? 【数据结构-Java语言描述】

🐋希望大家多多支持😘一起进步呀！~??
🌈若有帮助，还请【关注?点赞?收藏】，不行的话我再努力努力呀！💪
————————————————
?版权声明：本文由【路遥叶子】原创、在CSDN首发、需要转载请联系博主。
🍁想寻找共同成长的小伙伴，请点击【Java全栈开发社区】

?前言

说到树，你大脑里出现的第一个画面，是否是这样的呢！

?那说到森林，你大脑里出现的第一个画面，又是否是这样的呢！

?其实，树木与森林的关系是辩证统一的关系。

没有树木就没有森林，没有森林更谈不上树木，两者是相互依存，共同发展的命运共同体。

树型结构是一种重要的非线性数据结构。树型结构在客观世界广泛存在，如组织关系可用树来表示。树在计算机领域也有广泛应用，如在编译程序时，可用树来表示源程序的语法结构(语法树)。又如在数据库系统中，使用树型结构存储索引等信息。森林(Forest)是m(m≥0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此可以用森林和树的相互递归定义来描述树。对森林的研究，都是转化为对树的研究。

💙 💜 ?? 💚💙 💜 ?? 💚💙 💜 ?? 💚💙 💜 ??💙 💜 ?? 💚💙 💜 ?? 💚💙 💜 💚💙 💜

🐋树与二叉树的区别

🌲性质不同

树：树是一种数据结构。

二叉树：二叉树是每个结点最多有两个子树的一种树结构。

🌲结点不同

树：树的每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点。

二叉树：每个结点最多有两个子树。

🌲种类不同

树：树的种类包括无序树、有序树、二叉树和哈夫曼树等。

二叉树：二叉树的种类包括完全二叉树、满二叉树和平衡二叉树。

🐋树与森林

🌲转换概述

树与二叉树之间、森林与二叉树之间可以相互转换，而且这种转换是一一对应的。

🌲树转换成二叉树

树转换成二叉树可归纳3步骤：加线、删线、旋转
1. 加线：将树中所有相邻的 兄弟之间 加一条连线。
2. 删线：对树中的每一个结点，只保留它与第1个孩子结点之间的连线，删去它与其他孩子结点之间的连线。
3. 旋转：以树的根结点为轴心，将树平面顺时针旋转一定角度并做适当的调整，使得转化后所得二叉树看起来比较规整。

?由树转换成的二叉树永远是一棵根结点的右子树为空的二叉树。

🌲二叉树转换成树

二叉树转换成树是树转换二叉树的逆过程。
树转换成二叉树可归纳3步骤：加线、删线、旋转
1. 加线：若某结点是双亲结点的左孩子，则将该结点沿着右分支向下的所有结点与该结点的双亲结点用线连接。
2. 删除：将树中所有双亲结点与右孩子结点的连线删除。
3. 旋转：对经过（1）、（2）粮补后所得的树以根结点为轴心，按逆时针方向旋转一定的角度，并做适当调整，使得转化后所得的树看起来比较规整。