Day12:[资料结构]Binary Tree -  Traversal

Traversal翻译成中文就是遍历的意思，如果要遍历tree的每个节点的话，会有两种方式，Breadth-First Tree Traversal和Depth-First Tree Traversal。

Breadth-First Tree Traversal

Breadth-First Tree Traversal 也被称作Level Order Tree Traversal，利用广度优先搜寻(Breadth-First Search, BFS)的方式来遍历每个节点，概念非常容易理解 ，就是将每一层的节点由左至右依序取出。

甚麽是广度优先搜寻?

从某个节点出发，接下来走访相邻节点，同一层的都走访完了就往下一层

图片来源:BreadthFirstSearch

假设我们现在有颗Binary Tree如下图

用广度优先搜寻的方式走访的步骤为:
1.第1层 取出10
2.第2层 取出8, 11
3.第3层 取出5, 9 ,15
4.第4层 取出2, 13, 19

最後取得阵列[10, 8, 11, 5, 9, 15, 2, 13, 19]

用js实作Breadth-First Tree Traversal:

    bftt(node) {
        if (node === null) return;
        this.queue.push(node);
        for (let i = 0; i < this.queue.length; i++) {
            let currentNode = this.queue[i];
            if (currentNode === null) continue;
            if (currentNode.left !== null) {
                this.queue.push(currentNode.left);
            }
            if (currentNode.right !== null) {
                this.queue.push(currentNode.right);
            }
        }
    }
    tree.bftt(tree.root)

Depth-First Tree Traversal

采用的是深度优先搜寻(Depth-First-Search，DFS)的方式来遍历节点，Depth-First Tree Traversal又分为三种，这三种非常类似，但遍历的顺序不同。

• preorder - 前序
• inorder - 中序
• postorder - 後序

深度优先搜寻

深度优先搜寻演算法（英语：Depth-First-Search，DFS）是一种用於遍历或搜寻树或图的演算法。这个演算法会尽可能深的搜寻树的分支。当节点v的所在边都己被探寻过，搜寻将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个行程反覆进行直到所有节点都被存取为止。这种演算法不会根据图的结构等资讯调整执行策略(引用自wikipedia)

看完维基百科的解释真的是似懂非懂，这边我会想像是摸着墙在走迷宫，发现走到底了，就回头找另一道墙继续探索，只是靠墙的顺序有所差异(先靠左或是先靠右)。

PreOrder(root, left, right)

顺序: 根节点 → 左节点 →右节点

实际用PreOrder走访一次Binary Tree的话，顺序如下图

绿色的数字为遍历的顺序用

js实作PreOrder

    preOrder(node) {
        if (node === null) return;
        this.queue.push(node.value);
        //用递回来遍历节点
        this.preOrder(node.left);
        this.preOrder(node.right);
    }
    tree.preOrder(tree.root);

InOrder(left, root, right)

顺序: 左节点 → 根节点 →右节点

实际用InOrder的方式走访一次二元树的话顺序如下图

绿色的数字为遍历的顺序

用js实作InOrder

    inOrder(node) {
        if (node === null) return;
        //用递回来遍历节点
        this.inOrder(node.left);
        this.queue.push(node.value);
        this.inOrder(node.right);
    }
    tree.inOrder(tree.root);

PostOrder(left, right, root)

顺序: 左节点 → 右节点 → 根节点

实际用PostOrder走访一次Binary Tree的话顺序如下图

用js实作PostOrder

    postOrder(node) {
        if (node === null) return;
        //用递回来遍历节点
        this.postOrder(node.left);
        this.postOrder(node.right);
        this.queue.push(node.value);
    }
    tree.postOrder(tree.root);

下面这张图简易的说明了BFS和DFS两者的差异

图片来源:https://medium.com/basecs/breaking-down-breadth-first-search-cebe696709d9

如何在Binary tree中找到指定的值?

第一种方式使用递回，利用Binary tree的特性(当前节点的右子节点会比自己大 ，左子节点会比自己小)，如果目标值比当前节点还大的话就把当前节点的右节点作为参数传入函式，反之就把左节点传入，不断呼叫自己，直到找到节点或是找不到就中止递回。

const searchRecursively = (node, target) => {
    if (node === null || target === node.value) return node;
    if (target < node.value) {
        return searchRecursively(node.left, target);
    }
    if (target > node.value) {
        return searchRecursively(node.right, target);
    }
};
searchRecursively(tree.root, 13);

执行结果如下，找得到就回传该节点，若找不到就回传null

第二种方式用回圈，假如目标值比当前节点还大的话，就把当前节点移动到右边的子节点，反之则移动到左边的节点，直到找到值或是找不到就跳出回圈。

const searchIteratively = (node, target) => {
    while (node !== null && target !== node.value) {
        if (target < node.value) {
            node = node.left;
        } else {
            node = node.right;
        }
    }
    return node;
};
searchIteratively(tree.root, 8);

执行结果如下，找得到就回传该节点，若找不到就回传null

Binary Tree - Traversal完整的程序码如下(包含tree的建立)

class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor() {
        this.root = null;
        this.queue = [];
    }
    insertNode(value) {
        let current = new TreeNode(value);
        let target = null;
        let nowPos = this.root;
        while (nowPos !== null) {
            target = nowPos;
            if (current.value < nowPos.value) {
                nowPos = nowPos.left;
            } else {
                nowPos = nowPos.right;
            }
        }
        if (target === null) {
            this.root = current;
        } else if (current.value < target.value) {
            target.left = current;
        } else {
            target.right = current;
        }
    }
    bftt(node) {
        if (node === null) return;
        this.queue.push(node);
        for (let i = 0; i < this.queue.length; i++) {
            let currentNode = this.queue[i];
            if (currentNode === null) continue;
            if (currentNode.left !== null) {
                this.queue.push(currentNode.left);
            }
            if (currentNode.right !== null) {
                this.queue.push(currentNode.right);
            }
        }
    }
    preOrder(node) {
        if (node === null) return;
        this.queue.push(node.value);
        //用递回来遍历节点
        this.preOrder(node.left);
        this.preOrder(node.right);
    }

    inOrder(node) {
        if (node === null) return;
        //用递回来遍历节点
        this.inOrder(node.left);
        this.queue.push(node.value);
        this.inOrder(node.right);
    }

    postOrder(node) {
        if (node === null) return;
        //用递回来遍历节点
        this.postOrder(node.left);
        this.postOrder(node.right);
        this.queue.push(node.value);
    }
}

let tree = new BinarySearchTree();
tree.insertNode(10);
tree.insertNode(8);
tree.insertNode(11);
tree.insertNode(5);
tree.insertNode(9);
tree.insertNode(15);
tree.insertNode(2);
tree.insertNode(19);
tree.insertNode(13);

console.log("BST", tree);

tree.bftt(tree.root);
tree.preOrder(tree.root);
tree.inOrder(tree.root);
tree.postOrder(tree.root);
console.log(tree.queue);

const searchRecursively = (node, target) => {
    if (node === null || target === node.value) return node;
    if (target < node.value) {
        return searchRecursively(node.left, target);
    }
    if (target > node.value) {
        return searchRecursively(node.right, target);
    }
};

const searchIteratively = (node, target) => {
    while (node !== null && target !== node.value) {
        if (target < node.value) {
            node = node.left;
        } else {
            node = node.right;
        }
    }
    return node;
};

searchRecursively(tree.root, 13);
searchIteratively(tree.root, 8);

时间复杂度

?在最差的情况下， 时间复杂度是O(n)
?在最佳的情况下 ， 时间复杂度是O(1)
?在平均情况下，时间复杂度为 O(log n)

不管是Tree Traversal或是在tree中寻找特定的值都是leetcode蛮常见的考题，只要可以掌握这些核心观念，在解题的时候就会比较得心应手。

参考资料:Tree Traversals