哈喽!这里是一只派大鑫,不是派大星。本着基础不牢,地动山摇的学习态度,从基础的C语言语法讲到算法再到更高级的语法及框架的学习。更好地让同样热爱编程(或是应付期末考试 狗头.jpg)的大家能够在学习阶段找到好的方法、路线,让天下没有难学的程序(只有秃头的程序员 2333),学会程序和算法,走遍天下都不怕!

目录

引言

问题引出

转换过程

树—>二叉树

森林—>二叉树

二叉树—>树

二叉树—>森林

总结


引言

在数据结构的考试中,无论是本科期末考试还是考研,对树的考察一定是重点,其中对树和二叉树之间的转换也是热门考点,因为不涉及写代码,多数以画图或是选择题的形式出现,所以较为简单,但仍需认真学习。

本文对树、森林与二叉树之间的相互转换的过程和方法进行讲解,相信哪怕是小白的你,在看完文章后也能豁然开朗。

妈妈再也不担心我不会手写数据结构了

对于树、二叉树的介绍在本文不再进行重述,有需要的读者可以查看博主的上一篇关于二叉树详解的文章《数据结构C语言版》——二叉树详解(图文并茂)

问题引出

前面已经讲过了树的定义和存储结构,对树来说,在满足树的条件下可以是任意形状,一个结点可以有任意多个孩子,显然对树的处理要更复杂,去研究树的性质和算法就不太容易了。但是对于二叉树,尽管它也是树,但由于每个结点最多只能有左孩子和右孩子,面对的变化就少了很多。如果我们能把树转化为二叉树,那么就会方便很多。

转换过程

在树的存储结构那一讲中,提到了树的孩子兄弟表示法可以将一棵树用二叉链表进行存储,所以借助二叉链表,树和二叉树可以相互转换,同样的,森林也可以和二叉树相互转换。

树—>二叉树

假设我们的树是这样的。

将树转化为二叉树的步骤如下:

(1)加线。在所有兄弟结点之间加一条连线。如下所示。

(2)去线,对树中每个结点,只保留它与第一个孩子结点的连线,删除它与其他孩子结点之间的连线。如下所示。

(3)层次调整。以树的根结点为核心,将整棵树顺时针旋转一定的角度,使之层次分明。如下所示。

森林—>二叉树

假设森林是这样的。

将森林转化为二叉树的步骤如下:

(1)把每个树转换为二叉树。如下所示。

(2)第一棵二叉树不动,从第二棵二叉树开始,依次把后一颗二叉树的根结点作为前一颗二叉树的根结点的右孩子,用线链接起来。如下所示。

二叉树—>树

二叉树转换为树其实就是树转换为二叉树的逆过程,反过来做而已。

假设有这么一颗二叉树。

将二叉树转化为树的步骤如下:

(1)加线。若某结点的左孩子结点存在,则将这个左孩子的右孩子结点,右孩子的右孩子结点….(也就是将左孩子的n个右孩子结点都作为此节点的孩子)。将该结点与这些右孩子结点用线连接起来。如下所示。

(2)去线。删除原二叉树中所有结点与其右孩子结点的连线。如下所示。

(3)层次调整。使之结构层次分明。如下所示。

二叉树—>森林

判断一颗二叉树能够转换为一棵树还是森林很简单,如果这棵二叉树的根结点没有右孩子就是树,有右孩子就转化为森林。

假设有这么一颗二叉树。

将二叉树转化为森林的步骤如下:

(1)从根结点开始,若右孩子存在,则把与右孩子结点的连线删除。如下所示。

(2)再看分离后的二叉树,若右孩子存在,则连线删除…直到所有右孩子连线都被删除为止,得到分离的二叉树。如下所示。

(3)最后将分离的二叉树转换为树即可。如下所示。

总结

树、森林与二叉树之间的转换就是这样的,文、图给出的是详细过程,也是最基础的过程。

如果对“孩子兄弟”表示法比较熟悉的话,可以直接对其进行转换,也就是一个结点的第一个孩子变成该结点的左孩子,其他的孩子(即左孩子的兄弟)都依次连接在该结点的右边。

使用“孩子兄弟”表示法来进行转换省去加线、取线的过程,使转换更为直接。

知识学习完了不要忘记做一些练习题来巩固基础~~~