【经典回放】多种语言系列数据结构算法：二叉树（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，略加修改就是：

	
	
	二叉树测试程序
		
		
		function Trav(T)
		{
			var s;
			if(T==undefined||T==null) return;
			Trav(T.GetLChild());
			document.write(T.GetData()+'');
			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);
		}
		
	
	
		

		
		
	

注意这个程序的第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一样，完成一个简单的二叉树，就是：

	
	
	二叉树测试程序
		
		
		
		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()+'');
			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);
		}
		
	

	
		

		
		
	

表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中。为了测试这个类，编写网页程序如下：

	
	
	二叉树测试程序
		
		
		function P1(T)
		{
			document.write(T.GetData()+'');
		}
		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);
		}
		
	
	
		

		
		
	

注意第7行，这个函数P1()仅仅是打印结点的值，注意在第24行，TA结点的遍历用P1作为实参传递给遍历函数，这样，这个网页会打印出二叉树的先序遍历结果。