幾種復雜數據結構的轉換分析

摘 要

結合概念，運用動態圖形，用通俗的語言對三種數據結構的進行轉換分析，即：二叉樹與樹和森林的相互轉換；圖的最小生成樹的畫法；二叉排序樹轉換成平衡二叉樹。

【關鍵詞】數據結構 二叉樹、樹和森林 最小生成樹 平衡二叉樹 轉換

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