二叉樹的特點:

• 二叉樹是一種數(shù)據(jù)結(jié)構(gòu)。
• 由一系列節(jié)點組成，具有層級結(jié)構(gòu)。每個節(jié)點的特性包含有節(jié)點值，關(guān)系指針。節(jié)點之間存在對應(yīng)關(guān)系。
• 樹中存在一個沒有父節(jié)點的節(jié)點，叫做根節(jié)點。樹的末尾存在一系列沒有子節(jié)點的節(jié)點，成為葉子節(jié)點。其他可以叫做中間節(jié)點。
• 樹的根節(jié)點位于第一層，層級數(shù)越大，節(jié)點位置越深，層基數(shù)也叫做樹高。

二叉樹排序是二叉樹的一種類型，特點是:

• 節(jié)點分為左右子樹。
• 在不為空的情況下，左子樹子節(jié)點的值都小于父節(jié)點的值。

• 在不為空的情況下，右子樹子節(jié)點的值都大于父節(jié)點得值。

  
  
  二叉排序樹.png

代碼實現(xiàn)

節(jié)點用對象來描述，節(jié)點特性用對象屬性來描述。

//創(chuàng)建節(jié)點類
class Node {
    constructor(key) {
        this.key = key;//節(jié)點值
        this.left = null;//左指針
        this.right = null;//右指針
    }
}

二叉樹結(jié)構(gòu)用對象來描述。

class BinaryTree {
    constructor() {
        this.root = null;
    }
}

插入值

//插入
insert(key) {
    const newNode = new Node(key);
    if (this.root === null) {//設(shè)置根節(jié)點
        this.root = newNode;
    }
    this.insertNode(this.root, newNode);
}
insertNode(node, newNode) {
    if (newNode.key < node.key) {//插值小于節(jié)點值進入左子樹
        if (node.left === null) {//直到左子樹為空
            node.left = newNode
        } else {//左子樹已存在
            this.insertNode(node.left, newNode)
        }
    } else if (newNode.key > node.key){//插入值大于節(jié)點值進入右子樹
        if (node.right === null) {//直到右子樹為空
            node.right = newNode
        } else {//右子樹已存在
            this.insertNode(node.right, newNode)
        }
    }
}

使用方法

// 實例化二叉樹
const binaryTree = new BinaryTree();
// key值
const keys = [19, 8, 15, 24, 45, 12, 5];
// 生成二叉排序樹
keys.forEach(key => binaryTree.insert(key));

二叉排序樹的遍歷

中序遍歷

• 總是先遍歷左子樹，然后訪問根節(jié)點，接著遍歷右子樹

//中序遍歷
inorderTraversal() {
    let info = [];
    this.inorderTraversalNode(this.root, ({key}) => {
        info.push(key)
    });
    return info;
}
inorderTraversalNode(node, callback) {
    if (node) {//當(dāng)前節(jié)點
        this.inorderTraversalNode(node.left, callback);//遍歷左子樹
        callback(node);//訪問節(jié)點
        this.inorderTraversalNode(node.right, callback);//遍歷右子樹
    }
}
//遍歷結(jié)果：[5, 8, 12, 15, 19, 24, 45]

前序遍歷

• 總是先訪問根節(jié)點，然后遍歷左子樹，接著遍歷右子樹。

//前序遍歷
preOrderTraversal() {
    let info = [];
    this.preOrderTraversalNode(this.root, ({key}) => {
        info.push(key)
    });
    return info;
}
preOrderTraversalNode(node, callback) {
    if (node) {//當(dāng)前節(jié)點
        callback(node);//訪問節(jié)點
        this.preOrderTraversalNode(node.left, callback);//遍歷左子樹
        this.preOrderTraversalNode(node.right, callback);//遍歷右子樹
    }
}
//遍歷結(jié)果：[19,  8,  5, 15, 12, 24, 45]

后序遍歷

• 總是先遍歷左子樹，接著遍歷右子樹，最后訪問根節(jié)點。

//后序遍歷
postOrderTraversal() {
    let info = [];
    this.postOrderTraversalNode(this.root, ({key}) => {
        info.push(key)
    });
    return info;
}
postOrderTraversalNode(node, callback){
    if (node) {//當(dāng)前節(jié)點
        this.postOrderTraversalNode(node.left, callback);//遍歷左子樹
        this.postOrderTraversalNode(node.right, callback);//遍歷右子樹
        callback(node);//訪問節(jié)點
    }
}
//遍歷結(jié)果：[5, 12, 15, 8, 45, 24, 19]

二叉排序樹的查找

查找最大值

• 根據(jù)二叉排序樹的特點，右子樹的值都大于父節(jié)點得值。只需要進入節(jié)點的右子樹查找，當(dāng)某個節(jié)點的右子樹為空時，該節(jié)點就是最大值。

//最大值
max() {
    return this.maxNode(this.root)
}
maxNode(node) {
    if (node) {
        while (node.right !== null) {//右子樹不為空時
            node = node.right;
        }
        return node.key
    }
    return null
}

查找最小值

• 根據(jù)二叉排序樹的特點，左子樹的值都小于父節(jié)點的值。只需要進入節(jié)點的左子樹查找，當(dāng)某個節(jié)點的左子樹為空時，該節(jié)點就是最小值

//最小值
min() {
    return this.minNode(this.root)
}
minNode(node) {
    if (node) {
        while (node.left !== null) {//左子樹不為空時
            node = node.left;
        }
        return node.key
    }
    return null
}

查找指定值。

• 在二叉排序樹中查找有沒有節(jié)點對應(yīng)的值與給定值相同。
• 根據(jù)排序二叉樹的特點，比較給定值與節(jié)點值，小于時進入節(jié)點左子樹。大于時進入節(jié)點右子樹。等于時返回真。層層對比，最后如果子樹為空，則表示沒找到。

//查找
search(key) {
    return this.searchNode(this.root, key)
}
searchNode(node, key) {
    if (node === null) {
        return false
    }
    if (key < node.key) {//進入左子樹
        return this.searchNode(node.left, key)
    } else if (key > node.key) {//進入右子樹
        return this.searchNode(node.right, key)
    } else {//相等
        return true
    }
}

二叉排序樹的刪除

• 當(dāng)刪除的節(jié)點為葉子節(jié)點，關(guān)系指針為空，直接把葉子節(jié)點設(shè)置成空。
• 當(dāng)刪除的節(jié)點存在左子樹，把父節(jié)點的關(guān)系指針直接指向左子樹。存在右子樹同理。
• 當(dāng)刪除的節(jié)點存在左右子樹時，先去右子樹找最小值，然后用最小值替換節(jié)點值，最后進入右子樹刪除最小值對應(yīng)的節(jié)點。

//刪除
remove(key) {
    this.root = this.removeNode(this.root, key)
}
removeNode(node, key) {
    if (node === null) {//沒有找到值對應(yīng)節(jié)點
        return null
    }
    if (key < node.key) {//給定值小于當(dāng)前節(jié)點值
        node.left = this.removeNode(node.left, key);
        return node
    } else if (key > node.key) {//給定值大于當(dāng)前節(jié)點值
        node.right = this.removeNode(node.right, key);
        return node
    } else {//找到對應(yīng)的節(jié)點
        if (node.left === null && node.right === null) {//節(jié)點為葉子節(jié)點
            node = null;
            return node
        }
        if (node.right === null) {//節(jié)點存在左子樹
            node = node.left;
            return node
        } else if (node.left === null) {//節(jié)點存在右子樹
            node = node.right;
            return node
        }
        //節(jié)點存在左右子樹時，先去右子樹找最小值
        const minKey = this.minNode(node.right);
        //用最小值替換節(jié)點值
        node.key = minKey;
        //進入右子樹刪除最小值對應(yīng)的節(jié)點。
        this.removeNode(node.right, minKey);
        return node;
    }
}