关于javascript:二叉树遍历和JS实现

31次阅读

共计 2348 个字符，预计需要花费 6 分钟才能阅读完成。

二叉树遍历次要为深度优先（DFS）和广度优先（BFS），其中深度优先遍历包含前序、中序、后序，广度优先遍历也叫层序遍历。

深度优先三种办法遍历程序：

其实很好记，就是两头节点在最后面、两头和最初面输入，而左右的绝对程序是固定的。

例如上面这棵树：

前序遍历：1, 2, 4, 5, 3, 6, 7
中序遍历：4, 2, 5, 1, 6, 3, 7
后序遍历：4, 5, 2, 6, 7, 3, 1

深度优先和广度优先都能通过递归实现，因为递归办法过于简略，面试考查的通常是非递归实现。深度优先的非递归办法通过 堆栈实现 ，广度优先的非递归办法通过 队列实现。

前序遍历：

function preOrder(root) {if (root == null)
        return;
    console.log(root.val); // 输入管制
    preOrder(root.left);
    preOrder(root.right);
}

而中序遍历和后序遍历则只需批改 输入管制 的地位。

中序遍历：

function inOrder(root) {if (root == null)
        return;
    inOrder(root.left);
    console.log(root.val); // 输入管制
    inOrder(root.right);
}

后序遍历：

function postOrder(root) {if (root == null)
        return;
    postOrder(root.left);
    postOrder(root.right);
    console.log(root.val); // 输入管制
}

非递归版本应用堆栈实现，三种遍历办法次要是压栈弹栈的程序不同。

前序遍历：

一开始先把根节点压栈，每次弹出栈顶元素的同时输入该元素，而后把栈顶元素的右节点、左节点别离入栈（如果有的话，为空则不必）；直到栈为空则进行。

代码如下：

function preOrderByStack(root) {let res = new Array();
    if (root == null) // 边界判断
        return res;
    let stack = new Array();
    stack.push(root); // 先把根节点压栈
    while (stack.length > 0) {root = stack.pop(); // 弹出以后栈顶元素
        res.push(root.val); // 保留后果
        if (root.right != null) {stack.push(root.right); // 先压入右节点
        }
        if (root.left != null) {stack.push(root.left); // 再压入左节点
        }
    }
    return res;
}

下面的代码复用了 root 变量，益处就是不应用额定的变量，升高空间复杂度。

后序遍历：

后序遍历有一种十分 trick 的做法。咱们晓得先序遍历为 中左右 ，而后序遍历为 左右中 ，咱们把后序遍历反过来，就是 中右左 ，是不是发现和先序遍历有点像了？咱们先序遍历采纳了先压入右节点再压入左节点的形式失去了 中左右 的程序，那么咱们只有先压入左节点，再压入右节点，就能失去 中右左 的程序，这里只有保留后果的时候从前往后插入，就变成了咱们想要的后序遍历了：左右中。

function preOrderByStack(root) {let res = new Array();
    if (root == null)
        return res;
    let stack = new Array();
    stack.push(root);
    while (stack.length > 0) {root = stack.pop();
        res.unshift(root.val); // 从数组头部增加后果
        if (root.left != null) {stack.push(root.left); // 先压入左节点
        }
        if (root.right != null) {stack.push(root.right); // 再压入右节点
        }
    }
    return res;
}

中序遍历：

以后节点只有有左节点，就将其左节点压栈，并且以后节点向其左节点方向挪动，直到以后节点为空，阐明此时位于最左下方的节点的空左节点处，那么接下来咱们就须要弹栈获取栈顶，输入元素，而后挪动到栈顶节点的右节点处。

代码如下：

function inOrderByStack(root) {let res = new Array();
    let stack = new Array();
    while (stack.length > 0 || (root != null)) {if (root != null) { // 以后节点非空，压栈后向左挪动
            stack.push(root);
            root = root.left;
        } else { // 以后节点为空，弹栈输入后向右挪动
            root = stack.pop();
            res.push(root.val);
            root = root.right;
        }
    }
    return res;
}

简略来说就是一行一行地遍历，基于队列来做，先把根节点入队列，只有队列非空，每次把队头结点弹出，而后把堆头的左右节点压入队列中，这样最终遍历进去的就是层序遍历的程序。

function levelOrder(root) {if (root == null)
        return null;
    let res = new Array();
    let queue = new Array();
    queue.unshift(root); // 先把根节点入队列
    while (queue.length > 0) { // 队列非空
        root = queue.pop();
        res.push(root.val); // 弹出队头节点
        if (root.left != null) queue.unshift(root.left);
        if (root.right != null) queue.unshift(root.right);
    }
    return res;
}

参考：
二叉树遍历

正文完