Javascript 二叉搜索树

💡 知识点抢先看

• 什么是树结构？
• 树的相关术语
• 树结构有哪些类型
• 树的前中后序遍历
• 树的层序遍历
• 手写实现一颗树

一、什么是树结构？

树和哈希表一样是一种非顺序的数据结构，它对于存储需要快速查找的数据非常有用

树是一种分层抽象模型，可以理解为一层一层的，就类似于高中生物的遗传图谱

如下图所示

二、树的相关术语

根据上面的图，我们大致知道了树是一个怎样的数据结构，虽然对于实现它还一头雾水，现在我们先来了解一下关于树的相关术语

首先我们先列个表

术语	含义
节点	书中的每一个元素都叫节点
节点的深度	它的祖先节点的数量
树的高度	所有节点深度的最大值
内部节点	至少有一个子节点的节点
外部节点	没有子元素的节点
节点的度	节点拥有的子树个数
叶子节点	度为 0 的节点

接下来我们来详解一下这些分别是什么意思

首先位于树顶部的节点，称为根节点，它不存在父节点，也就是节点 1

树中的每一个元素都叫做节点

没有子元素的节点又叫做外部节点，例如图中的 4,5,7 这几个节点，它们都不存在子元素

剩下的节点都是内部节点

节点中有一个属性叫深度，它取决于祖先节点的数量，例如图中的节点5，它有2个祖先节点，分别是 2 和 1 ，因此它的深度就是2

对于一棵树而言，它有高度可言，高度取决于节点深度最大的值，也就是节点 7，它的深度是3，因此这颗树的高度为 3

节点的度，度表示的是节点拥有的子树的个数，例如节点1，有两颗子树，因此节点1的度为2，对于节点3而言，它只有一颗子树，因此节点3的度为1

对于叶子节点，也就是度为0的节点，也就是没有子树的节点，例如图中的节点 （4，5，7），这些都称做叶子节点

三、树结构有哪些类型

对于树来说它千变万化，它有着很多种形态，例如

最常见的二叉树，二叉搜索树

当然它还有

• 红黑树
• avl 树
• n 叉树
• 平衡二叉树...

还有很多种类型，这里主要就讲二叉树，因为其他的有点难，还没有学

二叉树：节点最多只能有两个子节点，一个是左侧节点，一个是右侧节点，如图就是一棵二叉树

二叉搜索树：左侧节点存储小的值，右侧节点存储大的值，因此也就是从左到右，从小到大，如图就是一棵二叉搜索树

四、树的前中后序遍历

对于树的遍历，我们有三种常规的方法，前序遍历，中序遍历，后序遍历

1. 前序遍历

前序遍历的顺序是：根节点 -> 左子节点 -> 右子节点，对于子树而言也是按照这个规律来遍历，如图所示

自己尝试用代码实现一下噢~~

2. 中序遍历

中序遍历的顺序是： 左子树 -> 根节点 -> 右子树，如图所示

递归代码实现

const inorder = (root) => {
    if(!root) { return }
    inorder(root.left)
    console.log(root.val);
    inorder(root.right)
}

3. 后序遍历

后序遍历的顺序是：左子树 -> 右子树 -> 根节点，如图所示

const postorder = (root) =>{
    if(!root) {return}
    // 先访问左子树，再访问右子树
    postorder(root.left)
    postorder(root.right)
    // 最后访问根节点
    console.log(root.val);
}

前序遍历代码如何实现呢？自己尝试一下吧~递归和迭代都可以试试噢

五、树的层序遍历

在 LeetCode 刷题中，经常会有这样的题目，需要按照层级来遍历，是什么意思呢

它的意思是：逐层地，从左到右访问所有节点

也就是按照图中的方式来遍历，并且返回结果

返回结果： [ [3], [9,20], [15,7] ]

也就是把每一层的元素放在一个数组中返回，如何实现呢？

• 首先我们需要在广度优先遍历的基础上，添加层级的判断
• 记录下当前层级的节点数，当当前层级遍历完成之后，从下一个数组继续遍历

var levelOrder = function (root) {
    //  空树
    if (!root) return []
    // 队列 广度优先遍历,[根节点,层级]
    const q = [
        root
    ]
    const res = []
    while (q.length) {
        // 记录一下当前有多少个节点是上一次循环遗留的,这些节点就是当前层级的全部节点
        let len = q.length
        res.push([])
        // 将这些节点全部出队
        while (len--) {
            const n = q.shift()
            res[res.length - 1].push(n.val)
            if (n.left) q.push(n.left)
            if (n.right) q.push(n.right)
        }
        // 在下一次的外层循环中,又会新创建一个新的空数组
    }
    return res
};

六、二叉搜索树有哪些方法？

在这里就罗列几个常见的方法吧

方法	作用
insert	向二叉搜索树中插入数据
serach	查找某个值
remove	移除某个值

还有很多比如返回最大值，返回最小值的方法，都可以实现，这里就不写那么多了

七、手写实现二叉搜索树

1. 创建 Node 类

创建一个节点类，用来实例化创建新节点，二叉搜索树最多只有两个节点

通过这个类来创建节点，默认为 null ，有 left，right 两个子节点都为 null

class Node {
    constructor(data = null, left = null, right = null){
        this.data = data
        this.left = left
        this.right = right
    }
}

2. 创建 BinarySearchTree 类

用来添加整棵树的方法

class BinarySearchTree {
    constructor() {
        this.root = null
    }
}

3. 实现 insert 方法

insert 方法实现插入一个元素，根据二叉搜多树的特性，左子树值小于右子树值，我们需要设计出合理的插入方式

• 首先我们需要创建一个新节点，并且传入 data 及节点数据
• 如果插入的是第一个节点，那么该节点就是根节点
• 如果不是第一个插入的节点，那么我们需要通过一个函数来辅助实现插入

insert(data) {
    const newNode = new Node(data)
    // insertNode为辅助函数
    this.root === null ? this.root = newNode : insertNode(this.root, newNode)
}

在这里我们写好了 insert 方法，简单的逻辑判断，根节点有无，接下来的处理交给 insertNode 函数来实现

如何实现呢？

根据二叉搜索树的特性，我们采用递归的方式

• 首先先判断传入的节点和根节点的大小关系
• 如果比根节点小，则放到左子树，反之
• 如果当前左（右）子树为空，则它直接成为左树第一个节点
• 如果不为空，我们接着比较它和左（或右）子树的大小关系，实现递归

function insertNode(node, newNode) {
    // 如果值小于根节点，插到左子树
    if (newNode.data < node?.data) {
        // 如果没有左子树，那么直接是左节点
        if (node.left === null) {
            node.left = newNode
        } else {
            // 递归
            insertNode(node.left, newNode)
        }
    }else {
        if(node.right === null) {
            node.right = newNode
        }else {
            insertNode(node.left,newNode)
        }
    }
}

这样我们就实现了一个 insert 方法，我们来看看如何使用吧~ 随便测试一下

const tree = new BinarySearchTree()
tree.insert(344)
tree.insert(31114)
tree.insert(324)
tree.insert(34)

看到调试器面板中的记录，符合我们的预期

我们再来看看插入是如何一步一步实现的吧~

const tree = new BinarySearchTree()
tree.insert(15)
tree.insert(31)
tree.insert(6)
tree.insert(48)

4. 实现 search 方法

search 方法需要接收一个查找的值，我们返回 true 或者 false ，这和之前的 has 方法类似，那我们该如何实现呢？

同样的我们需要借助一个辅助函数来实现

• 首先，我们先声明 search 方法，传入树和需要查找的值
• 当我们的树为空时，说明一定不可能查找到值
• 当查找的 data 小于根节点的 data 时，我们需要递归左子树继续判断
• 当大于根节点时，递归右子树判断
• 如果刚好等于根节点就返回 true

实现 search 方法

search(data) {
    return searchNode(this.root, data)
}

实现 searchNode 方法来实现查找

function searchNode(node, data) {
    if (node === null) {
        return false
    }
    if (data < node.data) {
        return searchNode(node.left, data)
    } else if (data > node.data) {
        return searchNode(node.right, data)
    } else {
        return true
    }
}

实现效果如何，我们来试试

const tree = new BinarySearchTree()
tree.insert(59)
tree.insert(29)
tree.insert(48)
tree.insert(18)
tree.insert(79)
tree.search(48)
tree.search(1)

5. 实现 remove 方法

remove 方法删除节点，这个方法是最复杂的一个方法，它要考虑的东西有很多

对于删除节点，可以分为三种类型

1. 删除叶子节点
2. 删除的节点只有一个子节点
3. 删除的节点有2个子节点

如何实现，我们一步步来看

首先我们需要实现一个 removeNode 函数，来保证我们的类中的干净，我们先声明这个 remove 方法，在这里我们预定 removeNode 需要返回根节点

remove(data) {
    this.root = removeNode(this.root, data)
}

来实现 removeNode 方法

首先我们先处理一些边界判断的工作

在这里我们先处理了空树的情况，当树为空时返回 null 即可，接着我们对需要删除的节点进行了搜索，这里利用的是递归实现的，当我们找到了这个节点时，当前的 node 就会指向了要删除的节点，然后进行判断

function removeNode(node, data) {
    if (node === null) return null
    if (data < node.data) {
        node.left = removeNode(node.left, key)
        return node
    } else if (data > node.key) {
        node.right = removeNode(node.right, key)
    } else {
        // 三个情况
    }
}

第一种情况：删除叶子节点，也就是 left,right 都为 null 时，可以直接删除，让当前节点 node = null 即可

if(node.left === null && node.right === null) {
    node = null
    return node
}

第二种情况：删除只有一个子节点的节点

这种情况下，我们需要跳过当前节点，指向它的子节点，也可以说是用子节点替代它的位置

if(node.left === null) {
    node = node.right
    return node
}else if(node.right === null) {
    node = node.left
    return node
}

第三种情况：删除两个子节点的节点

这种情况是最复杂的

1. 找到该节点的右子树中的最小值
2. 然后用这个最小值，去替代当前的这个被删除的节点
3. 之后我们需要删除右子树中的那个节点
4. 最后返回更新后节点的引用

在这里我们使用了一个自己封装的方法 findMinNode ，可以自己去试试如何实现，它的功能是，返回最小值的节点

const min = findMinNode(node.right)
node.data = min.data
node.right = removeNode(node.right,min.data)
return node

这样我们就实现了这三种情况的判断，结合起来就可以正常工作了

---

到这里我们实现了几个很常用的方法，难度还是蛮大的，需要自己多练练

八、LeetCode 实战

以下这些 leetcode 题可以去尝试一下

• 104. 二叉树的最大深度

• 111. 二叉树的最小深度

• 102. 二叉树的层序遍历

• 112. 路径总和

• 96. 不同的二叉搜索树

• 98. 验证二叉搜索树

• 99. 恢复二叉搜索树

• 226. 翻转二叉树

这篇文章转载于：学新通