樹是一種在計(jì)算機(jī)中廣泛應(yīng)用的非線性數(shù)據(jù)結(jié)構(gòu)香罐，數(shù)據(jù)以層次結(jié)構(gòu)存儲(chǔ)（hierarchical）筷频，磁盤的文件目錄就是典型的樹結(jié)構(gòu)筋粗。和字典不同集晚，樹支持對(duì)數(shù)據(jù)進(jìn)行有序存儲(chǔ)懊悯。
二叉樹是最典型的樹結(jié)構(gòu)蜓谋，其它類型的樹和其原理相似。相比線性結(jié)構(gòu)炭分，二叉樹的優(yōu)勢在于高效插入桃焕、刪除和查找。

二叉樹的js實(shí)現(xiàn)

function Node(data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
    this.show = show;
}

function show() {
    return this.data;
}

function BST() {
    this.root = null;
    this.insert = insert;
    this.inOrder = inOrder;
}

function insert(data) {
    var n = new Node(data, null, null);
    if (this.root == null) {
         this.root = n;
     } 
    else {
         var current = this.root;
         var parent;
         while (true) {
             parent = current;
             if (data < current.data ) { // 小于根捧毛，左子樹
                 current = current.left;
                 if (current == null) {
                     parent.left = n;
                     break;
                 }
             }
             else {  // 右子樹
                     current = current.right;
                     if (current == null) {
                         parent.right = n;
                         break;
                     }
              }
         } // end while
    }  // end else
}

function inOrder(node) {
    if (!(node==null)) {
        inOrder(node.left);
        print(node.show());
        inOrder(node.right);
    }
}

function preOrder(node) {
    if (!(node == null)) {
        print(node.show());
        preOrder(node.left);
        preOrder(node.right);
    }
}

function postOrder(node) {
   if (!(node == null)) {
      postOrder(node.left);
      postOrder(node.right);
      print(node.show());
   }
}

function getMin() {
    var cur = this.root;
    while(! (cur.left == null)) cur = cur.left;
    return cur.data;
}
 
function getMax() {
    var cur = this.root;
    while(!(cur.right==null)) cur = cur.right;
    return cur.data;
}
      
function find(data) {
    var cur = this.root;
    while(cur.data != data) {
        if (data < cur.data) {
            cur = cur.left;
        }
        else {
            cur = cur.right;
        }

        if (cur == null) {
            return null;
        }
    }
}
// 刪除節(jié)點(diǎn)
function remove(data) {
    this.root = removeNode(this.root, data);
}
// 遞歸實(shí)現(xiàn)
function removeNode(node, data) {
    if (node == null) {
        return null;
    }
    if (data == node.data) {
        //沒有孩子
        if (node.left == null && node.right == null) {
            return null;
        }
        // 只有左兒子
        if (node.left == null) {
            return node.right;
        }
        // 只有右兒子
        if (node.right == null) {
            return node.left;
        }
        // 有左右孩子
　    var tmp = getSmallest(node.right);
        node.data = tmp.data;
        node.right = removeNode(node.right, tmp.data);
        return node;
    }
    else if (data < node.data) {
        node.left = removeNode(node.left, data);
        return node;
    }
    else {
        node.right = removeNode(node.right, data);
        return node;
    }
}

function getSmallest(node) {
    var cur = node;
    while (cur.left != null) { cur = cur.left; }
    return cur;
}

注意樹的算法很多是遞歸實(shí)現(xiàn)的观堂，尤其注意樹的節(jié)點(diǎn)刪除算法，要清楚的考慮三種情況呀忧，即刪除的節(jié)點(diǎn)是否包含左右孩子师痕。