摘 要

結(jié)合概念，運用動態(tài)圖形，用通俗的語言對三種數(shù)據(jù)結(jié)構(gòu)的進行轉(zhuǎn)換分析，即：二叉樹與樹和森林的相互轉(zhuǎn)換；圖的最小生成樹的畫法；二叉排序樹轉(zhuǎn)換成平衡二叉樹。

【關(guān)鍵詞】數(shù)據(jù)結(jié)構(gòu) 二叉樹、樹和森林 最小生成樹 平衡二叉樹 轉(zhuǎn)換

1 引言

《數(shù)據(jù)結(jié)構(gòu)》是計算機專業(yè)的一門專業(yè)基礎課程，同時又是一門抽象性較強的課程，很多初學者都感到難以掌握，特別是對于幾種復雜數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換，更是感到難以下手。筆者在總結(jié)了多年的教學實踐，在本文中提出幾種復雜數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換方法，希望能對研究這方面問題的讀者有所幫助。

2 二叉樹與樹和森林的相互轉(zhuǎn)換

要確實掌握這一轉(zhuǎn)換技巧，首先必須搞清這樣幾個概念：

2.1 二叉樹與樹和森林的轉(zhuǎn)換方式

二叉樹與樹和森林的轉(zhuǎn)換其實只有兩種：

（1）二叉樹轉(zhuǎn)換成樹或森林。

（2）森林或樹轉(zhuǎn)換成二叉樹。

也就是說，樹和森林其實是一個概念，不是樹，就是森林，那種認為這一題目可能有六種轉(zhuǎn)換的思路是錯誤的。如圖2.1所示。

2.2 二叉樹與樹和森林的轉(zhuǎn)換分析

二叉樹與樹和森林之所以能夠相互轉(zhuǎn)換，是因為它們都可以用孩子兄弟表示法或稱二叉鏈表表示法作為存儲結(jié)構(gòu)，從物理結(jié)構(gòu)上看，它們的二叉鏈表是相同的，只是解釋不同而已，這一點可參考有關(guān)教科書。

轉(zhuǎn)換技巧：

必須深刻理解孩子兄弟表示法這一概念，在此舉例說明：

對于圖2.1 a的樹對應唯一的一棵二叉樹：

（1）二叉樹的根結(jié)點為A，樹最左邊的第一個孩子B作為A的左子樹根結(jié)點，由于A沒有兄弟，則右子樹為空（圖2.1 b）；

（2）B結(jié)點無孩子，則左子樹為空，右邊的第一個兄弟為C，則右子樹為C（圖2.1 c）

（3）C結(jié)點有一個孩子D，則左子樹為D，右邊的第一個兄弟為E，則右子樹為E，E結(jié)點既無孩子又無兄弟，則轉(zhuǎn)換完成（圖2.1 d）。

反之，若將圖2.1 d的二叉樹轉(zhuǎn)換為樹，則應采取以下方法：

（1）A為樹的根結(jié)點，左子樹B作為A的孩子（左孩子）；

（2）B結(jié)點左子樹為空，說明B結(jié)點無孩子，右子樹為C是B的兄弟（右兄弟），B的兄弟必為A的孩子，C與A連接；

（3）C的左子樹為D是C的孩子（左孩子），右子樹E是C的兄弟，C的兄弟也是A的孩子，D和E左、右子樹均為空，說明它們既無兄弟，又無孩子，轉(zhuǎn)換完成。

森林與二叉樹的相互轉(zhuǎn)換，在此以圖例說明（如圖2.2所示）。

圖2.2 b： A為根結(jié)點，左孩子為B，右兄弟E。

圖2.2 c： B結(jié)點無孩子，左子樹為空，但有兩個兄弟C、D。

E結(jié)點有一個孩子F為左子樹，有一個兄弟G為右子樹。

圖2.2 d： G結(jié)點有一個孩子H為左子樹，右邊無兄弟，右子樹為空。

H結(jié)點無孩子，左子樹為空，但有一兄弟I，右子樹為I。

I結(jié)點有一孩子J為其左子樹結(jié)點，右邊無兄弟，則右子樹為空。

J結(jié)點既無孩子又無兄弟，轉(zhuǎn)換完成。

顯然，對于二叉樹來說，如果根結(jié)點無右子樹，則只能轉(zhuǎn)換為樹，否則必轉(zhuǎn)換為森林，反之，森林轉(zhuǎn)換成的二叉樹必有右子樹，樹轉(zhuǎn)換成的二叉樹必無右子樹。

為了加深掌握這一 方法，再舉如下幾個圖例（如圖2.3所示）。

可見，無論怎樣轉(zhuǎn)換，根和長子（左邊第一個孩子）是不變的，關(guān)鍵是擺正右子樹的位置，在二叉樹轉(zhuǎn)換成樹或森林的過程中，右子樹是結(jié)點的兄弟，既然是兄弟大家就應放在同

一位置上（即同是某一結(jié)點的孩子）；在森林或樹轉(zhuǎn)換成二叉樹的過程中，某一結(jié)點的兄弟應放在該結(jié)點的右子樹上（右兄弟），這一點初學者必須搞清楚。

3 排序二叉樹轉(zhuǎn)換成平衡二叉樹

由于在構(gòu)造二叉排序樹的同時轉(zhuǎn)換為平衡二叉樹用到的概念較多，要掌握此方法，除了確實掌握平衡二叉樹（即AVL樹）的概念和四種基本型的轉(zhuǎn)換方法外，筆者再強調(diào)以下概念：

（1） *a ：由于插入結(jié)點而使平衡因子絕對值大于1的離插入結(jié)點最近的祖先結(jié)點；

（2） 最小不平衡子樹：*a與插入方向上離*a最近的的兩個結(jié)點構(gòu)成最小不平衡子樹，

顯然最小不平衡子樹屬于四種基本型；

（3） 二叉排序樹因插入結(jié)點失去平衡時，只需對最小不平衡子樹進行旋轉(zhuǎn)處理，旋轉(zhuǎn)后，其它結(jié)點放在相應的位置上即可。

在此只舉一個實際的例子予以說明：

假設關(guān)鍵字序列為（12，24，37，53，45，93），試畫出動態(tài)構(gòu)造此關(guān)鍵字序列的平衡二叉樹（如圖4.1所示）。

這種找到*a和最小不平衡子樹后僅對最小不平衡子樹（都是基本型）進行旋轉(zhuǎn)，其它結(jié)點放到相應的正確位置上的方法對于一般的情況是完全適用的，而且容易掌握，正確性能夠得到保證。

4 結(jié)語

由于數(shù)據(jù)結(jié)構(gòu)及其算法的抽象性和動態(tài)性，本文在說明以上幾種轉(zhuǎn)換技巧時使用了大量的動態(tài)圖例，實際上，熟練掌握這些方法后，不必畫出中間過程，可根據(jù)題目直接得到結(jié)果。如果本文能夠?qū)膺@些題目的讀者有所幫助，那將是筆者莫大的榮幸。不當之處，還望批評指正。

參考文獻

[1]嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學出版社，1997.

[2]許卓群等.數(shù)據(jù)結(jié)構(gòu)[M].北京：高等教育出版社，1995.

[3]唐策善等.數(shù)據(jù)結(jié)構(gòu)——用C語言描述[M].北京：高等教育出版社，1995.

[4] 徐紅.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學出版社，2005.

作者簡介

王鋼（1964-），男，碩士學位?，F(xiàn)為威海職業(yè)學院信息工程系副教授，主要從事C語言、數(shù)據(jù)結(jié)構(gòu)、計算機圖形學的教學工作。

作者單位

威海職業(yè)學院 山東省威海市 264210endprint

摘 要

結(jié)合概念，運用動態(tài)圖形，用通俗的語言對三種數(shù)據(jù)結(jié)構(gòu)的進行轉(zhuǎn)換分析，即：二叉樹與樹和森林的相互轉(zhuǎn)換；圖的最小生成樹的畫法；二叉排序樹轉(zhuǎn)換成平衡二叉樹。

【關(guān)鍵詞】數(shù)據(jù)結(jié)構(gòu) 二叉樹、樹和森林 最小生成樹 平衡二叉樹 轉(zhuǎn)換

1 引言

《數(shù)據(jù)結(jié)構(gòu)》是計算機專業(yè)的一門專業(yè)基礎課程，同時又是一門抽象性較強的課程，很多初學者都感到難以掌握，特別是對于幾種復雜數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換，更是感到難以下手。筆者在總結(jié)了多年的教學實踐，在本文中提出幾種復雜數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換方法，希望能對研究這方面問題的讀者有所幫助。

2 二叉樹與樹和森林的相互轉(zhuǎn)換

要確實掌握這一轉(zhuǎn)換技巧，首先必須搞清這樣幾個概念：

2.1 二叉樹與樹和森林的轉(zhuǎn)換方式

二叉樹與樹和森林的轉(zhuǎn)換其實只有兩種：

（1）二叉樹轉(zhuǎn)換成樹或森林。

（2）森林或樹轉(zhuǎn)換成二叉樹。

也就是說，樹和森林其實是一個概念，不是樹，就是森林，那種認為這一題目可能有六種轉(zhuǎn)換的思路是錯誤的。如圖2.1所示。

2.2 二叉樹與樹和森林的轉(zhuǎn)換分析

二叉樹與樹和森林之所以能夠相互轉(zhuǎn)換，是因為它們都可以用孩子兄弟表示法或稱二叉鏈表表示法作為存儲結(jié)構(gòu)，從物理結(jié)構(gòu)上看，它們的二叉鏈表是相同的，只是解釋不同而已，這一點可參考有關(guān)教科書。

轉(zhuǎn)換技巧：

必須深刻理解孩子兄弟表示法這一概念，在此舉例說明：

對于圖2.1 a的樹對應唯一的一棵二叉樹：

（1）二叉樹的根結(jié)點為A，樹最左邊的第一個孩子B作為A的左子樹根結(jié)點，由于A沒有兄弟，則右子樹為空（圖2.1 b）；

（2）B結(jié)點無孩子，則左子樹為空，右邊的第一個兄弟為C，則右子樹為C（圖2.1 c）

（3）C結(jié)點有一個孩子D，則左子樹為D，右邊的第一個兄弟為E，則右子樹為E，E結(jié)點既無孩子又無兄弟，則轉(zhuǎn)換完成（圖2.1 d）。

反之，若將圖2.1 d的二叉樹轉(zhuǎn)換為樹，則應采取以下方法：

（1）A為樹的根結(jié)點，左子樹B作為A的孩子（左孩子）；

（2）B結(jié)點左子樹為空，說明B結(jié)點無孩子，右子樹為C是B的兄弟（右兄弟），B的兄弟必為A的孩子，C與A連接；

（3）C的左子樹為D是C的孩子（左孩子），右子樹E是C的兄弟，C的兄弟也是A的孩子，D和E左、右子樹均為空，說明它們既無兄弟，又無孩子，轉(zhuǎn)換完成。

森林與二叉樹的相互轉(zhuǎn)換，在此以圖例說明（如圖2.2所示）。

圖2.2 b： A為根結(jié)點，左孩子為B，右兄弟E。

圖2.2 c： B結(jié)點無孩子，左子樹為空，但有兩個兄弟C、D。

E結(jié)點有一個孩子F為左子樹，有一個兄弟G為右子樹。

圖2.2 d： G結(jié)點有一個孩子H為左子樹，右邊無兄弟，右子樹為空。

H結(jié)點無孩子，左子樹為空，但有一兄弟I，右子樹為I。

I結(jié)點有一孩子J為其左子樹結(jié)點，右邊無兄弟，則右子樹為空。

J結(jié)點既無孩子又無兄弟，轉(zhuǎn)換完成。

顯然，對于二叉樹來說，如果根結(jié)點無右子樹，則只能轉(zhuǎn)換為樹，否則必轉(zhuǎn)換為森林，反之，森林轉(zhuǎn)換成的二叉樹必有右子樹，樹轉(zhuǎn)換成的二叉樹必無右子樹。

為了加深掌握這一 方法，再舉如下幾個圖例（如圖2.3所示）。

可見，無論怎樣轉(zhuǎn)換，根和長子（左邊第一個孩子）是不變的，關(guān)鍵是擺正右子樹的位置，在二叉樹轉(zhuǎn)換成樹或森林的過程中，右子樹是結(jié)點的兄弟，既然是兄弟大家就應放在同

一位置上（即同是某一結(jié)點的孩子）；在森林或樹轉(zhuǎn)換成二叉樹的過程中，某一結(jié)點的兄弟應放在該結(jié)點的右子樹上（右兄弟），這一點初學者必須搞清楚。

3 排序二叉樹轉(zhuǎn)換成平衡二叉樹

由于在構(gòu)造二叉排序樹的同時轉(zhuǎn)換為平衡二叉樹用到的概念較多，要掌握此方法，除了確實掌握平衡二叉樹（即AVL樹）的概念和四種基本型的轉(zhuǎn)換方法外，筆者再強調(diào)以下概念：

（1） *a ：由于插入結(jié)點而使平衡因子絕對值大于1的離插入結(jié)點最近的祖先結(jié)點；

（2） 最小不平衡子樹：*a與插入方向上離*a最近的的兩個結(jié)點構(gòu)成最小不平衡子樹，

顯然最小不平衡子樹屬于四種基本型；

（3） 二叉排序樹因插入結(jié)點失去平衡時，只需對最小不平衡子樹進行旋轉(zhuǎn)處理，旋轉(zhuǎn)后，其它結(jié)點放在相應的位置上即可。

在此只舉一個實際的例子予以說明：

假設關(guān)鍵字序列為（12，24，37，53，45，93），試畫出動態(tài)構(gòu)造此關(guān)鍵字序列的平衡二叉樹（如圖4.1所示）。

這種找到*a和最小不平衡子樹后僅對最小不平衡子樹（都是基本型）進行旋轉(zhuǎn)，其它結(jié)點放到相應的正確位置上的方法對于一般的情況是完全適用的，而且容易掌握，正確性能夠得到保證。

4 結(jié)語

由于數(shù)據(jù)結(jié)構(gòu)及其算法的抽象性和動態(tài)性，本文在說明以上幾種轉(zhuǎn)換技巧時使用了大量的動態(tài)圖例，實際上，熟練掌握這些方法后，不必畫出中間過程，可根據(jù)題目直接得到結(jié)果。如果本文能夠?qū)膺@些題目的讀者有所幫助，那將是筆者莫大的榮幸。不當之處，還望批評指正。

參考文獻

[1]嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學出版社，1997.

[2]許卓群等.數(shù)據(jù)結(jié)構(gòu)[M].北京：高等教育出版社，1995.

[3]唐策善等.數(shù)據(jù)結(jié)構(gòu)——用C語言描述[M].北京：高等教育出版社，1995.

[4] 徐紅.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學出版社，2005.

作者簡介

王鋼（1964-），男，碩士學位?，F(xiàn)為威海職業(yè)學院信息工程系副教授，主要從事C語言、數(shù)據(jù)結(jié)構(gòu)、計算機圖形學的教學工作。

作者單位

威海職業(yè)學院 山東省威海市 264210endprint

摘 要

結(jié)合概念，運用動態(tài)圖形，用通俗的語言對三種數(shù)據(jù)結(jié)構(gòu)的進行轉(zhuǎn)換分析，即：二叉樹與樹和森林的相互轉(zhuǎn)換；圖的最小生成樹的畫法；二叉排序樹轉(zhuǎn)換成平衡二叉樹。

【關(guān)鍵詞】數(shù)據(jù)結(jié)構(gòu) 二叉樹、樹和森林 最小生成樹 平衡二叉樹 轉(zhuǎn)換

1 引言

《數(shù)據(jù)結(jié)構(gòu)》是計算機專業(yè)的一門專業(yè)基礎課程，同時又是一門抽象性較強的課程，很多初學者都感到難以掌握，特別是對于幾種復雜數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換，更是感到難以下手。筆者在總結(jié)了多年的教學實踐，在本文中提出幾種復雜數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換方法，希望能對研究這方面問題的讀者有所幫助。

2 二叉樹與樹和森林的相互轉(zhuǎn)換

要確實掌握這一轉(zhuǎn)換技巧，首先必須搞清這樣幾個概念：

2.1 二叉樹與樹和森林的轉(zhuǎn)換方式

二叉樹與樹和森林的轉(zhuǎn)換其實只有兩種：

（1）二叉樹轉(zhuǎn)換成樹或森林。

（2）森林或樹轉(zhuǎn)換成二叉樹。

也就是說，樹和森林其實是一個概念，不是樹，就是森林，那種認為這一題目可能有六種轉(zhuǎn)換的思路是錯誤的。如圖2.1所示。

2.2 二叉樹與樹和森林的轉(zhuǎn)換分析

二叉樹與樹和森林之所以能夠相互轉(zhuǎn)換，是因為它們都可以用孩子兄弟表示法或稱二叉鏈表表示法作為存儲結(jié)構(gòu)，從物理結(jié)構(gòu)上看，它們的二叉鏈表是相同的，只是解釋不同而已，這一點可參考有關(guān)教科書。

轉(zhuǎn)換技巧：

必須深刻理解孩子兄弟表示法這一概念，在此舉例說明：

對于圖2.1 a的樹對應唯一的一棵二叉樹：

（1）二叉樹的根結(jié)點為A，樹最左邊的第一個孩子B作為A的左子樹根結(jié)點，由于A沒有兄弟，則右子樹為空（圖2.1 b）；

（2）B結(jié)點無孩子，則左子樹為空，右邊的第一個兄弟為C，則右子樹為C（圖2.1 c）

（3）C結(jié)點有一個孩子D，則左子樹為D，右邊的第一個兄弟為E，則右子樹為E，E結(jié)點既無孩子又無兄弟，則轉(zhuǎn)換完成（圖2.1 d）。

反之，若將圖2.1 d的二叉樹轉(zhuǎn)換為樹，則應采取以下方法：

（1）A為樹的根結(jié)點，左子樹B作為A的孩子（左孩子）；

（2）B結(jié)點左子樹為空，說明B結(jié)點無孩子，右子樹為C是B的兄弟（右兄弟），B的兄弟必為A的孩子，C與A連接；

（3）C的左子樹為D是C的孩子（左孩子），右子樹E是C的兄弟，C的兄弟也是A的孩子，D和E左、右子樹均為空，說明它們既無兄弟，又無孩子，轉(zhuǎn)換完成。

森林與二叉樹的相互轉(zhuǎn)換，在此以圖例說明（如圖2.2所示）。

圖2.2 b： A為根結(jié)點，左孩子為B，右兄弟E。

圖2.2 c： B結(jié)點無孩子，左子樹為空，但有兩個兄弟C、D。

E結(jié)點有一個孩子F為左子樹，有一個兄弟G為右子樹。

圖2.2 d： G結(jié)點有一個孩子H為左子樹，右邊無兄弟，右子樹為空。

H結(jié)點無孩子，左子樹為空，但有一兄弟I，右子樹為I。

I結(jié)點有一孩子J為其左子樹結(jié)點，右邊無兄弟，則右子樹為空。

J結(jié)點既無孩子又無兄弟，轉(zhuǎn)換完成。

顯然，對于二叉樹來說，如果根結(jié)點無右子樹，則只能轉(zhuǎn)換為樹，否則必轉(zhuǎn)換為森林，反之，森林轉(zhuǎn)換成的二叉樹必有右子樹，樹轉(zhuǎn)換成的二叉樹必無右子樹。

為了加深掌握這一 方法，再舉如下幾個圖例（如圖2.3所示）。

可見，無論怎樣轉(zhuǎn)換，根和長子（左邊第一個孩子）是不變的，關(guān)鍵是擺正右子樹的位置，在二叉樹轉(zhuǎn)換成樹或森林的過程中，右子樹是結(jié)點的兄弟，既然是兄弟大家就應放在同

一位置上（即同是某一結(jié)點的孩子）；在森林或樹轉(zhuǎn)換成二叉樹的過程中，某一結(jié)點的兄弟應放在該結(jié)點的右子樹上（右兄弟），這一點初學者必須搞清楚。

3 排序二叉樹轉(zhuǎn)換成平衡二叉樹

由于在構(gòu)造二叉排序樹的同時轉(zhuǎn)換為平衡二叉樹用到的概念較多，要掌握此方法，除了確實掌握平衡二叉樹（即AVL樹）的概念和四種基本型的轉(zhuǎn)換方法外，筆者再強調(diào)以下概念：

（1） *a ：由于插入結(jié)點而使平衡因子絕對值大于1的離插入結(jié)點最近的祖先結(jié)點；

（2） 最小不平衡子樹：*a與插入方向上離*a最近的的兩個結(jié)點構(gòu)成最小不平衡子樹，

顯然最小不平衡子樹屬于四種基本型；

（3） 二叉排序樹因插入結(jié)點失去平衡時，只需對最小不平衡子樹進行旋轉(zhuǎn)處理，旋轉(zhuǎn)后，其它結(jié)點放在相應的位置上即可。

在此只舉一個實際的例子予以說明：

假設關(guān)鍵字序列為（12，24，37，53，45，93），試畫出動態(tài)構(gòu)造此關(guān)鍵字序列的平衡二叉樹（如圖4.1所示）。

這種找到*a和最小不平衡子樹后僅對最小不平衡子樹（都是基本型）進行旋轉(zhuǎn)，其它結(jié)點放到相應的正確位置上的方法對于一般的情況是完全適用的，而且容易掌握，正確性能夠得到保證。

4 結(jié)語

由于數(shù)據(jù)結(jié)構(gòu)及其算法的抽象性和動態(tài)性，本文在說明以上幾種轉(zhuǎn)換技巧時使用了大量的動態(tài)圖例，實際上，熟練掌握這些方法后，不必畫出中間過程，可根據(jù)題目直接得到結(jié)果。如果本文能夠?qū)膺@些題目的讀者有所幫助，那將是筆者莫大的榮幸。不當之處，還望批評指正。

參考文獻

[1]嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學出版社，1997.

[2]許卓群等.數(shù)據(jù)結(jié)構(gòu)[M].北京：高等教育出版社，1995.

[3]唐策善等.數(shù)據(jù)結(jié)構(gòu)——用C語言描述[M].北京：高等教育出版社，1995.

[4] 徐紅.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學出版社，2005.

作者簡介

王鋼（1964-），男，碩士學位?，F(xiàn)為威海職業(yè)學院信息工程系副教授，主要從事C語言、數(shù)據(jù)結(jié)構(gòu)、計算機圖形學的教學工作。

作者單位

威海職業(yè)學院 山東省威海市 264210endprint