📢 大家好，我是小丞同学，一名大二的前端爱好者

📢 这篇文章将讲解数据结构中的树

📢 非常感谢你的阅读，不对的地方欢迎指正 🙏

📢 愿你忠于自己，热爱生活

💡 知识点抢先看 ​

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

一、什么是树结构？ ​

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

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

如下图所示

二、树的相关术语 ​

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

首先我们先列个表

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

首先位于树顶部的节点，称为根节点，它不存在父节点，也就是节点 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
};

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

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

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

七、手写实现二叉搜索树 ​

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. 翻转二叉树 ​

这些题都可以去尝试一下哦~

📖 总结 ​

在这篇文章中我们从什么是树开始，最后封装了一颗二叉搜索树，难度还是有的，做树相关的题目，必须要理顺我们的思路，采用递归要确定好递归顺序。在我们做题的时候，不必封装一个完整的树，只需要我们知道有这个数据结构，在我们需要使用的时候，我们提取它的灵魂即可，学了这么多的数据结构，也能发现，它们都是通过数组或者对象封装而成的，因此它们的本质还是我们最熟悉的东西。

本文关于树的内容就到这里结束了，相信你一定能从中学到很多东西。下一篇文章将带你探索堆的奥秘。

欢迎大家关注本专栏，持续关注最新文章~

最后，可能在很多地方讲诉的不够清晰，请见谅

💌 如果文章有什么错误的地方，或者有什么疑问，欢迎留言，也欢迎私信交流