二叉查找樹（Binary Sort Tree）

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

在樹結(jié)構(gòu)中妥色，每一個結(jié)點(diǎn)只有一個前件搪花，稱為父結(jié)點(diǎn)，沒有前件的結(jié)點(diǎn)只有一個嘹害，稱為樹的根結(jié)點(diǎn)撮竿，簡稱樹的根（root）。每一個結(jié)點(diǎn)可以有多個后件笔呀，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)幢踏。沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。一個結(jié)點(diǎn)所擁有的子結(jié)點(diǎn)的個數(shù)稱為該結(jié)點(diǎn)的度许师，所有結(jié)點(diǎn)中最大的度稱為樹的度房蝉。樹的最大層次稱為樹的深度。

二叉樹

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

二叉樹

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

按照根節(jié)點(diǎn)訪問的順序不同堡赔，樹的遍歷分為以下三種：前序遍歷，中序遍歷设联，后序遍歷善已；

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

先序遍歷

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

中序遍歷

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

后序遍歷

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

二叉查找樹（BST）

實(shí)際應(yīng)用中灼捂，樹的每個節(jié)點(diǎn)都會有一個與之相關(guān)的值對應(yīng)，有時候會被稱為鍵换团。因此悉稠，我們在構(gòu)建二叉查找樹的時候，確定子節(jié)點(diǎn)非常的重要艘包，通常將相對較小的值保存在左節(jié)點(diǎn)中的猛，較大的值保存在右節(jié)點(diǎn)中，這就使得查找的效率非常高想虎，因此被廣泛使用卦尊。

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

根據(jù)上面的知識，我們了解到二叉樹實(shí)際上是由多個節(jié)點(diǎn)組成舌厨，因此我們首先就要定義一個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)建一個類震庭，用來表示二叉查找數(shù)（BST），我們初始化類只包含一個成員你雌，一個表示二叉查找樹根節(jié)點(diǎn)的 Node 對象器联，初始化為 null ， 表示創(chuàng)建一個空節(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 方法氓栈，向樹中添加一個新節(jié)點(diǎn)渣磷，我們一起來看看這個方法；

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

因?yàn)樘砑庸?jié)點(diǎn)會涉及到插入位置的問題授瘦，必須將其放到正確的位置上醋界，才能保證樹的正確性，整個過程較為復(fù)雜提完，我們一起來梳理一下：

首先要添加新的節(jié)點(diǎn)形纺，首先需要創(chuàng)建一個Node對象，將數(shù)據(jù)傳入該對象徒欣。

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

如果待插入節(jié)點(diǎn)不是根節(jié)點(diǎn)级零，那么就必須對BST進(jìn)行遍歷，找到合適的位置始花。該過程類似遍歷鏈表妄讯，用一個變量存儲當(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)放到這個位置，退出循環(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)放到這個位置此虑，退出循環(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類已初步成型韭寸，但操作還僅僅限于插入節(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ù)后憨颠，會形成如下的二叉樹

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)想出來，怎么樣爽彤？看看對嗎养盗？

//先序遍歷

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

怎么樣，看起來是不是和中序遍歷差不多适篙，唯一的區(qū)別就是 if 語句中代碼的執(zhí)行順序往核，中序遍歷中 show 方法放在兩個遞歸調(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

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

對于BST通常有一下三種的查找類型：

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

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

要查找BST中的最小值和最大值是非常簡單的硫痰。因?yàn)檩^小的值總是在左子節(jié)點(diǎn)上衩婚，要想查找BST中的最小值，只需遍歷左子樹效斑，直到找到最后一個節(jié)點(diǎn)即可非春。同理，查找最大值缓屠，只需遍歷右子樹奇昙，直到找到最后一個節(jié)點(diǎn)即可。

getMin：查找最小值

遍歷左子樹敌完，直到左子樹的某個節(jié)點(diǎn)的 left 為 null 時储耐，該節(jié)點(diǎn)保存的即為最小值

//查找最小值

function getMin( ) {
    var current = this.root;
    while ( !( current.left == null ) ){
        current = current.left;
    }
    return current.show();
}

getMax：查找最大值

遍歷右子樹，直到右子樹的某個節(jié)點(diǎn)的 right 為 null 時滨溉，該節(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]

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

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

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

1. 首先判斷當(dāng)前節(jié)點(diǎn)是否包含待刪除的數(shù)據(jù)格遭，如果包含，則刪除該節(jié)點(diǎn)留瞳；如果不包含拒迅，則比較當(dāng)前節(jié)點(diǎn)上的數(shù)據(jù)和待刪除樹的的大小關(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)（沒有子節(jié)點(diǎn)）前硫，那么只需要將從父節(jié)點(diǎn)指向它的鏈接指向變?yōu)閚ull；
3. 如果待刪除節(jié)點(diǎn)含有一個子節(jié)點(diǎn)靶溜，那么原本指向它的節(jié)點(diǎn)需要做調(diào)整开瞭，使其指向它的子節(jié)點(diǎn)；
4. 最后罩息，如果待刪除節(jié)點(diǎn)包含兩個子節(jié)點(diǎn)嗤详，可以選擇查找待刪除節(jié)點(diǎn)左子樹上的最大值或者查找其右子樹上的最小值，這里我們選擇后一種瓷炮。

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

我們上面說會用到兩個方法烘绽，其中 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個子節(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)一個簡單的BST了，實(shí)際中樹的使用會很廣泛胡野，希望大家能多去了解了解樹的數(shù)據(jù)結(jié)構(gòu)材失，多動手實(shí)踐，相信你會有不少的收獲硫豆！