本文實(shí)例講述了JS中的算法與數(shù)據(jù)結(jié)構(gòu)之二叉查找樹（Binary Sort Tree）。分享給大家供大家參考，具體如下：
我們之前所學(xué)到的列表，棧等都是一種線性的數(shù)據(jù)結(jié)構(gòu)，今天我們將學(xué)習(xí)計(jì)算機(jī)中經(jīng)常用到的一種非線性的數(shù)據(jù)結(jié)構(gòu)——樹（Tree），由于其存儲(chǔ)的所有元素之間具有明顯的層次特性，因此常被用來存儲(chǔ)具有層級關(guān)系的數(shù)據(jù)，比如文件系統(tǒng)中的文件；也會(huì)被用來存儲(chǔ)有序列表等。
在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)，簡稱樹的根（root）。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。一個(gè)結(jié)點(diǎn)所擁有的子結(jié)點(diǎn)的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹的度。樹的最大層次稱為樹的深度。
二叉樹是一種特殊的樹，它的子節(jié)點(diǎn)個(gè)數(shù)不超過兩個(gè)，且分別稱為該結(jié)點(diǎn)的左子樹（left subtree）與右子樹（right subtree），二叉樹常被用作二叉查找樹和二叉堆或是二叉排序樹（BST）。
二叉樹
按一定的規(guī)則和順序走遍二叉樹的所有結(jié)點(diǎn)，使每一個(gè)結(jié)點(diǎn)都被訪問一次，而且只被訪問一次，這個(gè)操作被稱為樹的遍歷，是對樹的一種最基本的運(yùn)算。由于二叉樹是非線性結(jié)構(gòu)，因此，樹的遍歷實(shí)質(zhì)上是將二叉樹的各個(gè)結(jié)點(diǎn)轉(zhuǎn)換成為一個(gè)線性序列來表示。
按照根節(jié)點(diǎn)訪問的順序不同，樹的遍歷分為以下三種：前序遍歷，中序遍歷，后序遍歷；
前序遍歷：根節(jié)點(diǎn)->左子樹->右子樹
先序遍歷
中序遍歷：左子樹->根節(jié)點(diǎn)->右子樹
中序遍歷
后序遍歷：左子樹->右子樹->根節(jié)點(diǎn)
后序遍歷
因此我們可以得之上面二叉樹的遍歷結(jié)果如下：前序遍歷：ABDEFGC 中序遍歷：DEBGFAC 后序遍歷：EDGFBCA
實(shí)際應(yīng)用中，樹的每個(gè)節(jié)點(diǎn)都會(huì)有一個(gè)與之相關(guān)的值對應(yīng)，有時(shí)候會(huì)被稱為鍵。因此，我們在構(gòu)建二叉查找樹的時(shí)候，確定子節(jié)點(diǎn)非常的重要，通常將相對較小的值保存在左節(jié)點(diǎn)中，較大的值保存在右節(jié)點(diǎn)中，這就使得查找的效率非常高，因此被廣泛使用。
根據(jù)上面的知識(shí)，我們了解到二叉樹實(shí)際上是由多個(gè)節(jié)點(diǎn)組成，因此我們首先就要定義一個(gè)Node類，用于存放樹的節(jié)點(diǎn)，其構(gòu)造與前面的鏈表類似。Node類的定義如下：
//節(jié)點(diǎn)定義function Node (data , left , right) { this.data = data; // 數(shù)據(jù) this.left = left; // 左節(jié)點(diǎn) this.right = right; // 右節(jié)點(diǎn) this.show = show; // 顯示節(jié)點(diǎn)數(shù)據(jù)}function show(){ return this.data;}Node對象既保存了數(shù)據(jù)，也保存了它的左節(jié)點(diǎn)和右節(jié)點(diǎn)的鏈接，其中 show 方法用來顯示當(dāng)前保存在節(jié)點(diǎn)中數(shù)據(jù)。
現(xiàn)在我們可以創(chuàng)建一個(gè)類，用來表示二叉查找數(shù)（BST），我們初始化類只包含一個(gè)成員，一個(gè)表示二叉查找樹根節(jié)點(diǎn)的 Node 對象，初始化為 null ， 表示創(chuàng)建一個(gè)空節(jié)點(diǎn)。
//二叉查找樹（BST）的類function BST(){ this.root = null; // 根節(jié)點(diǎn) this.insert = insert; // 插入節(jié)點(diǎn) this.preOrder = preOrder; // 先序遍歷 this.inOrder = inOrder; // 中序遍歷 this.postOrder = postOrder; // 后序遍歷 this.find = find; // 查找節(jié)點(diǎn) this.getMin = getMin; // 查找最小值 this.getMax = getMax; // 查找最大值 this.remove = remove; // 刪除節(jié)點(diǎn)}現(xiàn)在，我們需要為我們的類添加方法。
首先就是 insert 方法，向樹中添加一個(gè)新節(jié)點(diǎn)，我們一起來看看這個(gè)方法；
insert：向樹中添加新節(jié)點(diǎn)
因?yàn)樘砑庸?jié)點(diǎn)會(huì)涉及到插入位置的問題，必須將其放到正確的位置上，才能保證樹的正確性，整個(gè)過程較為復(fù)雜，我們一起來梳理一下：
首先要添加新的節(jié)點(diǎn)，首先需要?jiǎng)?chuàng)建一個(gè)Node對象，將數(shù)據(jù)傳入該對象。
其次要檢查當(dāng)前的BST樹是否有根節(jié)點(diǎn)，如果沒有，那么表示是一棵新數(shù)，該節(jié)點(diǎn)就為該樹的根節(jié)點(diǎn)，那么插入這個(gè)過程就結(jié)束了；否則，就要繼續(xù)進(jìn)行下一步了。
如果待插入節(jié)點(diǎn)不是根節(jié)點(diǎn)，那么就必須對BST進(jìn)行遍歷，找到合適的位置。該過程類似遍歷鏈表，用一個(gè)變量存儲(chǔ)當(dāng)前節(jié)點(diǎn)，一層一層遍歷BST，算法如下：
這樣，就能保證每次添加的新節(jié)點(diǎn)能夠放到正確的位置上，具體實(shí)現(xiàn)如下；
//插入新節(jié)點(diǎn)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; } } } }}現(xiàn)在BST類已初步成型，但操作還僅僅限于插入節(jié)點(diǎn)，我們需要有遍歷BST的能力，上面我們也提到了是三種遍歷方式。其中中序遍歷是最容易實(shí)現(xiàn)的，我們需要升序的方法訪問樹中的所有節(jié)點(diǎn)，先訪問左子樹，在訪問根節(jié)點(diǎn)，最后是右子樹，我們采用遞歸來實(shí)現(xiàn)！
inOrder：中序遍歷
// 中序遍歷 function inOrder (node) { if( !(node == null )){ inOrder( node.left ); console.debug( node.show() + ' '); inOrder( node.right ); }}怎么樣，了解了原理，實(shí)現(xiàn)起來還是蠻簡單的~
我們用一段代碼來測試一下我們所寫的中序遍歷：
var nums = new BST();//插入數(shù)據(jù)nums.insert(23);nums.insert(45);nums.insert(16);nums.insert(37);nums.insert(3);nums.insert(99);nums.insert(22);
上述插入數(shù)據(jù)后，會(huì)形成如下的二叉樹
BST
中序遍歷結(jié)果如下：
//中序遍歷console.log("Inorder traversal: ");inOrder(nums.root);// Inorder traversal:// 3 16 22 23 37 45 99preOrder：先序遍歷
有了中序遍歷的基礎(chǔ)，相信先序遍歷的實(shí)現(xiàn)你已經(jīng)想出來，怎么樣？看看對嗎？
//先序遍歷function preOrder( node ) { if( !(node == null )){ console.log( node.show() + ' '); preOrder( node.left ); preOrder( node.right ); } }怎么樣，看起來是不是和中序遍歷差不多，唯一的區(qū)別就是 if 語句中代碼的執(zhí)行順序，中序遍歷中 show 方法放在兩個(gè)遞歸調(diào)用之間，先序遍歷則放在遞歸調(diào)用之前。
先序遍歷結(jié)果如下：
// 先序遍歷console.log("Preorder traversal: ");preOrder(nums.root);// Preorder traversal:// 23 16 3 22 45 37 99postOrder：后序遍歷
后序遍歷的實(shí)現(xiàn)和前面的基本相同，將 show 方法放在遞歸調(diào)用之后執(zhí)行即可
//后序遍歷 function postOrder ( node ) { if( !(node == null ) ){ postOrder( node.left ); postOrder( node.right ); console.log( node.show() + ' '); }}后序遍歷結(jié)果如下：
// 后序遍歷console.log("Postorder traversal: ");postOrder(nums.root);// Postorder traversal:// 3 22 16 37 99 45 23對于BST通常有一下三種的查找類型：
我們接下來一起來討論三種查找的方式的實(shí)現(xiàn)。
要查找BST中的最小值和最大值是非常簡單的。因?yàn)檩^小的值總是在左子節(jié)點(diǎn)上，要想查找BST中的最小值，只需遍歷左子樹，直到找到最后一個(gè)節(jié)點(diǎn)即可。同理，查找最大值，只需遍歷右子樹，直到找到最后一個(gè)節(jié)點(diǎn)即可。
getMin：查找最小值
遍歷左子樹，直到左子樹的某個(gè)節(jié)點(diǎn)的 left 為 null 時(shí)，該節(jié)點(diǎn)保存的即為最小值
//查找最小值function getMin( ) { var current = this.root; while ( !( current.left == null ) ){ current = current.left; } return current.show();}getMax：查找最大值
遍歷右子樹，直到右子樹的某個(gè)節(jié)點(diǎn)的 right 為 null 時(shí)，該節(jié)點(diǎn)保存的即為最大值
//查找最大值 function getMax () { var current = this.root; while ( !( current.right == null ) ) { current = current.right; } return current.show();}我們還是利用前面構(gòu)建的樹來測試：
// 最小值console.log('min:' + nums.getMin() ); // min : 3//最大值console.log('max:' + nums.getMax() ); // max : 99在BST上查找給定值，需要比較給定值和當(dāng)前節(jié)點(diǎn)保存的值的大小，通過比較，就能確定給定值在不在當(dāng)前節(jié)點(diǎn)，根據(jù)BST的特點(diǎn)，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;}如果找到給定值，該方法返回保存該值的節(jié)點(diǎn)，反之返回null；
//查找不存在的值console.log('find:' + nums.find(66)); // find : null//查找存在的值console.log('find:' + nums.find(99) ); // find : [object Object]從BST中刪除節(jié)點(diǎn)的操作最為復(fù)雜，其復(fù)雜程度取決于刪除的節(jié)點(diǎn)位置。如果待刪除的節(jié)點(diǎn)沒有子節(jié)點(diǎn)，那么非常簡單。如果刪除包含左子節(jié)點(diǎn)或者右子節(jié)點(diǎn)，就變得稍微有些復(fù)雜。如果刪除包含兩個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)最為復(fù)雜。
我們采用遞歸方法，來完成復(fù)雜的刪除操作，我們定義 remove() 和 removeNode() 兩個(gè)方法；算法思想如下：
因此，我們需要一個(gè)查找樹上最小值的方法，后面會(huì)用它找到最小值創(chuàng)建一個(gè)臨時(shí)節(jié)點(diǎn)，將臨時(shí)節(jié)點(diǎn)上的值復(fù)制到待刪除節(jié)點(diǎn)，然后再刪除臨時(shí)節(jié)點(diǎn)；
我們上面說會(huì)用到兩個(gè)方法，其中 remove 方法只是簡單的接收待刪除數(shù)據(jù)，調(diào)用 removeNode 刪除它，主要工作在 removeNode 中完成，定義如下：
//刪除操作function remove( data ) { removeNode( this.root , data);}//查找最小值function getSmallest(node) { if (node.left == null) { return node; } else { return getSmallest(node.left); }}//刪除節(jié)點(diǎn)function removeNode( node , data ) { if( node == null ) { return null; } if(data == node.data) { // 沒有子節(jié)點(diǎn)的節(jié)點(diǎn) if(node.left == null && node.right == null) { return null; } // 沒有左子節(jié)點(diǎn)的節(jié)點(diǎn) if(node.left == null) { return node.right; } // 沒有右子節(jié)點(diǎn)的節(jié)點(diǎn) if(node.right == null) { return node.left; } // 有2個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn) 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; }}現(xiàn)在我們來刪除節(jié)點(diǎn)試試。
//刪除根節(jié)點(diǎn)nums.remove(23);inOrder(nums.root);// 3 16 22 37 45 99
成功了！現(xiàn)在，我們的BST算是完整了。
我們現(xiàn)在已經(jīng)可以利用js是實(shí)現(xiàn)一個(gè)簡單的BST了，實(shí)際中樹的使用會(huì)很廣泛，希望大家能多去了解了解樹的數(shù)據(jù)結(jié)構(gòu)，多動(dòng)手實(shí)踐，相信你會(huì)有不少的收獲！
希望本文所述對大家JavaScript程序設(shè)計(jì)有所幫助。
新聞熱點(diǎn)
疑難解答
