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

前言

介绍

🍃数据结构专区：数据结构

参考

该部分知识参考于《数据结构（C语言版第2版）》129~130页

🌈每一个清晨，都是世界对你说的最温柔的早安：ૢ(≧▽≦)و✨

前言

1、基础知识

2、树转换为二叉树

2.1 方法介绍：

2.2 演示

3、森林转换为二叉树

3.1 方法介绍：

3.2 演示

4、二叉树转换为树或森林

4.1 方法介绍：

4.2 演示

结语

1、基础知识

树的定义：树是 n（n≥0）个结点的有限集合。当 n＝0 时，称为空树；任意一棵非空树满足以下条件：

⑴ 有且仅有一个特定的称为根的结点；

⑵ 当 n＞1 时，除根结点之外的其余结点被分成 m（m>0）个互不相交的有限集合 T1，T2，…，Tm，其中每个集合又是一棵树，并称为这个根结点的子树。

二叉树的定义：二叉树是 n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

森林的定义：森林是 m（m≥0）棵互不相交的树的有限集合。该集合或者为空集（称为空森林），或者由 m 棵互不相交的树组成，其中每棵树本身又是一棵二叉树。

2、树转换为二叉树

2.1 方法介绍：

⑴ 加线——树中所有相邻兄弟结点之间加一条连线；

⑵ 去线——对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线；

⑶ 层次调整——以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。

2.2 演示

~~首先这是一棵树~~

~~开始第一步，加线~~

~~随后进行第二步，删线~~

~~最后调整即可~~

3、森林转换为二叉树

3.1 方法介绍：

⑴ 将森林中的每棵树转换成二叉树；

⑵ 从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，所得到的二叉树就是由森林转换的二叉树。

3.2 演示

~~这是一片森林~~

~~首先将每棵树都转换为二叉树~~

~~随后，从第二棵二叉树开始，将后一棵树的根节点，作为前一棵树的根节点的右孩子~~

4、二叉树转换为树或森林

4.1 方法介绍：

⑴ 加线——若某结点 x 是其双亲 y 的左孩子，则把结点 x 的右孩子、右孩子的右孩子、……，都与结点 y 用线连起来；

⑵ 去线——删去原二叉树中所有的双亲结点与右孩子结点的连线；

⑶ 层次调整——整理由⑴、⑵两步所得到的树或森林，使之层次分明。树的遍历序列与二叉树的遍历序列之间的对应关系