前言

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

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

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

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

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

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

🐋树与二叉树的区别

🌲性质不同

树：树是一种数据结构。

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

🌲结点不同

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

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

🌲种类不同

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

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

🐋树与森林

🌲转换概述

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

🌲树转换成二叉树

树转换成二叉树可归纳3步骤：加线、删线、旋转

加线：将树中所有相邻的 兄弟之间 加一条连线。

删线：对树中的每一个结点，只保留它与第1个孩子结点之间的连线，删去它与其他孩子结点之间的连线。

旋转：以树的根结点为轴心，将树平面顺时针旋转一定角度并做适当的调整，使得转化后所得二叉树看起来比较规整。

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

🌲二叉树转换成树

二叉树转换成树是树转换二叉树的逆过程。

树转换成二叉树可归纳3步骤：加线、删线、旋转

加线：若某结点是双亲结点的左孩子，则将该结点沿着右分支向下的所有结点与该结点的双亲结点用线连接。

删除：将树中所有双亲结点与右孩子结点的连线删除。

旋转：对经过（1）、（2）粮补后所得的树以根结点为轴心，按逆时针方向旋转一定的角度，并做适当调整，使得转化后所得的树看起来比较规整。

🌲森林与二叉树互转

森林是由若干树组成，任何一棵树和树对应的二叉树其右子树一定是空的。

根据这个规律可以得到森林转化成二叉树的方法：

将森林中每棵树转化成二叉树。

按照森林的先后顺序，将一颗二叉树视为前一棵二叉树的右子树依次连接起来，从而构成一颗二叉树

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

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

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