JavaScript的數(shù)據(jù)結(jié)構(gòu)與算法（五） —— 二叉搜索樹

Anshiii 發(fā)布于2019-08-21 17:14 / 3485人閱讀

摘要：簡(jiǎn)介二叉樹是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，很多其它數(shù)據(jù)結(jié)構(gòu)都是基于二叉樹的基礎(chǔ)演變而來的。二叉搜索樹是二叉樹的一種，但是它只允許你在左側(cè)節(jié)點(diǎn)存儲(chǔ)比父節(jié)點(diǎn)小的值，在右側(cè)節(jié)點(diǎn)存儲(chǔ)比父節(jié)點(diǎn)大或者等于的值。樹的高度，樹的高度體現(xiàn)為節(jié)點(diǎn)深度的最大值。

簡(jiǎn)介

二叉樹是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，很多其它數(shù)據(jù)結(jié)構(gòu)都是基于二叉樹的基礎(chǔ)演變而來的。

對(duì)于二叉樹，有深度遍歷和廣度遍歷，深度遍歷有前序、中序以及后序三種遍歷方法，廣度遍歷即我們平常所說的層次遍歷。因?yàn)闃涞亩x本身就是遞歸定義，因此采用遞歸的方法去實(shí)現(xiàn)樹的三種遍歷不僅容易理解而且代碼很簡(jiǎn)潔，而對(duì)于廣度遍歷來說，需要其他數(shù)據(jù)結(jié)構(gòu)的支撐，比如堆了。

二叉樹中的節(jié)點(diǎn)最多只能有兩個(gè)節(jié)點(diǎn)：一個(gè)是左側(cè)子節(jié)點(diǎn)，另一個(gè)是右側(cè)子節(jié)點(diǎn)。
二叉搜索樹（BST）是二叉樹的一種，但是它只允許你在左側(cè)節(jié)點(diǎn)存儲(chǔ)（比父節(jié)點(diǎn)）小的值，在右側(cè)節(jié)點(diǎn)存儲(chǔ)（比父節(jié)點(diǎn)）大（或者等于）的值。

節(jié)點(diǎn)簡(jiǎn)介

樹中的每個(gè)元素，都叫做節(jié)點(diǎn)。從節(jié)點(diǎn)延伸而下的，叫子節(jié)點(diǎn)。
樹頂部的節(jié)點(diǎn)叫根節(jié)點(diǎn)。每棵樹只有一個(gè)根節(jié)點(diǎn)。
在節(jié)點(diǎn)中，有子節(jié)點(diǎn)的節(jié)點(diǎn)也稱為內(nèi)部節(jié)點(diǎn)，沒有的話則被稱為外部節(jié)點(diǎn)或者葉節(jié)點(diǎn)。
同時(shí)在節(jié)點(diǎn)中是有祖先和后代關(guān)系的，比如節(jié)點(diǎn)9的祖先就有13,7,6,15四個(gè)。

節(jié)點(diǎn)屬性

深度: 節(jié)點(diǎn)的深度取決于其祖先的數(shù)量，節(jié)點(diǎn)9的深度就是4。
樹的高度，樹的高度體現(xiàn)為節(jié)點(diǎn)深度的最大值。
比如上圖，節(jié)點(diǎn)深度最大值為4，則樹的高度為4。

代碼實(shí)現(xiàn) 簡(jiǎn)單的二叉搜索樹

下面我們先來簡(jiǎn)單實(shí)現(xiàn)一個(gè)二叉搜索樹類，并包含以下的方法：

insert(key): 向樹中插入一個(gè)新的鍵

min(): 返回樹中最小的值

max(): 返回樹中最大的值

search(key): 搜索某個(gè)值，在樹中則返回true

remove(key): 從樹中移除某個(gè)鍵

代碼如下：

function BinarySearchTree() {
    var Node = function(key){ //數(shù)據(jù)結(jié)構(gòu)類
        this.key = key;
        this.left = null;
        this.right = null;
    };
    var root = null; //根節(jié)點(diǎn)
    this.insert = function(key){ //插入新的鍵
        var newNode = new Node(key);
        //special case - first element
        if (root === null){ //根節(jié)點(diǎn)為空，作為根節(jié)點(diǎn)
            root = newNode;
        } else {
            insertNode(root,newNode); //插入節(jié)點(diǎn)操作
        }
    };
    var insertNode = function(node, newNode){
        if (newNode.key < node.key){
            if (node.left === null){ //如果沒有左側(cè)節(jié)點(diǎn)就插入新的節(jié)點(diǎn)
                node.left = newNode;
            } else { //有的話遞歸
                insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null){  //如果沒有右側(cè)節(jié)點(diǎn)就插入新的節(jié)點(diǎn)
                node.right = newNode;
            } else { //有的話遞歸
                insertNode(node.right, newNode);
            }
        }
    };
    this.getRoot = function(){
        return root;
    };
    this.search = function(key){  //搜索鍵
        return searchNode(root, key); //搜索操作
    };
    var searchNode = function(node, key){
        if (node === null){
            return false;
        }
        if (key < node.key){ //如果小于繼續(xù)從左邊搜索
            return searchNode(node.left, key);
        } else if (key > node.key){ //如果大于繼續(xù)從右邊搜索
            return searchNode(node.right, key);
        } else { //命中
            return true;
        }
    };
    this.min = function() { //找最小鍵
        return minNode(root);
    };
    var minNode = function (node) {
        if (node){
            while (node && node.left !== null) {
                node = node.left;
            }
            return node.key;
        }
        return null;
    };
    this.max = function() { //找最大鍵
        return maxNode(root);
    };
    var maxNode = function (node) {
        if (node){
            while (node && node.right !== null) {
                node = node.right;
            }
            return node.key;
        }
        return null;
    };
    this.remove = function(element){
        root = removeNode(root, element);
    };
    var findMinNode = function(node){ //返回節(jié)點(diǎn)
        while (node && node.left !== null) {
            node = node.left;
        }
        return node;
    };
    var removeNode = function(node, element){ //移除一個(gè)節(jié)點(diǎn)
        if (node === null){
            return null;
        }
        if (element < node.key){
            node.left = removeNode(node.left, element);
            return node;
        } else if (element > node.key){
            node.right = removeNode(node.right, element);
            return node;
        } else { //命中后分三種情況         
            //移除葉子節(jié)點(diǎn)，即該節(jié)點(diǎn)沒有左側(cè)或者右側(cè)子節(jié)點(diǎn)的葉結(jié)點(diǎn)
            if (node.left === null && node.right === null){
                node = null;
                return node;
            }
            //移除有一個(gè)左側(cè)或者右側(cè)子節(jié)點(diǎn)的節(jié)點(diǎn)
            if (node.left === null){
                node = node.right; //把引用改為子節(jié)點(diǎn)的引用，下同
                return node;
            } else if (node.right === null){
                node = node.left;
                return node;
            }
            //移除有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
            var aux = findMinNode(node.right); //找到右邊子樹的最小節(jié)點(diǎn)
            node.key = aux.key; //改變節(jié)點(diǎn)的鍵，更新節(jié)點(diǎn)的值
            node.right = removeNode(node.right, aux.key); //移除有相同鍵的節(jié)點(diǎn)
            return node; //返回更新后節(jié)點(diǎn)的引用
        }
    };
}

二叉樹的遍歷

前序遍歷：根結(jié)點(diǎn) ---> 左子樹 ---> 右子樹
中序遍歷：左子樹---> 根結(jié)點(diǎn) ---> 右子樹
后序遍歷：左子樹 ---> 右子樹 ---> 根結(jié)點(diǎn)
層次遍歷：只需按層次遍歷即可

例如，求下面二叉樹的各種遍歷

前序遍歷：1 2 4 5 7 8 3 6
中序遍歷：4 2 7 5 8 1 3 6
后序遍歷：4 7 8 5 2 6 3 1
層次遍歷：1 2 3 4 5 6 7 8

前序遍歷

代碼實(shí)現(xiàn)如下：

/**
 * 先序遍歷
 * @param {any} callback 回調(diào)函數(shù)
 */
this.preOrderTranverse = function (callback) {
    preOrderTranverseNode(root, callback)
}
var preOrderTranverseNode = function (node, callback) {
    if (node !== null) {
        callback && callback(node.key);
        preOrderTranverseNode(node.left, callback);
        preOrderTranverseNode(node.right, callback);
    }
}

中序遍歷

代碼實(shí)現(xiàn)如下：
/**

中序遍歷

@param {any} callback 回調(diào)函數(shù)
*/

this.inOrderTraverse = function (callback) {

inOrderTraverseNode(root, callback)

}
var inOrderTraverseNode = function (node, callback) {

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

}

后序遍歷

代碼實(shí)現(xiàn)如下：

 /**
  * 后序遍歷
  * @param {any} callback 回調(diào)函數(shù)
  */
 this.postOrderTranverse = function (callback) {
     postOrderTranverseNode(root, callback);
 }
 var postOrderTranverseNode = function (node, callback) {
     if (node !== null) {
         postOrderTranverseNode(node.left, callback);
         postOrderTranverseNode(node.right, callback);
         callback(node.key);
     }
 }