張標(biāo)漢

文章編號(hào)：1672-5913(2009)10-0051-02

摘要：平衡二叉樹教學(xué)中傳統(tǒng)的旋轉(zhuǎn)方法不太容易被學(xué)生理解，針對(duì)這一問題，本文通過分析二叉排序樹的基本原理，摸索出一種在教學(xué)實(shí)踐中更加容易被學(xué)生理解的平衡二叉樹調(diào)整方法。

關(guān)鍵詞：二叉排序樹 平衡二叉樹 教學(xué)探討

中圖分類號(hào)：G642

文獻(xiàn)標(biāo)識(shí)碼：B

在“數(shù)據(jù)結(jié)構(gòu)與算法”課程教學(xué)中，許多教科書在介紹平衡二叉樹調(diào)整這部分內(nèi)容時(shí)，采用的都是旋轉(zhuǎn)的方法，將不平衡二叉樹用左右、順逆時(shí)針旋轉(zhuǎn)的方法使失去平衡的二叉排序樹調(diào)整為平衡二叉樹。但是在實(shí)際教學(xué)過程中，筆者發(fā)現(xiàn)這樣的方法不太容易被學(xué)生理解，許多學(xué)生尤其是專科學(xué)生搞不清楚怎么旋轉(zhuǎn)、圍繞誰旋轉(zhuǎn)。針對(duì)這一問題，筆者通過不斷的教學(xué)實(shí)踐摸索出一種更容易被學(xué)生接受和理解的平衡二叉樹調(diào)整方法——填空法，這種方法充分利用了二叉排序樹的特點(diǎn)，采用填空的方式對(duì)失衡的二叉排序樹進(jìn)行調(diào)整使之保持平衡。

1基本原理

我們知道，二叉排序樹具有這樣一個(gè)特點(diǎn)：左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值，右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值。即有這樣一個(gè)關(guān)系：左<根<右。利用這個(gè)特點(diǎn)，當(dāng)我們?cè)诓迦虢Y(jié)點(diǎn)使得原平衡二叉樹失去平衡而需要進(jìn)行調(diào)整時(shí)，首先尋找最小不平衡子樹。最小不平衡子樹的尋找方法是：從插入的結(jié)點(diǎn)出發(fā)，依次計(jì)算其祖先的平衡因子，發(fā)現(xiàn)的第一個(gè)平衡因子的絕對(duì)值大于1的結(jié)點(diǎn)就是最小不平衡子樹的根結(jié)點(diǎn)，則以它為根結(jié)點(diǎn)的子樹就是最小不平衡子樹。先考慮最簡(jiǎn)單的情況，這棵最小不平衡子樹僅由三個(gè)結(jié)點(diǎn)構(gòu)成。此時(shí)最小不平衡子樹可以分為四種基本類型，分別是：LL型、LR型、RL型和RR型。如圖1所示：

在教科書中，這四種情況是分別討論的：對(duì)LL型做一次順時(shí)針旋轉(zhuǎn)，對(duì)LR型先逆時(shí)針旋轉(zhuǎn)后順時(shí)針旋轉(zhuǎn)，對(duì)RL型先順時(shí)針旋轉(zhuǎn)后逆時(shí)針旋轉(zhuǎn)，對(duì)RR型做一次逆時(shí)針旋轉(zhuǎn)。但應(yīng)用填空法，這四種基本情況的調(diào)整可以統(tǒng)一在一起：

可以知道，要使得由三個(gè)結(jié)點(diǎn)構(gòu)成的二叉排序樹平衡，其基本結(jié)構(gòu)必定是一個(gè)結(jié)點(diǎn)作為根結(jié)點(diǎn)，一個(gè)作為左孩子結(jié)點(diǎn)，一個(gè)作為右孩子結(jié)點(diǎn)。如圖2所示：

根據(jù)二叉排序樹的特點(diǎn)(左<根<右)，我們只要把上述每種基本情況中的三個(gè)結(jié)點(diǎn)按值從小到大排列，將最小的一個(gè)填在左孩子結(jié)點(diǎn)位置，最大的一個(gè)填在右孩子結(jié)點(diǎn)位置，中間的填在根結(jié)點(diǎn)位置。很容易地就可以將上述四種最小不平衡子樹調(diào)整為平衡二叉樹，如圖3所示：

進(jìn)一步考慮更為復(fù)雜的情況，假定上述結(jié)點(diǎn)各自還有左右子樹，我們?nèi)匀豢梢允褂梦覀兊奶羁辗ㄝp松的加以調(diào)整。這四種復(fù)雜情況如圖4所示：

假定都在CL中插入一個(gè)結(jié)點(diǎn)使得A的平衡因子的絕對(duì)值變?yōu)?從而使得原平衡二叉樹失去平衡，此時(shí)以A為根結(jié)點(diǎn)的子樹就是最小不平衡子樹，這棵最小不平衡子樹可以分為7個(gè)部分。沿著從根結(jié)點(diǎn)A到插入結(jié)點(diǎn)位置CL的路徑方向依次取三個(gè)結(jié)點(diǎn)，假設(shè)為A、B、C，它們和剩下的AL、AR、BL、BR、CL、CR中的4個(gè)構(gòu)成的二叉排序樹要成為平衡二叉樹，則由這7個(gè)部分組成的平衡二叉樹的基本結(jié)構(gòu)一定是如圖5所示情形：

其中，A、B、C三者中值最小的為左子樹的根結(jié)點(diǎn)，值最大的為右子樹的根結(jié)點(diǎn)，中間的為整個(gè)最小不平衡子樹的根結(jié)點(diǎn)。其余的AL、AR、BL、BR、CL、CR等按從小到大的順序排列，將它們從左到右依次填在樹的第三層即可，完成后的二叉樹一定是平衡二叉樹。對(duì)上述四種復(fù)雜情形，平衡后如圖6所示：

2示例

例：已知長(zhǎng)度為12的表：{Jan,Feb,Mar,Apr,May,June, July,Aug,Sep,Oct,Nov,Dec}，按照表中元素順序構(gòu)造一棵平衡二叉排序樹。

解：構(gòu)造過程如圖7、圖8所示。

教學(xué)實(shí)踐證明，本文采用的填空法要比傳統(tǒng)的旋轉(zhuǎn)法更容易被學(xué)生接受和理解。

參考文獻(xiàn)：

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

[2] 馬秋菊. 數(shù)據(jù)結(jié)構(gòu)(C語言描述)[M]. 北京:中國(guó)水利水電出版社,2006.

Discussion on Teaching of Balancing the Binary Tree

ZHANG Biao-han

(The Department of Maths & Computer Science, Sanming College, Sanming 365004, China)

Abstract:The rotation method for balanced binary tree is not easy to understand by the students, This paper introduced a new method using the characteristics of the binary sort tree that is easier to understand by the students.

Key words:binary sort tree; balanced binary tree; teaching discussion