溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了JS中的算法與數據結構之二叉查找樹（Binary Sort Tree）。分享給大家供大家參考，具體如下：
我們之前所學到的列表，棧等都是一種線性的數據結構，今天我們將學習計算機中經常用到的一種非線性的數據結構——樹（Tree），由于其存儲的所有元素之間具有明顯的層次特性，因此常被用來存儲具有層級關系的數據，比如文件系統中的文件；也會被用來存儲有序列表等。
在樹結構中，每一個結點只有一個前件，稱為父結點，沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根（root）。每一個結點可以有多個后件，稱為該結點的子結點。沒有后件的結點稱為葉子結點。一個結點所擁有的子結點的個數稱為該結點的度，所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
二叉樹是一種特殊的樹，它的子節點個數不超過兩個，且分別稱為該結點的左子樹（left subtree）與右子樹（right subtree），二叉樹常被用作二叉查找樹和二叉堆或是二叉排序樹（BST）。
二叉樹
按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且只被訪問一次，這個操作被稱為樹的遍歷，是對樹的一種最基本的運算。由于二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。
按照根節點訪問的順序不同，樹的遍歷分為以下三種：前序遍歷，中序遍歷，后序遍歷；
前序遍歷：根節點->左子樹->右子樹
先序遍歷
中序遍歷：左子樹->根節點->右子樹
中序遍歷
后序遍歷：左子樹->右子樹->根節點
后序遍歷
因此我們可以得之上面二叉樹的遍歷結果如下：前序遍歷：ABDEFGC 中序遍歷：DEBGFAC 后序遍歷：EDGFBCA
實際應用中，樹的每個節點都會有一個與之相關的值對應，有時候會被稱為鍵。因此，我們在構建二叉查找樹的時候，確定子節點非常的重要，通常將相對較小的值保存在左節點中，較大的值保存在右節點中，這就使得查找的效率非常高，因此被廣泛使用。
根據上面的知識，我們了解到二叉樹實際上是由多個節點組成，因此我們首先就要定義一個Node類，用于存放樹的節點，其構造與前面的鏈表類似。Node類的定義如下：
//節點定義
function Node (data , left , right) {
this.data = data; // 數據
this.left = left; // 左節點
this.right = right; // 右節點
this.show = show; // 顯示節點數據
}
function show(){
return this.data;
}
Node對象既保存了數據，也保存了它的左節點和右節點的鏈接，其中 show 方法用來顯示當前保存在節點中數據。
現在我們可以創建一個類，用來表示二叉查找數（BST），我們初始化類只包含一個成員，一個表示二叉查找樹根節點的 Node 對象，初始化為 null ， 表示創建一個空節點。
//二叉查找樹（BST）的類
function BST(){
this.root = null; // 根節點
this.insert = insert; // 插入節點
this.preOrder = preOrder; // 先序遍歷
this.inOrder = inOrder; // 中序遍歷
this.postOrder = postOrder; // 后序遍歷
this.find = find; // 查找節點
this.getMin = getMin; // 查找最小值
this.getMax = getMax; // 查找最大值
this.remove = remove; // 刪除節點
}
現在，我們需要為我們的類添加方法。
首先就是 insert 方法，向樹中添加一個新節點，我們一起來看看這個方法；
insert：向樹中添加新節點
因為添加節點會涉及到插入位置的問題，必須將其放到正確的位置上，才能保證樹的正確性，整個過程較為復雜，我們一起來梳理一下：
首先要添加新的節點，首先需要創建一個Node對象，將數據傳入該對象。
其次要檢查當前的BST樹是否有根節點，如果沒有，那么表示是一棵新數，該節點就為該樹的根節點，那么插入這個過程就結束了；否則，就要繼續進行下一步了。
如果待插入節點不是根節點，那么就必須對BST進行遍歷，找到合適的位置。該過程類似遍歷鏈表，用一個變量存儲當前節點，一層一層遍歷BST，算法如下：
這樣，就能保證每次添加的新節點能夠放到正確的位置上，具體實現如下；
//插入新節點
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;
}
}
}
}
}
現在BST類已初步成型，但操作還僅僅限于插入節點，我們需要有遍歷BST的能力，上面我們也提到了是三種遍歷方式。其中中序遍歷是最容易實現的，我們需要升序的方法訪問樹中的所有節點，先訪問左子樹，在訪問根節點，最后是右子樹，我們采用遞歸來實現！
inOrder：中序遍歷
// 中序遍歷
function inOrder (node) {
if( !(node == null )){
inOrder( node.left );
console.debug( node.show() + ' ');
inOrder( node.right );
}
}
怎么樣，了解了原理，實現起來還是蠻簡單的~
我們用一段代碼來測試一下我們所寫的中序遍歷：
var nums = new BST(); //插入數據 nums.insert(23); nums.insert(45); nums.insert(16); nums.insert(37); nums.insert(3); nums.insert(99); nums.insert(22);
上述插入數據后，會形成如下的二叉樹
BST
中序遍歷結果如下：
//中序遍歷
console.log("Inorder traversal: ");
inOrder(nums.root);
// Inorder traversal:
// 3 16 22 23 37 45 99
preOrder：先序遍歷
有了中序遍歷的基礎，相信先序遍歷的實現你已經想出來，怎么樣？看看對嗎？
//先序遍歷
function preOrder( node ) {
if( !(node == null )){
console.log( node.show() + ' ');
preOrder( node.left );
preOrder( node.right );
}
}
怎么樣，看起來是不是和中序遍歷差不多，唯一的區別就是 if 語句中代碼的執行順序，中序遍歷中 show 方法放在兩個遞歸調用之間，先序遍歷則放在遞歸調用之前。
先序遍歷結果如下：
// 先序遍歷
console.log("Preorder traversal: ");
preOrder(nums.root);
// Preorder traversal:
// 23 16 3 22 45 37 99
postOrder：后序遍歷
后序遍歷的實現和前面的基本相同，將 show 方法放在遞歸調用之后執行即可
//后序遍歷
function postOrder ( node ) {
if( !(node == null ) ){
postOrder( node.left );
postOrder( node.right );
console.log( node.show() + ' ');
}
}
后序遍歷結果如下：
// 后序遍歷
console.log("Postorder traversal: ");
postOrder(nums.root);
// Postorder traversal:
// 3 22 16 37 99 45 23
對于BST通常有一下三種的查找類型：
我們接下來一起來討論三種查找的方式的實現。
要查找BST中的最小值和最大值是非常簡單的。因為較小的值總是在左子節點上，要想查找BST中的最小值，只需遍歷左子樹，直到找到最后一個節點即可。同理，查找最大值，只需遍歷右子樹，直到找到最后一個節點即可。
getMin：查找最小值
遍歷左子樹，直到左子樹的某個節點的 left 為 null 時，該節點保存的即為最小值
//查找最小值
function getMin( ) {
var current = this.root;
while ( !( current.left == null ) ){
current = current.left;
}
return current.show();
}
getMax：查找最大值
遍歷右子樹，直到右子樹的某個節點的 right 為 null 時，該節點保存的即為最大值
//查找最大值
function getMax () {
var current = this.root;
while ( !( current.right == null ) ) {
current = current.right;
}
return current.show();
}
我們還是利用前面構建的樹來測試：
// 最小值
console.log('min:' + nums.getMin() ); // min : 3
//最大值
console.log('max:' + nums.getMax() ); // max : 99
在BST上查找給定值，需要比較給定值和當前節點保存的值的大小，通過比較，就能確定給定值在不在當前節點，根據BST的特點，qu接下來是向左還是向右遍歷；
//查找給定值
function find ( data ) {
var current = this.root;
while ( current != null ){
if( current.data == data ){
return current;
}else if( current.data < data ){
current = current.right;
}else{
current = current.left;
}
}
return null;
}
如果找到給定值，該方法返回保存該值的節點，反之返回null；
//查找不存在的值
console.log('find:' + nums.find(66)); // find : null
//查找存在的值
console.log('find:' + nums.find(99) ); // find : [object Object]
從BST中刪除節點的操作最為復雜，其復雜程度取決于刪除的節點位置。如果待刪除的節點沒有子節點，那么非常簡單。如果刪除包含左子節點或者右子節點，就變得稍微有些復雜。如果刪除包含兩個節點的節點最為復雜。
我們采用遞歸方法，來完成復雜的刪除操作，我們定義 remove() 和 removeNode() 兩個方法；算法思想如下：
因此，我們需要一個查找樹上最小值的方法，后面會用它找到最小值創建一個臨時節點，將臨時節點上的值復制到待刪除節點，然后再刪除臨時節點；
我們上面說會用到兩個方法，其中 remove 方法只是簡單的接收待刪除數據，調用 removeNode 刪除它，主要工作在 removeNode 中完成，定義如下：
//刪除操作
function remove( data ) {
removeNode( this.root , data);
}
//查找最小值
function getSmallest(node) {
if (node.left == null) {
return node;
}
else {
return getSmallest(node.left);
}
}
//刪除節點
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;
}
// 有2個子節點的節點
var tempNode = getSmallest(node.right);
node.data = tempNode.data;
node.right = removeNode(node.right,tempNode.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;
}
}
現在我們來刪除節點試試。
//刪除根節點 nums.remove(23); inOrder(nums.root); // 3 16 22 37 45 99
成功了！現在，我們的BST算是完整了。
我們現在已經可以利用js是實現一個簡單的BST了，實際中樹的使用會很廣泛，希望大家能多去了解了解樹的數據結構，多動手實踐，相信你會有不少的收獲！
感興趣的朋友可以使用在線HTML/CSS/JavaScript代碼運行工具：http://tools.jb51.net/code/HtmlJsRun測試上述代碼運行效果。
更多關于JavaScript相關內容感興趣的讀者可查看本站專題：《JavaScript數學運算用法總結》、《JavaScript數據結構與算法技巧總結》、《JavaScript數組操作技巧總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》
希望本文所述對大家JavaScript程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
