【經典回放】多種語言系列數據結構算法：二叉樹（JavaScript版）

1 二叉樹類的設計以及二叉樹遍歷

要完成二叉樹的類設計，最好把鏈表下的Node.js復制過來，相比鏈表的結點，二叉樹僅僅是多了一個結點指針而已。略加修改后，就是：

function TNODE(DATA)
{
this.Data=DATA;
this.lChild=null;
this.rChild=null;
this.SetLChild=function (LCHILD){this.lChild=LCHILD;}
this.GetLChild=function (){return this.lChild;}
this.SetRChild=function (RCHILD){this.rChild=RCHILD;}
this.GetRChild=function (){return this.rChild;}
this.GetData=function (){return this.Data;}
}

在這個類中，用：

SetLChild()、GetLChild()? 兩個方法來設置、讀出該結點的左孩子；

SetRChild()、GetRChild()? 兩個方法來設置、讀出該結點的右孩子；

SetData()、GetData()???? 兩個方法來設置、讀出該結點的數值。

要測試這個類，也很容易，注意再次復制二叉樹下的a1.html，略加修改就是：

<html><head><meta http-equiv="Content-Type" content="text/html; charset=gb2312" /><title>二叉樹測試程序</title><SCRIPT TYPE="TEXT/JAVASCRIPT" src="TNode0.js"></SCRIPT><script type="text/javascript">function Trav(T){var s;if(T==undefined||T==null) return;Trav(T.GetLChild());document.write(T.GetData()+'<br>');Trav(T.GetRChild());}function fun(){var A='AA';var B='BB';var C='CC';var D='DD';var TA=new TNODE(A);var TB=new TNODE(B);var TC=new TNODE(C);var TD=new TNODE(D);TA.SetLChild(TB);TA.SetRChild(TC);TB.SetRChild(TD);		Trav(TA);}</script></head><body bgcolor="#FFFFFF"><div><input type="button" id=BUTTON1 value="開始測試" onclick='fun()'/></div></body>
</html>

注意這個程序的第5行，一定要加載TNode0.js，否則無法構造二叉樹。

第7到14行是一個典型的遞歸二叉樹遍歷，其中第12行打印遍歷結果的語句，說明它是按中序遍歷打印結果的。

第15開始的函數fun()，是構造一個簡單的二叉樹，然后在第27行進行遍歷。

從程序本身而言，沒有任何復雜的地方，直接點開T1.html就顯示了結果。

2 IE8下JavaScript程序的調試

JavaScript編程，最大的麻煩是缺乏一個好的編程平臺，往往這類簡單的程序，都是在記事本這樣的程序里編寫的，但必要的調試手段還是需要的。目前，很多瀏覽器都自己帶有JavaScrip程序調試工具，比較常用的有兩種：IE8、Chrome兩種瀏覽器。IE8是WINDOWS系統默認的瀏覽器，而谷歌的Chrome則非常小，并且功能異常強大，我們下面先看在IE8下如何調試JvaaScrip程序。

用IE8打開T1.HTML文件，然后點開菜單：工具->開發人員工具，就是：

圖 1

則顯示下面的界面：

圖 2

注意按下選項卡：腳本，如圖3，就會看到我們的程序。

圖 3

注意看上面的按鈕：啟動調試，鼠標按下該按鈕。然后看左邊程序行號，選第17行的“17”位置處、鼠標點下，就是這樣的結果：

圖 4

這個功能是給該行上加上斷點，所謂斷點就是程序運行到這里要停止下來，做完這些工作后，回到瀏覽器界面里，按下網頁上按鈕：開始測試，讓程序開始運行，此時程序會跳到上述加斷點的位置處、并停下來，就是：

圖 5

注意此時的界面，它分割成兩個部分，按下右邊界面的按鈕：局部變量，有：

圖 6

如果按下F10、F11（含義同VC一致），會逐個語句執行并看到結果，如：

圖 7

從圖7我們可以看到這些變量的結果確實是我們所要的。按F11逐步進Trav()函數，就會看到這個樹的遍歷情況。

谷歌瀏覽器chrome的調試過程和IE8差別不大，僅僅是界面有差異，由于谷歌瀏覽器并沒有IE8瀏覽器的文件打開菜單，所以你可以用鼠標點中T1.HTML文件，直接拖進瀏覽器界面里即可，注意谷歌瀏覽器的調試功能是在：

圖 8

? 該功能隱藏很深，但功能確實不錯。值得注意的是谷歌瀏覽器支持HTML5，而IE8則不支持。

學會瀏覽器下調試JavaScript的另一個好處是：你可以直接對一個網站的程序進行這樣的調試，這在過去是不能想象的事情。由于有了這樣的功能，一度讓很多網站的安全防護遭到解破，但很快，相當數量的網站其安全體系也有了質的飛躍，所以一個工具本身的好壞是很難評價的，但總體說來：勤奮者手中有好的工具、那么好處是顯而易見的事情。

3 復雜數據類型對象的二叉樹構造以及遍歷

對JavaScrip這樣的計算機語言而言，它的變量本身沒有什么特定的類型概念，所以本身就是泛型的，但我們還是做一個結點數據類型復雜的二叉樹來完成一個實驗。

復制鏈表下的ElemType.js過來，這個類是：

function ElemType(SNO,SNAME,SAGE)
{this.sNo=SNO;this.sName=SNAME;this.sAge=SAGE;this.GetSNO=function(){return this.sNo;}this.GetSNAME=function(){return this.sName;}this.GetSAGE=function(){return this.sAge;}
}

這個類雖然簡單但也有合適的數據類型。為此，我們就要修改T1.html中結點的數據，就是這樣的：

?????????????????? var A=new ElemType(20102000,'A',19);

?????????????????? var B=new ElemType(20102001,'B',20);

?????????????????? var C=new ElemType(20102002,'C',21);

?????????????????? var D=new ElemType(20102003,'D',22);

然后和T1.HEML一樣，完成一個簡單的二叉樹，就是：

<html><head><meta http-equiv="Content-Type" content="text/html; charset=gb2312" /><title>二叉樹測試程序</title><SCRIPT TYPE="TEXT/JAVASCRIPT" src="ElemType.js"></SCRIPT><SCRIPT TYPE="TEXT/JAVASCRIPT" src="TNode0.js"></SCRIPT><script type="text/javascript">function Trav(T){var s;if(T==undefined||T==null) return;Trav(T.GetLChild());s=T.GetData();document.write(s.GetSNO()+'  '+s.GetSNAME()+'  '+s.GetSAGE()+'<br>');Trav(T.GetRChild());}function fun(){var A=new ElemType(20102000,'A',19);var B=new ElemType(20102001,'B',20);var C=new ElemType(20102002,'C',21);var D=new ElemType(20102003,'D',22);var TA=new TNODE(A);var TB=new TNODE(B);var TC=new TNODE(C);var TD=new TNODE(D);TA.SetLChild(TB);TA.SetRChild(TC);TB.SetRChild(TD);		Trav(TA);}</script></head><body bgcolor="#FFFFFF"><div><input type="button" id=BUTTON1 value="開始測試" onclick='fun()'/></div></body>
</html>

表4 復雜數據類型的二叉樹遍歷，見T2.html

注意上面程序的變更：

第5行：要引用ElemType.js，否則我們沒辦法構造學生類型數據；

由于JavaScript的數據類型本身就是泛型，所以二叉樹類不需要任何修改。

第8行開始的遍歷函數Trav()，由于每個結點類型成為ElemType這樣的三列數據，所以要顯示一行就必須把三列分開顯示，如第14行。運行T2.html，會看到這個樹的遍歷結果。

4 回調模式傳輸遍歷結果

在C#下dt.c已經顯示了這個技術的全貌，這樣的遞歸函數就是這樣的；

function Trav(T,preTrav,inTrav,posTrav)
{if(T==undefined||T==null) return;if(!(preTrav==undefined||preTrav==null)) preTrav(T);Trav(T.GetLChild(),preTrav,inTrav,posTrav);if(!(inTrav==undefined||inTrav==null)) inTrav(T);Trav(T.GetRChild(),preTrav,inTrav,posTrav);if(!(posTrav==undefined||posTrav==null)) posTrav(T);
}

在這個函數里，參數:

T：????? 遍歷中二叉樹的結點對象；

preTrav：先序遍歷處理函數；

inTrav：中序遍歷處理函數；

posTrav：后序遍歷處理函數；

把這個函數寫進二叉樹類中，全部就是：

function TNODE(DATA)
{
this.Data=DATA;
this.lChild=null;
this.rChild=null;
this.SetLChild=function (LCHILD){this.lChild=LCHILD;}
this.GetLChild=function (){return this.lChild;}
this.SetRChild=function (RCHILD){this.rChild=RCHILD;}
this.GetRChild=function (){return this.rChild;}
this.GetData=function (){return this.Data;}
function Trav(T,preTrav,inTrav,posTrav)
{if(T==undefined||T==null) return;if(!(preTrav==undefined||preTrav==null)) preTrav(T);Trav(T.GetLChild(),preTrav,inTrav,posTrav);if(!(inTrav==undefined||inTrav==null)) inTrav(T);Trav(T.GetRChild(),preTrav,inTrav,posTrav);if(!(posTrav==undefined||posTrav==null)) posTrav(T);
}
this.Traverse=function(preTrav,inTrav,posTrav){Trav(this,preTrav,inTrav,posTrav);}
}

注意這個類是在文件TNode1.js中。為了測試這個類，編寫網頁程序如下：

<html><head><meta http-equiv="Content-Type" content="text/html; charset=gb2312" /><title>二叉樹測試程序</title><SCRIPT TYPE="TEXT/JAVASCRIPT" src="TNode1.js"></SCRIPT><script type="text/javascript">function P1(T){document.write(T.GetData()+'<br>');}function fun(){var A='AA';var B='BB';var C='CC';var D='DD';var TA=new TNODE(A);var TB=new TNODE(B);var TC=new TNODE(C);var TD=new TNODE(D);TA.SetLChild(TB);TA.SetRChild(TC);TB.SetRChild(TD);		TA.Traverse(P1,null,null);}</script></head><body bgcolor="#FFFFFF"><div><input type="button" id=BUTTON1 value="開始測試" onclick='fun()'/></div></body>
</html>

注意第7行，這個函數P1()僅僅是打印結點的值，注意在第24行，TA結點的遍歷用P1作為實參傳遞給遍歷函數，這樣，這個網頁會打印出二叉樹的先序遍歷結果。