摘 要

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

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

1 引言

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

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

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

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

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

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

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

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

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

二叉樹與樹和森林之所以能夠相互轉(zhuǎn)換，是因?yàn)樗鼈兌伎梢杂煤⒆有值鼙硎痉ɑ蚍Q二叉鏈表表示法作為存儲(chǔ)結(jié)構(gòu)，從物理結(jié)構(gòu)上看，它們的二叉鏈表是相同的，只是解釋不同而已，這一點(diǎn)可參考有關(guān)教科書。

轉(zhuǎn)換技巧：

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

對(duì)于圖2.1 a的樹對(duì)應(yīng)唯一的一棵二叉樹：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

顯然，對(duì)于二叉樹來(lái)說(shuō)，如果根結(jié)點(diǎn)無(wú)右子樹，則只能轉(zhuǎn)換為樹，否則必轉(zhuǎn)換為森林，反之，森林轉(zhuǎn)換成的二叉樹必有右子樹，樹轉(zhuǎn)換成的二叉樹必?zé)o右子樹。

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

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

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

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

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

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

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

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

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

在此只舉一個(gè)實(shí)際的例子予以說(shuō)明：

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

作者簡(jiǎn)介

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

作者單位

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

摘 要

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

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

1 引言

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

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

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

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

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

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

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

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

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

二叉樹與樹和森林之所以能夠相互轉(zhuǎn)換，是因?yàn)樗鼈兌伎梢杂煤⒆有值鼙硎痉ɑ蚍Q二叉鏈表表示法作為存儲(chǔ)結(jié)構(gòu)，從物理結(jié)構(gòu)上看，它們的二叉鏈表是相同的，只是解釋不同而已，這一點(diǎn)可參考有關(guān)教科書。

轉(zhuǎn)換技巧：

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

對(duì)于圖2.1 a的樹對(duì)應(yīng)唯一的一棵二叉樹：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

顯然，對(duì)于二叉樹來(lái)說(shuō)，如果根結(jié)點(diǎn)無(wú)右子樹，則只能轉(zhuǎn)換為樹，否則必轉(zhuǎn)換為森林，反之，森林轉(zhuǎn)換成的二叉樹必有右子樹，樹轉(zhuǎn)換成的二叉樹必?zé)o右子樹。

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

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

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

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

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

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

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

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

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

在此只舉一個(gè)實(shí)際的例子予以說(shuō)明：

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

作者簡(jiǎn)介

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

作者單位

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

摘 要

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

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

1 引言

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

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

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

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

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

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

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

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

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

二叉樹與樹和森林之所以能夠相互轉(zhuǎn)換，是因?yàn)樗鼈兌伎梢杂煤⒆有值鼙硎痉ɑ蚍Q二叉鏈表表示法作為存儲(chǔ)結(jié)構(gòu)，從物理結(jié)構(gòu)上看，它們的二叉鏈表是相同的，只是解釋不同而已，這一點(diǎn)可參考有關(guān)教科書。

轉(zhuǎn)換技巧：

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

對(duì)于圖2.1 a的樹對(duì)應(yīng)唯一的一棵二叉樹：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

顯然，對(duì)于二叉樹來(lái)說(shuō)，如果根結(jié)點(diǎn)無(wú)右子樹，則只能轉(zhuǎn)換為樹，否則必轉(zhuǎn)換為森林，反之，森林轉(zhuǎn)換成的二叉樹必有右子樹，樹轉(zhuǎn)換成的二叉樹必?zé)o右子樹。

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

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

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

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

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

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

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

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

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

在此只舉一個(gè)實(shí)際的例子予以說(shuō)明：

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

作者簡(jiǎn)介

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

作者單位

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