2022-09-17数据结构00
请注意,本文编写于 637 天前,最后修改于 637 天前,其中某些信息可能已经过时。

二叉树的先序,中序,后序遍历

先序遍历表示先访问根节点,然后访问左节点,最后访问右节点。

中序遍历表示先访问左节点,然后访问根节点,最后访问右节点。

后序遍历表示先访问左节点,然后访问右节点,最后访问根节点。

递归实现

递归实现相当简单,代码如下

function TreeNode(val) {
  this.val = val
  this.left = this.right = null
}
var traversal = function(root) {
  if (root) {
    // 先序
    console.log(root)
    traversal(root.left)
    // 中序
    // console.log(root);
    traversal(root.right)
    // 后序
    // console.log(root);
  }
}

对于递归的实现来说,只需要理解每个节点都会被访问三次就明白为什么这样实现了。

非递归实现

非递归实现使用了栈的结构,通过栈的先进后出模拟递归实现。

以下是先序遍历代码实现

function pre(root) {
  if (root) {
    let stack = []
    // 先将根节点 push
    stack.push(root)
    // 判断栈中是否为空
    while (stack.length > 0) {
      // 弹出栈顶元素
      root = stack.pop()
      console.log(root)
      // 因为先序遍历是先左后右,栈是先进后出结构
      // 所以先 push 右边再 push 左边
      if (root.right) {
        stack.push(root.right)
      }
      if (root.left) {
        stack.push(root.left)
      }
    }
  }
}

以下是中序遍历代码实现

function mid(root) {
  if (root) {
    let stack = []
    // 中序遍历是先左再根最后右
    // 所以首先应该先把最左边节点遍历到底依次 push 进栈
    // 当左边没有节点时,就打印栈顶元素,然后寻找右节点
    // 对于最左边的叶节点来说,可以把它看成是两个 null 节点的父节点
    // 左边打印不出东西就把父节点拿出来打印,然后再看右节点
    while (stack.length > 0 || root) {
      if (root) {
        stack.push(root)
        root = root.left
      } else {
        root = stack.pop()
        console.log(root)
        root = root.right
      }
    }
  }
}

以下是后序遍历代码实现,该代码使用了两个栈来实现遍历,相比一个栈的遍历来说要容易理解很多

function pos(root) {
  if (root) {
    let stack1 = []
    let stack2 = []
    // 后序遍历是先左再右最后根
    // 所以对于一个栈来说,应该先 push 根节点
    // 然后 push 右节点,最后 push 左节点
    stack1.push(root)
    while (stack1.length > 0) {
      root = stack1.pop()
      stack2.push(root)
      if (root.left) {
        stack1.push(root.left)
      }
      if (root.right) {
        stack1.push(root.right)
      }
    }
    while (stack2.length > 0) {
      console.log(s2.pop())
    }
  }
}

本文作者:毛超颖

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!