关于javascript:数据结构一文看懂二叉搜索树-JavaScript

二叉搜寻树介绍

1. 二叉搜寻树是一种节点值之间具备肯定数量级秩序的二叉树，对于树中每个节点：
2. 若其左子树存在，则其左子树中每个节点的值都不大于该节点值；
3. 若其右子树存在，则其右子树中每个节点的值都不小于该节点值。

满足条件

1. 若左子树不为空，则左子树上左右节点的值都小于根节点的值；
2. 若它的右子树不为空，则它的右子树上所有的节点的值都大于根节点的值；
3. 它的左右子树也要别离是二叉搜寻树；

查问节点过程是，比拟元素值是否相等，相等则返回，不相等则判断大小状况，迭代查问左、右子树，直到找到相等的元素，或子节点为空，返回节点不存在。

两种非凡的二叉树

齐全二叉树，所有节点尽量填满树的每一层，上一层填满后还有残余节点的话，则由左向右尽量填满下一层。

每一层只有一个节点的二叉树。

Node 节点实例

let Node = function (key) {
    this.key = key;
    this.left = null;
    this.right = null;
}
this.roots = null;

实例一个节点

let node = new Node()
console.log(node)
//{key: undefined, left: null, right: null}

1. 二叉树插入

1.1Node 节点实例

//Node 节点实例
function Node(key) {
    this.key = key;
    this.left = null;
    this.right = null;
}

1.2 二叉树对象

function BinarySearchTree() {
    this.roots = null;
    this.insert = insert
}

1.3 节点插入（三种状况）

因为二叉搜寻树的非凡性质确定了二叉搜寻树中每个元素只可能呈现一次，所以在插入的过程中如果发现这个元素曾经存在于二叉搜寻树中，就不进行插入。否则就查找适合的地位进行插入。

1.3.1 第一种状况：_root 为空

直接插入，return true；

let insert = function (key) {let newNode = new Node(key)
    if (this.roots === null) {this.roots = newNode}
}

1.3.2 第二种状况：要插入的元素曾经存在

如下面所说，如果在二叉搜寻树中曾经存在该元素，则不再进行插入，间接 return false；不再让它插入；

function insertNode(node, newNode) {if(newNode.key === node.key){return false}
}

节点插入测试

能够看到节点 2 没有反复插入;

let BST = new BinarySearchTree();
BST.insert(2)
BST.insert(2)
BST.insert(7)
BST.insert(3)
BST.insert(1)
console.log(BST)

1.3.3 第三种状况：可能找到适合地位

function insertNode(node, newNode) {if(newNode.key === node.key){return false}
    if (newNode.key < node.key) {
        // 如果新节点值小于以后节点值，则插入左子节点
        if (node.left === null) {node.left = newNode} else {insertNode(node.left, newNode)
        }
    } else {
        // 如果新节点值小于以后节点值，则插入右子节点
        if (node.right === null) {node.right = newNode} else {insertNode(node.right, newNode)
        }
    }
}

1.3.4 节点插入完整版

//Node 节点实例
function Node(key) {
    this.key = key;
    this.left = null;
    this.right = null;
}
// 二叉搜寻树
function BinarySearchTree() {
    this.roots = null;
    this.insert = insert
}
let insert = function (key) {let newNode = new Node(key)
    if (this.roots === null) {this.roots = newNode} else {insertNode(this.roots, newNode)
    }
}
function insertNode(node, newNode) {if(newNode.key === node.key){return false}
    if (newNode.key < node.key) {
        // 如果新节点值小于以后节点值，则插入左子节点
        if (node.left === null) {node.left = newNode} else {insertNode(node.left, newNode)
        }
    } else {
        // 如果新节点值小于以后节点值，则插入右子节点
        if (node.right === null) {node.right = newNode} else {insertNode(node.right, newNode)
        }
    }
}

let BST = new BinarySearchTree();
BST.insert(2)
BST.insert(6)
BST.insert(7)
BST.insert(3)
BST.insert(1)
console.log(BST)

2. 二叉树遍历（四种）

2.1 二叉树遍历类型

2.2 前序遍历

所谓的前序遍历就是先拜访根节点，再拜访左节点，最初拜访右节点。

那么遍历程序就是:8->4->2->6->12->9->15

实现

// 先序遍历是以优先于后辈节点的程序拜访每一个节点。let preOrderTraverse = function (callback) {preOrderTraverseNode(this.roots, callback)
}
function preOrderTraverseNode(node, callback) {if (node!==null) {callback(node.key)
        preOrderTraverseNode(node.left, callback)
        preOrderTraverseNode(node.right, callback)
    }
}
let BST = new BinarySearchTree();
let tree =[8,4,2,6,12,9,15]
tree.forEach(v=>{BST.insert(v)
})
BST.preOrderTraverse(key=>console.log(key)) //8,4,2,6,12,9,15

2.3 中序遍历

所谓的中序遍历就是先拜访左节点，再拜访根节点，最初拜访右节点。

那么程序是：2->4->6->8->9->12->15

实现

// 中序遍历是一种以从最小到最大的程序拜访所有节点的遍历形式
let inOrderTraverse = function (callback) {inOrderTraverseNode(this.roots, callback)
}
function inOrderTraverseNode(node, callback) {if (node !== null) {inOrderTraverseNode(node.left, callback)
        callback(node.key)
        inOrderTraverseNode(node.right, callback)
    }
}
let BST = new BinarySearchTree();
let tree = [8, 4, 2, 6, 12, 9, 15]
tree.forEach(v => {BST.insert(v)
})
BST.inOrderTraverse(key => console.log(key)) //2->4->6->8->9->12->15

2.4 后序遍历

所谓的后序遍历就是先拜访左节点，再拜访右节点，最初拜访根节点。

那么程序是:2->6->4->9->15->12->8

实现

// 后序遍历是先拜访节点的后辈节点，再拜访节点自身
let postOrderTraverse = function (callback) {postOrderTraverseNode(this.roots, callback)
}
function postOrderTraverseNode(node, callback) {if (node!==null) {postOrderTraverseNode(node.left, callback)
        postOrderTraverseNode(node.right, callback)
        callback(node.key)
    }
}

2.5 层序遍历

二叉树的层序遍历，即二叉树的广度遍历，先遍历根节点的相邻节点，再一次遍历相邻节点的子节点。广度遍历通常借助队列来实现。用队列来存储以后层的节点数，遍历以后层的节点，将以后层的节点顺次推入数组 subRes[]，再将以后节点的左右子节点推入队列中，进入下一层进行遍历，直到遍历完整棵树，即实现到二叉树的层序遍历。

图片来自 leetcode 题解：BFS 的应用场景总结：层序遍历、最短门路问题

十分的精彩，点赞！！！

实现

let levelOrder = function (root) {if (!root) return []
    let res = [] // 后果最外层数组
    let queue = [root]
    while (queue.length > 0) {
        var len = queue.length// 以后层的节点数目
        var subRes = []
        for (var i = 0; i < len; i++) {var node = queue.shift() // 节点出列
            subRes.push(node.val) // 将以后层的节点值退出 subRes 数组中
            // 将下一层节点计入队列中
            if (node.left) {queue.push(node.left)
            }
            if (node.right) {queue.push(node.right)
            }
        }
        res.push(subRes)
    }
    return res
};

具体的能够查看 leetcode 这道题的题解：102. 二叉树的层序遍历

3 二叉树搜寻

在 JavaScript 中咱们能够通过 hasOwnProperty 来检测指定 key 在对象是否存在，当初咱们在二叉搜寻中实现一个相似的办法，传入一个值 value 判断是否在二叉搜寻树中存在。

3.1 四种状况

1. 先判断传入的 node 是否为 null，如果为 null 就示意查找失败，返回 false。
2. 找到了节点，返回 true。
3. 要找的节点，比以后节点小，在左侧节点持续查找。
4. 要找的节点，比以后节点大，在右侧节点持续查找。

实现

let search = function (key) {searchNode(this.roots, key)
}
function searchNode(node, key) {
    // 查找失败，返回 false
    if (node === null) {return false;}
    // 比以后节点小，在左侧节点持续查找
    if (node.key > key) {searchNode(node.left, key)
    }
    // 比以后节点大，在右侧节点持续查找
    if (node.key < key) {searchNode(node.right, key)
    }
    return true;
}

4. 查找最小节点

查找最小值，往二叉树的左侧查找，直到该节点 left 为 null 没有左侧节点，证实其是最小值。

实现

// 最小值
function min() {return minNode(this.roots) || null
}
function minNode(node) {console.log(node)
    while (node !== null && node.left !== null) {node = node.left}
    return node.key
}

let BST = new BinarySearchTree();
let tree = [8, 4, 2, 6, 12, 9, 15]
tree.forEach(v => {BST.insert(v)
})
console.log(BST.min())  //2

5. 查找最大节点

查找最大值，往二叉树的右侧查找，直到该节点 right 为 null 没有右侧节点，证实其是最大值。

实现

// 最大值
let max = function () {return maxNode(this.roots) || null
}
function maxNode(node) {while (node !== null && node.right !== null) {node = node.right}
    return node.key
}

let BST = new BinarySearchTree();
let tree = [8, 4, 2, 6, 12, 9, 15]
tree.forEach(v => {BST.insert(v)
})
console.log(BST.max()) //15

6. 二叉树节点删除

1. 先判断节点是否为 null，如果等于 null 间接返回。
2. 判断要删除节点小于以后节点，往树的左侧查找
3. 判断要删除节点大于以后节点，往树的右侧查找

4. 节点已找到，另划分为四种状况:

   4.1. 以后节点即无左侧节点又无右侧节点，间接删除，返回 null

   4.2. 若左侧节点为 null，就证实它有右侧节点，将以后节点的援用改为右侧节点的援用，返回更新之后的值

   4.3. 若右侧节点为 null，就证实它有左侧节点，将以后节点的援用改为左侧节点的援用，返回更新之后的值

   4.4. 若左侧节点、右侧节点都不为空状况

实现

// 移除节点
let remove = function (key) {this.roots = removeNode(this.roots, key)
    console.log(this.roots)
}
function findMinNode(node, key) {while (node !== null && node.left !== null) {node = findMinNode(node.left, key);
    }
    return node;
}
function removeNode(node, key) {
    //1. 要删除节点小于以后节点，往树的左侧查找
    if (node.key > key) {node.left = removeNode(node.left, key);
        return node;
    }
    //2. 要删除节点大于以后节点，往树的右侧查找
    if (node.key < key) {node.right = removeNode(node.right, key);
        return node;
    }
    if (node.key === key) {
        //1. 以后节点即无左侧节点又无右侧节点，间接删除，返回 null
        if (node.left === null && node.right === null) {return null;}
        //2. 若右侧节点为 null，就证实它有左侧节点，将以后节点的援用改为左侧节点的援用，返回更新之后的值
        if (node.left !== null && node.right === null) {return node.left;}
        //3. 若左侧节点为 null，就证实它有右侧节点，将以后节点的援用改为右侧节点的援用，返回更新之后的值
        if (node.left === null && node.right !== null) {return node.right;}
        node.right = findMinNode(node.right, key);
        return node;
    }
}

let BST = new BinarySearchTree();
let tree = [8, 4, 2, 6, 12, 9, 15]
tree.forEach(v => {BST.insert(v)
})
console.log(BST.remove(15)) //15

7. 搜寻二叉树残缺的代码

// 根底类
function BinarySearchTree() {let Node = function (key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
    this.roots = null;
    // 二叉树插入
    this.insert = function (key) {let newNode = new Node(key)
        if (this.roots === null) {this.roots = newNode} else {insertNode(this.roots, newNode)
        }
    }
    function insertNode(node, newNode) {if (newNode.key < node.key) {
            // 如果新节点值小于以后节点值，则插入左子节点
            if (node.left === null) {node.left = newNode} else {insertNode(node.left, newNode)
            }
        } else {
            // 如果新节点值小于以后节点值，则插入右子节点
            if (node.right === null) {node.right = newNode} else {insertNode(node.right, newNode)
            }
        }
    }

    // 中序遍历是一种以从最小到最大的程序拜访所有节点的遍历形式
    this.inOrderTraverse = function (callback) {inOrderTraverseNode(this.roots, callback)
    }
    function inOrderTraverseNode(node, callback) {if (node !== null) {inOrderTraverseNode(node.left, callback)
            callback(node.key)
            inOrderTraverseNode(node.right, callback)
        }
    }
    // 先序遍历是以优先于后辈节点的程序拜访每一个节点。this.preOrderTraverse = function (callback) {preOrderTraverseNode(this.roots, callback)
    }
    function preOrderTraverseNode(node, callback) {if (node !== null) {callback(node.key)
            preOrderTraverseNode(node.left, callback)
            preOrderTraverseNode(node.right, callback)
        }
    }
    // 后序遍历是先拜访节点的后辈节点，再拜访节点自身
    this.postOrderTraverse = function (callback) {postOrderTraverseNode(this.roots, callback)
    }
    function postOrderTraverseNode(node, callback) {if (node !== null) {postOrderTraverseNode(node.left, callback)
            postOrderTraverseNode(node.right, callback)
            callback(node.key)
        }
    }

    // 搜寻二叉树
    this.search = function (key) {searchNode(this.roots, key)
    }
    function searchNode(node, key) {if (node === null) {return false;}
        if (node.key > key) {searchNode(node.left, key)
        }
        if (node.key < key) {searchNode(node.right, key)
        }
        return true;
    }
    // 最小值
    this.min = function () {minNode(this.roots)
    }
    function minNode(node) {while (node !== null && node.left !== null) {node = node.left}
        return node.key
    }
    // 最大值
    this.max = function () {maxNode(this.roots)
    }
    function maxNode(node) {while (node !== null && node.right !== null) {node = node.right}
        return node.key
    }
    // 移除节点
    this.remove = function (key) {this.roots = removeNode(this.roots, key)
    }
    function findMinNode(node, key) {while (node !== null && node.left !== null) {node = findMinNode(node.left, key);
        }
        return node;
    }
    function removeNode(node, key) {
        //1. 要删除节点小于以后节点，往树的左侧查找
        if (node.key > key) {node.left = removeNode(node.left, key);
            return node;
        }
        //2. 要删除节点大于以后节点，往树的右侧查找
        if (node.key < key) {node.right = removeNode(node.right, key);
            return node;
        }
        if (node.key === key) {
            //1. 以后节点即无左侧节点又无右侧节点，间接删除，返回 null
            if (node.left === null && node.right === null) {return null;}
            //2. 若右侧节点为 null，就证实它有左侧节点，将以后节点的援用改为左侧节点的援用，返回更新之后的值
            if (node.left !== null && node.right === null) {return node.left;}
            //3. 若左侧节点为 null，就证实它有右侧节点，将以后节点的援用改为右侧节点的援用，返回更新之后的值
            if (node.left === null && node.right !== null) {return node.right;}
            node.right = findMinNode(node.right, key);
            return node;
        }
    }
}
let nodeTree = [1, 12, 2, 3, 4, 5, 14, 6, 19];
let BST = new BinarySearchTree();

nodeTree.forEach(v => {BST.insert(v)
})
console.log(BST.remove(19))
console.log(BST.max())
console.log(BST.min())
console.log(BST.preOrderTraverse(key => console.log(key)))
console.log(BST.inOrderTraverse(key => console.log(key)))
console.log(BST.postOrderTraverse(key => console.log(key)))

8. 总结

样的数据，不同的插入程序，树的后果是不一样的。这就是二叉树的局限性。同时节点过多时，会比拟耗费性能。有啥问题能够评论区留言，一起学习，一起精进。也能够 拜访集体博客地址。叫我詹躲躲

在线 DEMO 地址在线 DEMO 地址

9. 参考资料

1. 二叉树查找与节点删除的 javascript 实现

2. 二叉树的 javascript 实现

3.JavaScript 二叉树深刻了解

4. 数据结构（二）：二叉搜寻树（Binary Search Tree）

5. 实现一个二叉搜寻树（JavaScript 版）

6. 二叉搜寻树的插入与删除图解

7. 二叉树的四种遍历形式

8.102. 二叉树的层序遍历