乐趣区

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

基本概念

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

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

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

例如上面这棵树:

    1
   / \
  2   3
 / \ / \
4  5 6  7

前序遍历: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;
}

参考:
二叉树遍历

退出移动版