几种复杂数据结构的转换分析
2014-10-29王钢
摘 要
结合概念，运用动态图形，用通俗的语言对三种数据结构的进行转换分析，即：二叉树与树和森林的相互转换；图的最小生成树的画法；二叉排序树转换成平衡二叉树。
【关键词】数据结构 二叉树、树和森林 最小生成树 平衡二叉树 转换
1 引言
《数据结构》是计算机专业的一门专业基础课程，同时又是一门抽象性较强的课程，很多初学者都感到难以掌握，特别是对于几种复杂数据结构的转换，更是感到难以下手。笔者在总结了多年的教学实践，在本文中提出几种复杂数据结构的转换方法，希望能对研究这方面问题的读者有所帮助。
2 二叉树与树和森林的相互转换
要确实掌握这一转换技巧，首先必须搞清这样几个概念：
2.1 二叉树与树和森林的转换方式
二叉树与树和森林的转换其实只有两种：
（1）二叉树转换成树或森林。
（2）森林或树转换成二叉树。
也就是说，树和森林其实是一个概念，不是树，就是森林，那种认为这一题目可能有六种转换的思路是错误的。如图2.1所示。
2.2 二叉树与树和森林的转换分析
二叉树与树和森林之所以能够相互转换，是因为它们都可以用孩子兄弟表示法或称二叉链表表示法作为存储结构，从物理结构上看，它们的二叉链表是相同的，只是解释不同而已，这一点可参考有关教科书。
转换技巧：
必须深刻理解孩子兄弟表示法这一概念，在此举例说明：
对于图2.1 a的树对应唯一的一棵二叉树：
（1）二叉树的根结点为A，树最左边的第一个孩子B作为A的左子树根结点，由于A没有兄弟，则右子树为空（图2.1 b）；
（2）B结点无孩子，则左子树为空，右边的第一个兄弟为C，则右子树为C（图2.1 c）
（3）C结点有一个孩子D，则左子树为D，右边的第一个兄弟为E，则右子树为E，E结点既无孩子又无兄弟，则转换完成（图2.1 d）。
反之，若将图2.1 d的二叉树转换为树，则应采取以下方法：
（1）A为树的根结点，左子树B作为A的孩子（左孩子）；
（2）B结点左子树为空，说明B结点无孩子，右子树为C是B的兄弟（右兄弟），B的兄弟必为A的孩子，C与A连接；
（3）C的左子树为D是C的孩子（左孩子），右子树E是C的兄弟，C的兄弟也是A的孩子，D和E左、右子树均为空，说明它们既无兄弟，又无孩子，转换完成。
森林与二叉树的相互转换，在此以图例说明（如图2.2所示）。
图2.2 b： A为根结点，左孩子为B，右兄弟E。
图2.2 c： B结点无孩子，左子树为空，但有两个兄弟C、D。
E结点有一个孩子F为左子树，有一个兄弟G为右子树。
图2.2 d： G结点有一个孩子H为左子树，右边无兄弟，右子树为空。
H结点无孩子，左子树为空，但有一兄弟I，右子树为I。
I结点有一孩子J为其左子树结点，右边无兄弟，则右子树为空。
J结点既无孩子又无兄弟，转换完成。
显然，对于二叉树来说，如果根结点无右子树，则只能转换为树，否则必转换为森林，反之，森林转换成的二叉树必有右子树，树转换成的二叉树必无右子树。
为了加深掌握这一 方法，再举如下几个图例（如图2.3所示）。
可见，无论怎样转换，根和长子（左边第一个孩子）是不变的，关键是摆正右子树的位置，在二叉树转换成树或森林的过程中，右子树是结点的兄弟，既然是兄弟大家就应放在同
一位置上（即同是某一结点的孩子）；在森林或树转换成二叉树的过程中，某一结点的兄弟应放在该结点的右子树上（右兄弟），这一点初学者必须搞清楚。
3 排序二叉树转换成平衡二叉树
由于在构造二叉排序树的同时转换为平衡二叉树用到的概念较多，要掌握此方法，除了确实掌握平衡二叉树（即AVL树）的概念和四种基本型的转换方法外，笔者再强调以下概念：
（1） *a ：由于插入结点而使平衡因子绝对值大于1的离插入结点最近的祖先结点；
（2） 最小不平衡子树：*a与插入方向上离*a最近的的两个结点构成最小不平衡子树，
显然最小不平衡子树属于四种基本型；
（3） 二叉排序树因插入结点失去平衡时，只需对最小不平衡子树进行旋转处理，旋转后，其它结点放在相应的位置上即可。
在此只举一个实际的例子予以说明：
假设关键字序列为（12，24，37，53，45，93），试画出动态构造此关键字序列的平衡二叉树（如图4.1所示）。
这种找到*a和最小不平衡子树后仅对最小不平衡子树（都是基本型）进行旋转，其它结点放到相应的正确位置上的方法对于一般的情况是完全适用的，而且容易掌握，正确性能够得到保证。
4 结语
由于数据结构及其算法的抽象性和动态性，本文在说明以上几种转换技巧时使用了大量的动态图例，实际上，熟练掌握这些方法后，不必画出中间过程，可根据题目直接得到结果。如果本文能够对解这些题目的读者有所帮助，那将是笔者莫大的荣幸。不当之处，还望批评指正。
参考文献
[1]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，1997.
[2]许卓群等.数据结构[M].北京：高等教育出版社，1995.
[3]唐策善等.数据结构——用C语言描述[M].北京：高等教育出版社，1995.
[4] 徐红.数据结构（C语言版）[M].北京：清华大学出版社，2005.
作者简介
王钢（1964-），男，硕士学位。现为威海职业学院信息工程系副教授，主要从事C语言、数据结构、计算机图形学的教学工作。
作者单位
威海职业学院 山东省威海市 264210endprint
摘 要
结合概念，运用动态图形，用通俗的语言对三种数据结构的进行转换分析，即：二叉树与树和森林的相互转换；图的最小生成树的画法；二叉排序树转换成平衡二叉树。
【关键词】数据结构 二叉树、树和森林 最小生成树 平衡二叉树 转换
1 引言
《数据结构》是计算机专业的一门专业基础课程，同时又是一门抽象性较强的课程，很多初学者都感到难以掌握，特别是对于几种复杂数据结构的转换，更是感到难以下手。笔者在总结了多年的教学实践，在本文中提出几种复杂数据结构的转换方法，希望能对研究这方面问题的读者有所帮助。
2 二叉树与树和森林的相互转换
要确实掌握这一转换技巧，首先必须搞清这样几个概念：
2.1 二叉树与树和森林的转换方式
二叉树与树和森林的转换其实只有两种：
（1）二叉树转换成树或森林。
（2）森林或树转换成二叉树。
也就是说，树和森林其实是一个概念，不是树，就是森林，那种认为这一题目可能有六种转换的思路是错误的。如图2.1所示。
2.2 二叉树与树和森林的转换分析
二叉树与树和森林之所以能够相互转换，是因为它们都可以用孩子兄弟表示法或称二叉链表表示法作为存储结构，从物理结构上看，它们的二叉链表是相同的，只是解释不同而已，这一点可参考有关教科书。
转换技巧：
必须深刻理解孩子兄弟表示法这一概念，在此举例说明：
对于图2.1 a的树对应唯一的一棵二叉树：
（1）二叉树的根结点为A，树最左边的第一个孩子B作为A的左子树根结点，由于A没有兄弟，则右子树为空（图2.1 b）；
（2）B结点无孩子，则左子树为空，右边的第一个兄弟为C，则右子树为C（图2.1 c）
（3）C结点有一个孩子D，则左子树为D，右边的第一个兄弟为E，则右子树为E，E结点既无孩子又无兄弟，则转换完成（图2.1 d）。
反之，若将图2.1 d的二叉树转换为树，则应采取以下方法：
（1）A为树的根结点，左子树B作为A的孩子（左孩子）；
（2）B结点左子树为空，说明B结点无孩子，右子树为C是B的兄弟（右兄弟），B的兄弟必为A的孩子，C与A连接；
（3）C的左子树为D是C的孩子（左孩子），右子树E是C的兄弟，C的兄弟也是A的孩子，D和E左、右子树均为空，说明它们既无兄弟，又无孩子，转换完成。
森林与二叉树的相互转换，在此以图例说明（如图2.2所示）。
图2.2 b： A为根结点，左孩子为B，右兄弟E。
图2.2 c： B结点无孩子，左子树为空，但有两个兄弟C、D。
E结点有一个孩子F为左子树，有一个兄弟G为右子树。
图2.2 d： G结点有一个孩子H为左子树，右边无兄弟，右子树为空。
H结点无孩子，左子树为空，但有一兄弟I，右子树为I。
I结点有一孩子J为其左子树结点，右边无兄弟，则右子树为空。
J结点既无孩子又无兄弟，转换完成。
显然，对于二叉树来说，如果根结点无右子树，则只能转换为树，否则必转换为森林，反之，森林转换成的二叉树必有右子树，树转换成的二叉树必无右子树。
为了加深掌握这一 方法，再举如下几个图例（如图2.3所示）。
可见，无论怎样转换，根和长子（左边第一个孩子）是不变的，关键是摆正右子树的位置，在二叉树转换成树或森林的过程中，右子树是结点的兄弟，既然是兄弟大家就应放在同
一位置上（即同是某一结点的孩子）；在森林或树转换成二叉树的过程中，某一结点的兄弟应放在该结点的右子树上（右兄弟），这一点初学者必须搞清楚。
3 排序二叉树转换成平衡二叉树
由于在构造二叉排序树的同时转换为平衡二叉树用到的概念较多，要掌握此方法，除了确实掌握平衡二叉树（即AVL树）的概念和四种基本型的转换方法外，笔者再强调以下概念：
（1） *a ：由于插入结点而使平衡因子绝对值大于1的离插入结点最近的祖先结点；
（2） 最小不平衡子树：*a与插入方向上离*a最近的的两个结点构成最小不平衡子树，
显然最小不平衡子树属于四种基本型；
（3） 二叉排序树因插入结点失去平衡时，只需对最小不平衡子树进行旋转处理，旋转后，其它结点放在相应的位置上即可。
在此只举一个实际的例子予以说明：
假设关键字序列为（12，24，37，53，45，93），试画出动态构造此关键字序列的平衡二叉树（如图4.1所示）。
这种找到*a和最小不平衡子树后仅对最小不平衡子树（都是基本型）进行旋转，其它结点放到相应的正确位置上的方法对于一般的情况是完全适用的，而且容易掌握，正确性能够得到保证。
4 结语
由于数据结构及其算法的抽象性和动态性，本文在说明以上几种转换技巧时使用了大量的动态图例，实际上，熟练掌握这些方法后，不必画出中间过程，可根据题目直接得到结果。如果本文能够对解这些题目的读者有所帮助，那将是笔者莫大的荣幸。不当之处，还望批评指正。
参考文献
[1]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，1997.
[2]许卓群等.数据结构[M].北京：高等教育出版社，1995.
[3]唐策善等.数据结构——用C语言描述[M].北京：高等教育出版社，1995.
[4] 徐红.数据结构（C语言版）[M].北京：清华大学出版社，2005.
作者简介
王钢（1964-），男，硕士学位。现为威海职业学院信息工程系副教授，主要从事C语言、数据结构、计算机图形学的教学工作。
作者单位
威海职业学院 山东省威海市 264210endprint
摘 要
结合概念，运用动态图形，用通俗的语言对三种数据结构的进行转换分析，即：二叉树与树和森林的相互转换；图的最小生成树的画法；二叉排序树转换成平衡二叉树。
【关键词】数据结构 二叉树、树和森林 最小生成树 平衡二叉树 转换
1 引言
《数据结构》是计算机专业的一门专业基础课程，同时又是一门抽象性较强的课程，很多初学者都感到难以掌握，特别是对于几种复杂数据结构的转换，更是感到难以下手。笔者在总结了多年的教学实践，在本文中提出几种复杂数据结构的转换方法，希望能对研究这方面问题的读者有所帮助。
2 二叉树与树和森林的相互转换
要确实掌握这一转换技巧，首先必须搞清这样几个概念：
2.1 二叉树与树和森林的转换方式
二叉树与树和森林的转换其实只有两种：
（1）二叉树转换成树或森林。
（2）森林或树转换成二叉树。
也就是说，树和森林其实是一个概念，不是树，就是森林，那种认为这一题目可能有六种转换的思路是错误的。如图2.1所示。
2.2 二叉树与树和森林的转换分析
二叉树与树和森林之所以能够相互转换，是因为它们都可以用孩子兄弟表示法或称二叉链表表示法作为存储结构，从物理结构上看，它们的二叉链表是相同的，只是解释不同而已，这一点可参考有关教科书。
转换技巧：
必须深刻理解孩子兄弟表示法这一概念，在此举例说明：
对于图2.1 a的树对应唯一的一棵二叉树：
（1）二叉树的根结点为A，树最左边的第一个孩子B作为A的左子树根结点，由于A没有兄弟，则右子树为空（图2.1 b）；
（2）B结点无孩子，则左子树为空，右边的第一个兄弟为C，则右子树为C（图2.1 c）
（3）C结点有一个孩子D，则左子树为D，右边的第一个兄弟为E，则右子树为E，E结点既无孩子又无兄弟，则转换完成（图2.1 d）。
反之，若将图2.1 d的二叉树转换为树，则应采取以下方法：
（1）A为树的根结点，左子树B作为A的孩子（左孩子）；
（2）B结点左子树为空，说明B结点无孩子，右子树为C是B的兄弟（右兄弟），B的兄弟必为A的孩子，C与A连接；
（3）C的左子树为D是C的孩子（左孩子），右子树E是C的兄弟，C的兄弟也是A的孩子，D和E左、右子树均为空，说明它们既无兄弟，又无孩子，转换完成。
森林与二叉树的相互转换，在此以图例说明（如图2.2所示）。
图2.2 b： A为根结点，左孩子为B，右兄弟E。
图2.2 c： B结点无孩子，左子树为空，但有两个兄弟C、D。
E结点有一个孩子F为左子树，有一个兄弟G为右子树。
图2.2 d： G结点有一个孩子H为左子树，右边无兄弟，右子树为空。
H结点无孩子，左子树为空，但有一兄弟I，右子树为I。
I结点有一孩子J为其左子树结点，右边无兄弟，则右子树为空。
J结点既无孩子又无兄弟，转换完成。
显然，对于二叉树来说，如果根结点无右子树，则只能转换为树，否则必转换为森林，反之，森林转换成的二叉树必有右子树，树转换成的二叉树必无右子树。
为了加深掌握这一 方法，再举如下几个图例（如图2.3所示）。
可见，无论怎样转换，根和长子（左边第一个孩子）是不变的，关键是摆正右子树的位置，在二叉树转换成树或森林的过程中，右子树是结点的兄弟，既然是兄弟大家就应放在同
一位置上（即同是某一结点的孩子）；在森林或树转换成二叉树的过程中，某一结点的兄弟应放在该结点的右子树上（右兄弟），这一点初学者必须搞清楚。
3 排序二叉树转换成平衡二叉树
由于在构造二叉排序树的同时转换为平衡二叉树用到的概念较多，要掌握此方法，除了确实掌握平衡二叉树（即AVL树）的概念和四种基本型的转换方法外，笔者再强调以下概念：
（1） *a ：由于插入结点而使平衡因子绝对值大于1的离插入结点最近的祖先结点；
（2） 最小不平衡子树：*a与插入方向上离*a最近的的两个结点构成最小不平衡子树，
显然最小不平衡子树属于四种基本型；
（3） 二叉排序树因插入结点失去平衡时，只需对最小不平衡子树进行旋转处理，旋转后，其它结点放在相应的位置上即可。
在此只举一个实际的例子予以说明：
假设关键字序列为（12，24，37，53，45，93），试画出动态构造此关键字序列的平衡二叉树（如图4.1所示）。
这种找到*a和最小不平衡子树后仅对最小不平衡子树（都是基本型）进行旋转，其它结点放到相应的正确位置上的方法对于一般的情况是完全适用的，而且容易掌握，正确性能够得到保证。
4 结语
由于数据结构及其算法的抽象性和动态性，本文在说明以上几种转换技巧时使用了大量的动态图例，实际上，熟练掌握这些方法后，不必画出中间过程，可根据题目直接得到结果。如果本文能够对解这些题目的读者有所帮助，那将是笔者莫大的荣幸。不当之处，还望批评指正。
参考文献
[1]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，1997.
[2]许卓群等.数据结构[M].北京：高等教育出版社，1995.
[3]唐策善等.数据结构——用C语言描述[M].北京：高等教育出版社，1995.
[4] 徐红.数据结构（C语言版）[M].北京：清华大学出版社，2005.
作者简介
王钢（1964-），男，硕士学位。现为威海职业学院信息工程系副教授，主要从事C语言、数据结构、计算机图形学的教学工作。
作者单位
威海职业学院 山东省威海市 264210endprint
