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

文档中心

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

       【安利Java零基础】

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

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

前言

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

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

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

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

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

💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 💚💙 💜

🐋树与二叉树的区别

🌲性质不同

树：树是一种数据结构。

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

🌲结点不同

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

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

🌲种类不同

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

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

🐋树与森林

🌲转换概述

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

🌲树转换成二叉树

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

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

🌲二叉树转换成树

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

🌲森林与二叉树互转

森林是由若干树组成，任何一棵树和树对应的二叉树其右子树一定是空的。
根据这个规律可以得到森林转化成二叉树的方法：
1. 将森林中每棵树转化成二叉树。
2. 按照森林的先后顺序，将一颗二叉树视为前一棵二叉树的右子树依次连接起来，从而构成一颗二叉树

将二叉树转化成森林正好是这个过程相反。

💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 💚💙 💜

🌲树、二叉树、森林互转关系图

如果文章对您有帮助，就拿起小手赶紧给博主点赞💚评论❤️收藏💙 一下吧！

想要了解更多吗？没时间解释了，快来点一点！

路遥叶子的博客_CSDN博客-数据结构,安利Java零基础,spring领域博主https://blog.csdn.net/zsy3757486?spm=1000.2115.3001.5343

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

目录

🐋树与二叉树的区别

🐋树与森林

前言