使用javascript模擬常見數據結構(四)

七、樹

　　樹是一種非線性的分層的數據結構，在現實生活中比較常見的例子比如家譜和公司的組織架構圖，如下所示：

　　

　　一個樹結構存在著一系列的父子結構，并且有著一個根節點，這種結構本質上表明了一對多的關系。

　　

　　那，如同上面這樣的結構，一個節點可以有多個子節點，但最多只能有一個父節點，如果每個節點的子節點數都不大于2，那么我們可以把這樣一棵樹叫做二叉樹。而如果這棵樹的左側的節點均小于其根節點，而右側的節點都大于根節點，那么我們管這樣的一棵樹叫做搜索二叉樹（BST）。

　　我們可以用以下js代碼構建二叉搜索樹：

　　

function BinarySearchTree() {
         var Node = function(key){ 
         this.key = key;
         this.left = null;
         this.right = null;
     };
     var root = null; 
}

　　嗯嗯，其實就如同下圖所示：

　　

　　嗯，老慣例，還是有一些方法需要介紹，下面繼續貼一些代碼，大家看到名字其實就基本知道是干嘛的了。

　　

var insertNode = function(node, newNode){if (newNode.key < node.key){ if (node.left === null){ node.left = newNode; } else {insertNode(node.left, newNode);}} else {if (node.right === null){ node.right = newNode;} else {insertNode(node.right, newNode);}}
};

　　嗯，上面是插入的方法，用到了遞歸，下面說幾個遍歷的方法。

var inOrderTraverseNode = function (node, callback) {if (node !== null) { inOrderTraverseNode(node.left, callback); callback(node.key); inOrderTraverseNode(node.right, callback); }
}

　　這個是中序遍歷，其遍歷過程大概如下圖所示：

　　

嗯，可以看到，這樣遍歷完了之后是從下到大的，可以用于排序。

然后，先序遍歷

　　

var preOrderTraverseNode = function (node, callback) {if (node !== null) {callback(node.key); preOrderTraverseNode(node.left, callback); preOrderTraverseNode(node.right, callback); }
}

?

　　恩，然后這個就是先序遍歷~最后一種就是后序遍歷，其實就是最后來訪問根節點。

　　

var postOrderTraverseNode = function (node, callback) {if (node !== null) {postOrderTraverseNode(node.left, callback); //{1}postOrderTraverseNode(node.right, callback); //{2}callback(node.key); //{3}
    }
};    

?