//以下定義一個節點類function Node(data,left,right){  // 節點的鍵值  this.data = data;  // 左節點  this.left = left;  // 右節點  this.right = left;  // 顯示該節點的鍵值  this.show = show;}// 實現show方法function show(){  return this.data;}

// 二叉查找樹BST// 有一個節點屬性，還有一些其他的方法，以下定義一個二叉查找樹BST類function BST(){  // 根節點初始化為空  this.root = null;  // 方法  // 插入  this.insert = insert;  // 中序遍歷  this.inorder = inorder;  // 先序遍歷  this.preorder = preorder;  // 后序遍歷  this.postorder = postorder;}//實現insert插入方法function insert(data){  // 創建一個節點保存數據  var node = new Node(data,null,null);  // 下面將節點node插入到樹中  // 如果樹是空的，就將節點設為根節點  if(!this.root){    this.root = node;  }else{ //樹不為空    // 判斷插在父節點的左邊還是右邊    // 所以先要保存一下父節點    // var parent = this.root;    var current = this.root;    var parent;    // 如果要插入的節點鍵值小于父節點鍵值，則插在父節點左邊，    // 前提是父節點的左邊為空，否則要將父節點往下移一層，    // 然后再做判斷    while(true){      // data小于父節點的鍵值      parent = current;      if(data < parent.data){        // 將父節點往左下移(插入左邊)        // parent = parent.left;        current = current.left;        // 如果節點為空，則直接插入        if(!current){          // ！！！此處特別注意，如果就這樣把parent賦值為node，也僅僅只是parent指向node，          // 而并沒有加到父元素的左邊！??！根本沒有加到樹中去。所以要先記住父元素，再把當前元素加入進去          parent.left = node;          break;        }            }else{ // 將父節點往右下移(插入右邊)        current = current.right;        if(!current){          parent.right = node;          break;        }      }    }  }} //實現inorder遍歷方法(左中右)function inorder(node){  if(node){    inorder(node.left);    console.log(node.show());    inorder(node.right);  }}// 先序遍歷(中左右)function preorder(node){  if(node){    console.log(node.show());    preorder(node.left);    preorder(node.right);  }}// 后序遍歷(左右中)function postorder(node){  if(node){    preorder(node.left);    preorder(node.right);    console.log(node.show());  }}

// 后序遍歷(左右中)function postorder(node){  if(node){    postorder(node.left);    postorder(node.right);    console.log(node.show());  }}// 實例化一個BST樹var tree = new BST();// 添加節點tree.insert(30);tree.insert(14);tree.insert(35);tree.insert(12);tree.insert(17);// 中序遍歷tree.inorder(tree.root);// 先序遍歷tree.preorder(tree.root);// 后序遍歷tree.postorder(tree.root);