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

9-5二元樹節點插入

談到二元樹節點插入的情況和搜尋相似，重點是插入後仍要保持二元搜尋樹的特性。如果插入的節點在二元樹就沒有插入的必要，而搜尋失敗的狀況，就是準備插入的位置。

if (search (ptr, data)!=null)
       process.stdout.write(‘二元樹中有此節點了！\n’)
else {
       ptr=create_tree(ptr.data);
       inorder(ptr);
}

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

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)=> {
	while (true) {
		if (ptr==null)
			return null;
		if (ptr.data==val)
			return ptr;
		else if (ptr.data>val)
			ptr=ptr.left;
		else
			ptr=ptr.right;
	}
}

var inorder=(ptr)=> {
	if (ptr!=null) {
		inorder(ptr.left);
		process.stdout.write('['+ptr.data+'] ');
		inorder(ptr.right);
	}
}

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('二元樹中有此節點了！\n');
else {
	ptr=create_tree(ptr,data);
	inorder(ptr);
}

9-6二元樹節點的刪除

二元樹節點的刪除則稍微複雜，可分為以下三種狀況：