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

9-2鏈結串列實作二元樹

所謂鏈結串列實作二元樹，就是利用鏈結串列來儲存二元樹。基本上，使用串列來表示二元樹的好處是對於節點的增加與刪除相當容易，缺點是很難找到父節點，除非在每一節點多增加一個欄位。以上述宣告而言，此節點所存放的資料型態為整數。寫成如下宣告：

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

以串列方式建立二元樹的演算法如下：

var creat_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) {
                  back=current;
                  if (current.data>val)
                      current=current.left;
                  else
                  current=current.right;
      }
      if (back.data>val)
             backup.left=newnode;
      else
             backup.right=newnode;
     }
       return root;
}

JS               list_tree.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;
}
data=[5,6,24,8,12,3,17,1,9];
ptr=null;
root=null;
for (i=0; i<9; i++) 
	ptr=create_tree(ptr,data[i]);
process.stdout.write('左子樹：\n');
root=ptr.left;
while (root!=null) {
	process.stdout.write(root.data+'\n');
	root=root.left;
}
process.stdout.write('------------------------------\n');
process.stdout.write('右子樹：\n');
root=ptr.right;
while (root!=null) {
	process.stdout.write(root.data+'\n');
	root=root.right;
}
process.stdout.write('\n');