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

9-4二元樹節點搜尋

我們先來討論在所建立的二元樹中搜尋單一節點資料。基本上，二元樹在建立的過程中，是依據左子樹<樹根<右子樹的原則建立，因此只須從樹根出發比較鍵值，如果比樹根大就往右，否則由左往下，直到相等就可以找到搜尋的值，如果比到null，無法再前進就代表搜尋不到此值。

二元樹搜尋的演算法

var search=(ptr,val)=> {
     i=1;
     while (true)  {
            if (ptr==null)
                  return null;
             if (ptr.data==val) {
                  process.stdout.write(‘共搜尋 ‘+i+’ 次’+’\n’);
                  return ptr;
              }
              else if (ptr.data>val)
                  ptr=ptr.left;
              else
                  ptr=ptr.right;
              i+=1;
       }
}

JS               binary_search.js

class tree {
	constructor() {
		this.data=0;
		this.left=null;
		this.right=null;
	}
}

var create_tree=(root,val)=> {
	newnode=new tree();
	newnode.data=val;
	newnode.left=null;
	newnode.right=null;
	if (root==null) {
		root=newnode;
		return root;
	}
	else {
		current=root;
		while (current!=null) {
			backup=current;
			if (current.data>val)
				current=current.left;
			else
				current=current.right;
		}
		if (backup.data>val)
			backup.left=newnode;
		else
			backup.right=newnode;
	}
	return root;
}

var search=(ptr,val)=> {
	i=1;
	while (true) {
		if (ptr==null)
			return null;
		if (ptr.data==val) {
			process.stdout.write('共搜尋 '+i+' 次'+'\n');
			return ptr;
		}
		else if (ptr.data>val)
			ptr=ptr.left;
		else
			ptr=ptr.right;
		i+=1;
	}
}

arr=[7,1,4,2,8,13,12,11,15,9,5];
ptr=null;
process.stdout.write('[原始陣列內容]\n');
for (i=0; i<11; i++) {
	ptr=create_tree(ptr,arr[i]);
	process.stdout.write('['+arr[i]+'] ');
}
process.stdout.write('\n');
const prompt=require('prompt-sync')();
const data=parseInt(prompt('請輸入搜尋值：'));
if (search(ptr.data)!=null)
	process.stdout.write('你要找的值 ['+data+'] 有找到！！\n');
else
	process.stdout.write('您要找的值沒找到！！\n');

Java Script的程式有問題！