本文實(shí)例講述了JS中的算法與數(shù)據(jù)結(jié)構(gòu)之二叉查找樹(shù)（Binary Sort Tree）。分享給大家供大家參考，具體如下：

二叉查找樹(shù)（Binary Sort Tree）

我們之前所學(xué)到的列表，棧等都是一種線性的數(shù)據(jù)結(jié)構(gòu)，今天我們將學(xué)習(xí)計(jì)算機(jī)中經(jīng)常用到的一種非線性的數(shù)據(jù)結(jié)構(gòu)——樹(shù)（Tree），由于其存儲(chǔ)的所有元素之間具有明顯的層次特性，因此常被用來(lái)存儲(chǔ)具有層級(jí)關(guān)系的數(shù)據(jù)，比如文件系統(tǒng)中的文件；也會(huì)被用來(lái)存儲(chǔ)有序列表等。

在樹(shù)結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)，沒(méi)有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹(shù)的根結(jié)點(diǎn)，簡(jiǎn)稱樹(shù)的根（root）。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。一個(gè)結(jié)點(diǎn)所擁有的子結(jié)點(diǎn)的個(gè)數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹(shù)的度。樹(shù)的最大層次稱為樹(shù)的深度。

二叉樹(shù)

二叉樹(shù)是一種特殊的樹(shù)，它的子節(jié)點(diǎn)個(gè)數(shù)不超過(guò)兩個(gè)，且分別稱為該結(jié)點(diǎn)的左子樹(shù)（left subtree）與右子樹(shù)（right subtree），二叉樹(shù)常被用作二叉查找樹(shù)和二叉堆或是二叉排序樹(shù)（BST）。

 
二叉樹(shù)

按一定的規(guī)則和順序走遍二叉樹(shù)的所有結(jié)點(diǎn)，使每一個(gè)結(jié)點(diǎn)都被訪問(wèn)一次，而且只被訪問(wèn)一次，這個(gè)操作被稱為樹(shù)的遍歷，是對(duì)樹(shù)的一種最基本的運(yùn)算。由于二叉樹(shù)是非線性結(jié)構(gòu)，因此，樹(shù)的遍歷實(shí)質(zhì)上是將二叉樹(shù)的各個(gè)結(jié)點(diǎn)轉(zhuǎn)換成為一個(gè)線性序列來(lái)表示。

按照根節(jié)點(diǎn)訪問(wèn)的順序不同，樹(shù)的遍歷分為以下三種：前序遍歷，中序遍歷，后序遍歷；

前序遍歷：根節(jié)點(diǎn)->左子樹(shù)->右子樹(shù)

 
先序遍歷

中序遍歷：左子樹(shù)->根節(jié)點(diǎn)->右子樹(shù)

 
中序遍歷

后序遍歷：左子樹(shù)->右子樹(shù)->根節(jié)點(diǎn)

 
后序遍歷

因此我們可以得之上面二叉樹(shù)的遍歷結(jié)果如下：前序遍歷：ABDEFGC 中序遍歷：DEBGFAC 后序遍歷：EDGFBCA

二叉查找樹(shù)（BST）

實(shí)際應(yīng)用中，樹(shù)的每個(gè)節(jié)點(diǎn)都會(huì)有一個(gè)與之相關(guān)的值對(duì)應(yīng)，有時(shí)候會(huì)被稱為鍵。因此，我們?cè)跇?gòu)建二叉查找樹(shù)的時(shí)候，確定子節(jié)點(diǎn)非常的重要，通常將相對(duì)較小的值保存在左節(jié)點(diǎn)中，較大的值保存在右節(jié)點(diǎn)中，這就使得查找的效率非常高，因此被廣泛使用。

二叉查找樹(shù)的實(shí)現(xiàn)

根據(jù)上面的知識(shí)，我們了解到二叉樹(shù)實(shí)際上是由多個(gè)節(jié)點(diǎn)組成，因此我們首先就要定義一個(gè)Node類(lèi)，用于存放樹(shù)的節(jié)點(diǎn)，其構(gòu)造與前面的鏈表類(lèi)似。Node類(lèi)的定義如下：

//節(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對(duì)象既保存了數(shù)據(jù)，也保存了它的左節(jié)點(diǎn)和右節(jié)點(diǎn)的鏈接，其中 show 方法用來(lái)顯示當(dāng)前保存在節(jié)點(diǎn)中數(shù)據(jù)。

現(xiàn)在我們可以創(chuàng)建一個(gè)類(lèi)，用來(lái)表示二叉查找數(shù)（BST），我們初始化類(lèi)只包含一個(gè)成員，一個(gè)表示二叉查找樹(shù)根節(jié)點(diǎn)的 Node 對(duì)象，初始化為 null ， 表示創(chuàng)建一個(gè)空節(jié)點(diǎn)。

//二叉查找樹(shù)（BST）的類(lèi)

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)在，我們需要為我們的類(lèi)添加方法。

首先就是 insert 方法，向樹(shù)中添加一個(gè)新節(jié)點(diǎn)，我們一起來(lái)看看這個(gè)方法；

insert：向樹(shù)中添加新節(jié)點(diǎn)

因?yàn)樘砑庸?jié)點(diǎn)會(huì)涉及到插入位置的問(wèn)題，必須將其放到正確的位置上，才能保證樹(shù)的正確性，整個(gè)過(guò)程較為復(fù)雜，我們一起來(lái)梳理一下：

首先要添加新的節(jié)點(diǎn)，首先需要?jiǎng)?chuàng)建一個(gè)Node對(duì)象，將數(shù)據(jù)傳入該對(duì)象。

其次要檢查當(dāng)前的BST樹(shù)是否有根節(jié)點(diǎn)，如果沒(méi)有，那么表示是一棵新數(shù)，該節(jié)點(diǎn)就為該樹(shù)的根節(jié)點(diǎn)，那么插入這個(gè)過(guò)程就結(jié)束了；否則，就要繼續(xù)進(jìn)行下一步了。

如果待插入節(jié)點(diǎn)不是根節(jié)點(diǎn)，那么就必須對(duì)BST進(jìn)行遍歷，找到合適的位置。該過(guò)程類(lèi)似遍歷鏈表，用一個(gè)變量存儲(chǔ)當(dāng)前節(jié)點(diǎn)，一層一層遍歷BST，算法如下：

1. 設(shè)值當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)
2. 如果待插入節(jié)點(diǎn)保存的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)，則新節(jié)點(diǎn)為原節(jié)點(diǎn)的左節(jié)點(diǎn)，反之，執(zhí)行第4步
3. 如果當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)為null，就將新節(jié)點(diǎn)放到這個(gè)位置，退出循環(huán)；反之，繼續(xù)執(zhí)行下一次循環(huán)
4. 設(shè)置新節(jié)點(diǎn)為原節(jié)點(diǎn)的右節(jié)點(diǎn)
5. 如果當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)為null，就將新節(jié)點(diǎn)放到這個(gè)位置，退出循環(huán)；反之，繼續(xù)執(zhí)行下一次循環(huán)

這樣，就能保證每次添加的新節(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類(lèi)已初步成型，但操作還僅僅限于插入節(jié)點(diǎn)，我們需要有遍歷BST的能力，上面我們也提到了是三種遍歷方式。其中中序遍歷是最容易實(shí)現(xiàn)的，我們需要升序的方法訪問(wèn)樹(shù)中的所有節(jié)點(diǎn)，先訪問(wèn)左子樹(shù)，在訪問(wèn)根節(jié)點(diǎn)，最后是右子樹(shù)，我們采用遞歸來(lái)實(shí)現(xiàn)！

inOrder：中序遍歷

 // 中序遍歷
 
function inOrder (node) {
  if( !(node == null )){
    inOrder( node.left );
    console.debug( node.show() + ' ');
    inOrder( node.right );
  }
}

怎么樣，了解了原理，實(shí)現(xiàn)起來(lái)還是蠻簡(jiǎn)單的~

我們用一段代碼來(lái)測(cè)試一下我們所寫(xiě)的中序遍歷：

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ì)形成如下的二叉樹(shù)

 
BST

中序遍歷結(jié)果如下：

//中序遍歷
console.log("Inorder traversal: ");
inOrder(nums.root);

// Inorder traversal:
// 3 16 22 23 37 45 99

preOrder：先序遍歷

有了中序遍歷的基礎(chǔ)，相信先序遍歷的實(shí)現(xiàn)你已經(jīng)想出來(lái)，怎么樣？看看對(duì)嗎？

//先序遍歷

function preOrder( node ) {
  if( !(node == null )){
    console.log( node.show() + ' ');
    preOrder( node.left );
    preOrder( node.right );
  } 
}

怎么樣，看起來(lái)是不是和中序遍歷差不多，唯一的區(qū)別就是 if 語(yǔ)句中代碼的執(zhí)行順序，中序遍歷中 show 方法放在兩個(gè)遞歸調(diào)用之間，先序遍歷則放在遞歸調(diào)用之前。

先序遍歷結(jié)果如下：

// 先序遍歷

console.log("Preorder traversal: ");
preOrder(nums.root);

// Preorder traversal:
// 23 16 3 22 45 37 99

postOrder：后序遍歷

后序遍歷的實(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

二叉查找樹(shù)的查找運(yùn)算

對(duì)于BST通常有一下三種的查找類(lèi)型：

1. 查找給定值
2. 查找最大值
3. 查找最小值

我們接下來(lái)一起來(lái)討論三種查找的方式的實(shí)現(xiàn)。

要查找BST中的最小值和最大值是非常簡(jiǎn)單的。因?yàn)檩^小的值總是在左子節(jié)點(diǎn)上，要想查找BST中的最小值，只需遍歷左子樹(shù)，直到找到最后一個(gè)節(jié)點(diǎn)即可。同理，查找最大值，只需遍歷右子樹(shù)，直到找到最后一個(gè)節(jié)點(diǎn)即可。

getMin：查找最小值

遍歷左子樹(shù)，直到左子樹(shù)的某個(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：查找最大值

遍歷右子樹(shù)，直到右子樹(shù)的某個(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)建的樹(shù)來(lái)測(cè)試：

// 最小值
console.log('min:' + nums.getMin() );    // min : 3

//最大值
console.log('max:' + nums.getMax() );    // max : 99

在BST上查找給定值，需要比較給定值和當(dāng)前節(jié)點(diǎn)保存的值的大小，通過(guò)比較，就能確定給定值在不在當(dāng)前節(jié)點(diǎn)，根據(jù)BST的特點(diǎn)，qu接下來(lái)是向左還是向右遍歷；

//查找給定值

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]

二叉查找樹(shù)的刪除運(yùn)算

從BST中刪除節(jié)點(diǎn)的操作最為復(fù)雜，其復(fù)雜程度取決于刪除的節(jié)點(diǎn)位置。如果待刪除的節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)，那么非常簡(jiǎn)單。如果刪除包含左子節(jié)點(diǎn)或者右子節(jié)點(diǎn)，就變得稍微有些復(fù)雜。如果刪除包含兩個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)最為復(fù)雜。

我們采用遞歸方法，來(lái)完成復(fù)雜的刪除操作，我們定義 remove() 和 removeNode() 兩個(gè)方法；算法思想如下：

1. 首先判斷當(dāng)前節(jié)點(diǎn)是否包含待刪除的數(shù)據(jù)，如果包含，則刪除該節(jié)點(diǎn)；如果不包含，則比較當(dāng)前節(jié)點(diǎn)上的數(shù)據(jù)和待刪除樹(shù)的的大小關(guān)系。如果待刪除的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)，則移至當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)繼續(xù)比較；如果大于，則移至當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)繼續(xù)比較。
2. 如果待刪除節(jié)點(diǎn)是葉子節(jié)點(diǎn)（沒(méi)有子節(jié)點(diǎn)），那么只需要將從父節(jié)點(diǎn)指向它的鏈接指向變?yōu)閚ull；
3. 如果待刪除節(jié)點(diǎn)含有一個(gè)子節(jié)點(diǎn)，那么原本指向它的節(jié)點(diǎn)需要做調(diào)整，使其指向它的子節(jié)點(diǎn)；
4. 最后，如果待刪除節(jié)點(diǎn)包含兩個(gè)子節(jié)點(diǎn)，可以選擇查找待刪除節(jié)點(diǎn)左子樹(shù)上的最大值或者查找其右子樹(shù)上的最小值，這里我們選擇后一種。

因此，我們需要一個(gè)查找樹(shù)上最小值的方法，后面會(huì)用它找到最小值創(chuàng)建一個(gè)臨時(shí)節(jié)點(diǎn)，將臨時(shí)節(jié)點(diǎn)上的值復(fù)制到待刪除節(jié)點(diǎn)，然后再刪除臨時(shí)節(jié)點(diǎn)；

我們上面說(shuō)會(huì)用到兩個(gè)方法，其中 remove 方法只是簡(jiǎn)單的接收待刪除數(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) {
    // 沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)
    if(node.left == null && node.right == null) {
      return null;
    }
    // 沒(méi)有左子節(jié)點(diǎn)的節(jié)點(diǎn)
    if(node.left == null) {
      return node.right;
    }
    // 沒(méi)有右子節(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)在我們來(lái)刪除節(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è)簡(jiǎn)單的BST了，實(shí)際中樹(shù)的使用會(huì)很廣泛，希望大家能多去了解了解樹(shù)的數(shù)據(jù)結(jié)構(gòu)，多動(dòng)手實(shí)踐，相信你會(huì)有不少的收獲！

感興趣的朋友可以使用在線HTML/CSS/JavaScript代碼運(yùn)行工具：http://tools.jb51.net/code/HtmlJsRun測(cè)試上述代碼運(yùn)行效果。

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專(zhuān)題：《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)組操作技巧總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》

希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。

最新評(píng)論