数据结构（七）树

数据结构（七）树

1. 定义

树结构

根节点：位于树顶部的节点，没有父节点 =》10

内部节点：至少有一个子节点的节点称为内部节点 =》7、5、9、15、13 、20

外部节点：没有子元素的节点称为外部节点或叶节点 =》3、6、8、10、12、14、18 、25

子树：由节点和它的后代构成

深度：祖先节点的数量 =》3 有3 个祖先节点（5、7 、11），深度为3

二叉树：节点最多只能有两个：左侧子节点+右侧子节点

可以更高效地在树中插入、查找和删除节点

二叉树在计算机科学中的应用非常广泛

二叉搜索树BST：二叉树的一种，只允许你在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大的值

2. 具体操作

二叉搜索树

创建

1
2
3
4
5
6
7
8
9
10
11
12
13
class Node {
    constructor(key){
        this.key = key;
        this.left = null;
        this.right = null;
    }
}
class BinarySearchTree {
    construtor(compareFn = defaultCompare) {
        this.compareFn = compareFn;  //用来比较节点值
        this.root = null;
    }
}

方法

  • insert(key)：向树中插入一个新的

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    insert(key){
        if(this.root == null) {  // 先检查根节点，没有就直接new一个
            this.root = new Node(key);
        } else {
            this.insertNode(this.root,key);
        }
    }

    inserNode(node, key) {
        if(this.compareFn(key, node.key) === Compare.LESS_THAN) {
            if(node.left = null) {   // 先检查左侧子节点，没有则新建一个
                node.left = new Node(key);
            } else {
                this.inserNode(node.left, key);
            }
        } else {
            if (node.right == null) {  // 节点的键比当前节点的键大，同时当前节点没有右侧子节点
                node.right = new Node(key);
            } else {  // 新节点的键小于当前节点的键，那么需要检查当前节点的左侧子节点
                this.insertNode(node.right, key);
            }
        }
    }

  • search(key)：在树中查找一个键。如果节点存在，则返回true；如果不存在，则返回false

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    search(key) {
        return this.searchNode(this.root, key);
    }
    searchNode(node, key) {
        if (node == null) {  // 节点为空时，返回false
            return false;
        }
        // 要找的键比当前的节点小，到左支找
        if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
            return this.searchNode(node.left, key);
        // 果要找的键比当前的节点大，到右支找
        } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
            return this.searchNode(node.right, key);
        } else {
            return true;
        }
    }

  • inOrderTraverse()：通过中序遍历BST方式遍历所有节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    inOrderTraverse(callback) {
        this.inOrderTraverseNode(this.root, callback);
    }

    inOrderTraverseNode(node, callback) {  // 使用递归，判断传入的节点是否为空
        if (node != null) {
            this.inOrderTraverseNode(node.left, callback);
            callback(node.key);
            this.inOrderTraverseNode(node.right, callback);
        }
    }

    inOrderTraverse方法的访问路径

  • preOrderTraverse()：通过先序遍历方式遍历所有节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    preOrderTraverse(callback) {
        this.preOrderTraverseNode(this.root,callback)
    }

    preOrderTraverseNode(node,callback){
        if(node != null) {
            callback(node.key);
            this.proOrderTraverseNode(node.left, callback);
            this.proOrderTraverseNode(node.right, callback);
        }
    }

    preOrderTraverse方法的访问路径

  • postOrderTraverse()：通过后序遍历方式遍历所有节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    postOrderTraverse(callback) {
        this.postOrderTraverseNode(this.root, callback);
    }
    postOrderTraverseNode(node, callback) {
        if(node != null) {
            this.postOrderTraverseNode(node.left, callback);
            this.postOrderTraverseNode(node.right, callback);
            callback(node.key);
        }
    }

    postOrderTraverse方法的访问路径

  • min()：返回树中最小的值/键

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    min() {
        return this.minNode(this.root);
    }
    minNode(node) {
        let current = node;
        while (current != null && current.left != null) {
            current = current.left
        }
        return current;
    }

  • max()：返回树中最大的值/键

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    max() {
        return this.maxNode(this.root);
    }
    maxNode(node) {
        let current = node;
        while (current != null && current.right != null) {
            current = current.right
        }
        return current;
    }

  • remove(key)：从树中移除某个键

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    remove(key) {
        this.root = this.removeNode(this.root, key)
    }
    removeNode(node, key) {
        if(node == null) {
            return null;
        }
        if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
            node.left = this.removeNode(node.left, key);
            return node;
        } else if (this.compareFn(key,node.key) === Compare.BIGGER__THAN) {
            node.right = this.removeNode(node.right, key);
            return node;
        } else {
            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;
            }
            // 左右支都有
            const aux = this.minNode(node.right);
            node.key = aux.key;
            node.right = this.removeNode(node.right, aux.key);
            return node;
        }
    }

    移除有两个子节点的节点的过程

3. 树和前端

一种分层数据的抽象模型

前端工作中常见的树包括：DOM树、级联选择、树形控件……

JS没有树，用 Object 和 Array 构建树

树的常见操作：深度/广度优先遍历、先中后序遍历

遍历JSON的所有节点值

1
2
3
4
5
6
7
8
9
10
11
12
const json = {
    a: {b: {c: 1}},
    d: [1, 2],
};

const dfs = (node, path) => {
    console.log(node, path);
    Object.keys(node).forEach(k => {
        dfs(node[k], path.concat(k))
    });
};
dfs(json, [])

4. 深度/广度优先遍历

  • 深度优先遍历：尽可能深的搜索树的分支

    • 访问根节点

    • 对根节点的children挨个进行深度优先遍历

      递归

    1
    2
    3
    4
    5
    6
    // dfs
    const tree = {...}
    const dfs = (root) => {
        root.children.forEach(dfs);
    }
    dfs(tree)

  • 广度优先遍历：先访问离根节点最近的节点

    • 新建一个队列，把根节点入队
    • 把队头出队并访问
    • 把队头的children挨个入队
    • 重复第二三步，直到队列为空
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // bfs
    const tree = {...}
    const bfs = (root) => {
        const queue = [root];
        while(queue.length > 0) {
            const node = queue.shift();
            node.children.forEach(child => {
                queue.push(child);
            })
        }
    }

我们可以比喻成看书，深度优先遍历就是从第一章标题开始看，然后看第一章内容（深度）；而广度优先遍历就是先看这本书的各章标题，也就是目录，然后按照顺序看各章的内容（广度）

5. 二叉树

树中每个节点最多只能有两个子节点

在js中通常使用Object来模拟二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
const binaryTree = {
    val: 1,
    left: {
        val: 2,
        left: null,
        right: null
    },
    right: {
        val: 3,
        left: null,
        right: null
    }
}

6. 先中后序遍历

  • 先序遍历
    • 访问根节点
    • 对根节点的左子树进行先序遍历
    • 对根节点的右子树进行先序遍历
    1
    2
    3
    4
    5
    6
    7
    8
    const bt = {...}
    const preorder = (root) => {
        if(!root) return;
        console.log(root);
        preorder(root.left);
        preorder(root.right);
    }
    preorder()
  • 中序遍历
    • 对根节点的左子树进行中序遍历
    • 访问根节点
    • 对根节点的右子树进行中序遍历
    1
    2
    3
    4
    5
    6
    7
    8
    const bt = {...}
    const inorder = (root) => {
        if(!root) return;
        inorder(root.left);
        console.log(root);
        inorder(root.right);
    }
    inorder()
  • 后序遍历
    • 对根节点的左子树进行后序遍历
    • 对根节点的右子树进行后序遍历
    • 访问根节点
    1
    2
    3
    4
    5
    6
    7
    const bt = {...}
    const postorder = (root) => {
        if(!root) return;
        postorder(root.left);
        postorder(root.right);
        console.log(root);    
    }

7. 先中后序遍历（非递归版 栈模拟）

  • 先序遍历（根左右）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    const bt = {...}
    const preorder = (root) => {
        if(!root) return;
        const stack = [root];
        while (stack.length) {
            const node = stack.pop();
            console.log(node.val);
            if (n.right) stack.push(n.right);
            if (n.left) stack.push(n.left);  // 因为stack的特点是后进先出
        }
    }
  • 中序遍历（左根右）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    const bt = {...}
    const inorder = (root) => {
        if(!root) return;
        let p = root;  // 指针
        while (stack.length || p) {
            while(p) {
                stack.push(p);
                p = p.left;
            }
            const node = stack.pop();
            console.log(node.val);
            p = node.right;
        }
    }
  • 后序遍历（左右根）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    const bt = {...}
    const postorder = (root) => {
        if (!root) return;
        const outputStack = [];
        const stack = [root];
        while (stack.length) {
            const node = stack.pop();
            outputStack.push(node);
            if (node.left) stack.push(node.left);
            if (node.right) stack.push(node.right);
        }
        while(outputStack.length) {
            const node = outputStack.pop();
            console.log(node.val);
        }
    }

    使用两个栈，第一个栈类似先序遍历，再将此push到outputStack里，再pop拿到node

8. LeetCode题

104. 二叉树的最大深度

104. 二叉树的最大深度
思路：

求最大深度，考虑使用深度优先遍历

在深度优先遍历过程中，记录每个节点所在的层级，找到最大的层级

步骤：

新建一个变量，记录最大深度

深度优先遍历整棵树，并记录每个节点的层级，同时不断刷新最大深度这个变量

遍历结束后返回最大深度这个变量

1
2
3
4
5
6
7
8
9
10
11
12
const maxDepth = function(root) {
    let res = 0;
    const dfs = (node, len) => {
        if(!node) return;
        res = Math.max(res, len);
        // 可以优化一下，为叶子节点的时候再刷新res值，即if(!node.left && !node.right)
        dfs(node.left, len + 1);
        dfs(node.right, len + 1);
    };
    dfs(root, 1)
    return res
};

111. 二叉树的最小深度

111. 二叉树的最小深度

思路：

求最小深度，考虑使用广度优先遍历

在广度优先遍历过程中，遇到叶子节点，停止遍历，返回节点层级

步骤：

广度优先遍历整棵树，并记录每个节点的层级

遇到叶子节点，返回节点层级，停止遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var minDepth = function(root) {
    if(!root) return 0;
    const queue = [[root, 1]];
    while (queue.length) {
        const [node, len] = queue.shift();
        if (!node.left && !node.right) {
            return len;
        }
        if(node.left) {
            queue.push([node.left, len + 1]);
        }
        if(node.right) {
            queue.push([node.right, len + 1]);
        }
    }
};

102. 二叉树的层序遍历

102. 二叉树的层序遍历

思路：

层序遍历就是广度优先遍历

但在遍历的时候需要记录当前节点所处的层级，方便将其添加到不同的数组里

步骤：

广度优先遍历二叉树

遍历过程中，记录每个节点的层级，并将其添加到不同的数组中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var levelOrder = function(root) {
    if(!root) return [];
    const q = [[root, 0]];
    const res = [];
    while(q.length) {
        const [node, level] = q.shift();
        if(!res[level]) {
            res.push([node.val])
        } else {
            res[level].push(node.val)
        }
        if(node.left) q.push([node.left, level + 1]);
        if(node.right) q.push([node.right,level + 1])
    }
    return res;
};

优化：在每个层级里就将元素push到res里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var levelOrder = function(root) {
    if(!root) return [];
    const q = [root];
    const res = [];
    while(q.length) {
        let len = q.length
        res.push([]);
        while(len--){
            const node = q.shift();
            res[res.length - 1].push(node.val);
            if(node.left) q.push(node.left);
            if(node.right) q.push(node.right);
        }
    }
    return res;
};

94. 二叉树的中序遍历

94. 二叉树的中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
// 递归
var inorderTraversal = function(root) {
    const res = [];
    const rec = (node) => {
        if(!node) return;
        rec(node.left);
        res.push(node.val);
        rec(node.right);
    };
    rec(root);
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 非递归，栈实现
var inorderTraversal = function(root) {
    const res = [];
    const stack = [];
    let p = root;
    while(stack.length || p) {
        while(p) {
            stack.push(p);
            p = p.left;
        }
        const node = stack.pop();
        res.push(node.val);
        p = node.right;
    }
    return res;
};

112. 路径总和

112. 路径总和

思路：

在深度优先遍历的过程中，记录当前路径的节点值的和

在叶子节点处，判断当前路径的节点值的和是否等于目标值

步骤：

深度优先遍历二叉树，在叶子节点处，判断当前路径的节点值的和是否等于目标值，是则返回true

遍历结束，如果没有匹配到，返回false

1
2
3
4
5
6
7
8
9
10
11
12
13
var hasPathSum = function(root, targetSum) {
    if(!root) return false;
    let res = false;
    const dfs = (node, s) => {
        if(!node.left && !node.right && s === targetSum){
            res = true;
        }
        if(node.left) dfs(node.left, s + node.left.val);
        if(node.right) dfs(node.right, s + node.right.val);
    };
    dfs(root,root.val);
    return res;
};