圖說演算法使用JavaScript(二十二)

9-1陣列實作二元樹

如果使用循序的一維陣列來表示二元樹，首先可將此二元樹假想成一個完滿二元樹(Full Binary Tree)，而且第k個階度具有2^(k-1)個節點，並且依序存放在此一維陣列中。首先來看看使用一維陣列建立二元樹的表示方法及索引值的配置：

從上圖中，我們可以看到此一維陣列中的索引值有以下關係：

1.左子樹索引值是父節點索引值*2
2.右子樹索引值是父節點索引值*2+1

接著就來看如何以一維陣列建立二元樹的實例，事實上就是建立一個二元搜尋樹，這是一種很好的排序應用模式，因為在建立二元樹的同時，資料已經經過初步的比較判斷，並依照二元樹的建立規則來存放資料。所謂二元搜尋樹具有以下特點：

1.可以是空集合，但若不是空集合則節點上一定要有健值。
2.每一個樹根的值須大於左子樹的值。
3.每一個樹根的值需小於右子樹的值。
4.左右子樹也是二元搜尋樹。
5.樹的每個節點值都不同。

JS                  array_tree.js

length=8;
data=[6,3,5,9,7,8,4,2];
btree=[];
for (i=0; i<16; i++)  btree[i]=0;
	process.stdout.write("原始陣列內容： \n");

for (i=0; i<length; i++) 
	process.stdout.write("[" +data[i] + "] ");
	process.stdout.write('\n');

	for (i=0; i<length; i++) {
		for (level=1; btree[level] !=0;) {
			if (data[i] > btree[level])
				level=level*2+1;
			else
				level=level*2;
		}
		btree[level]=data[i];
	}
process.stdout.write("二元樹內容：\n");
for (i=1; i<16; i++)
	process.stdout.write("[" + btree[i] + "] ");
process.stdout.write('\n');

PHP                array_tree.php

$length=8;
$brtree=array();
$data=array(6,3,5,9,7,8,4,2);
echo "<br>原始陣列：<br>";
print_arr($data);
echo "<br>";

for ($i=0; $i<$length; $i++) {
	for ($level=1; $brtree[$level]!=0;) {
		if ($data[$i]>$brtree[$level])
			$level=$level*2+1;
		else
			$level=$level*2;
	}
	$brtree[$level]=$data[$i];
}

//$brtree = asort($brtree);
//print_arr($brtree);
//echo "<-here<br>";
$count=$length*2;
$new_brtree=array();
for ($j=1; $j<=$count; $j++) {
	if (!$brtree[$j]) 
		$value=0;
	else 
		$value=$brtree[$j];
	//echo "{$j}-[{$value}]   ";
	$new_brtree[]=$value;
}

print_arr($new_brtree);


function print_arr ($arr) {
	$i=0;
	foreach ($arr as $key =>$value){
		$key=$key+1;
		echo $key."[".$value."]   ";
		//echo ($i%8==0 && $i!=0) ? "<br>":"   ";
		$i++;
	}
}