算法 二叉树

二叉树的前序、中序、后序遍历的非递归实现

Posted by WWJ on May 13, 2018

二叉树的前序、中序、后序的非递归遍历实现

三种遍历的入栈顺序一致，不一样的是根结点的输出时间

前序：当根结点不为空时，根结点入栈，同时输出根结点 中序：当根结点不为空时，暂存根结点，当根结点所有的左子树都遍历完时，输出根节点 后序：当根结点不为空时，暂存根节点，当根结点的左子树和右子树都遍历完时（且左子树要在右子树之前遍历），输出根结点

算法实现

前序：

  1. 实现思路：
    • 访问根结点root，并将其入栈，同时输出根结点
    • 判断根结点root的左孩子是否为空，若不为空，左孩子入栈，并将当前根结点设置为左孩子（即根结点root指向根结点root的左孩子）
    • 循环执行第二条直至根结点的左孩子为空；
    • 若为空，取栈顶元素进行出栈操作，并将当前根结点设置成栈顶元素的右孩子（root指向栈顶元素的右孩子）
    • 直到root为空或者栈为空，则遍历结束
  2. 代码实现 
    const preorderTraversal = function(root) {
 let stack = [], arr = []
 //当根结点不为空或者栈不为空的情况下遍历
 while(root || stack.length) {
     //当根结点不为空的情况下，入栈，并判断左孩子是否为空，是进行出栈操作，不是，将root指向左孩子
     while(root) {
         stack.push(root)
         arr.push(root)
         root = root.left
     }
     let lastVal = stack[stack.length - 1]
     stack.pop()
     //进行出栈操作后，将root指向右孩子(遍历右子树)
     root = lastVal.right
 }
 return arr
}

中序：

  1. 实现思路
    • 访问根结点root，并将其入栈，暂存
    • 判断根结点root的左孩子是否为空，若不为空，左孩子入栈，并将当前根结点设置为根结点的左孩子（结点root指向左孩子），循环这一操作，直到左孩子为空；
    • 若为空，输出栈顶元素并进行出栈操作，然后将当前根结点设置成栈顶元素的右孩子
    • 直到root为空或者栈为空，遍历结束
  2. 代码实现 
    const middleorderTraversal = function(root) {
 let stack = [], arr = []
 //当根结点不为空或者栈不为空的情况下遍历
 while(root || stack.length) {
     //当根结点不为空的情况下，入栈，并判断左孩子是否为空，是进行出栈操作，不是，将root指向左孩子
     while(root) {
         stack.push(root)
         root = root.left
     }
     //将栈顶元素输出并出栈
     let lastVal = stack[stack.length - 1]
     arr.push(lastVal)
     stack.pop()
     //进行出栈操作后，将root指向右孩子(遍历右子树)
     root = lastVal.right
 }
 return arr
}

后序遍历：

  1. 实现思路 后序遍历是这三种遍历方式里面最复杂的一种，因为后序在输出根结点的时候需要考虑根结点的左右子树是否都已遍遍历 所以我们可以设置一个变量lastVisit，来标记当前遍历的根结点的右孩子是否等于lastVisit，如果相等，那么表示当前根结点的左右孩子都已经遍历，那么就可以输出当前根结点，如果不相等，那么就把当前根结点设置为当前根结点的右孩子，所有整体思路就是：
    • 访问根结点root，入栈
    • 判断根结点的左孩子是否为空，若不为空，那么左孩子入栈，并将当前根结点设置为当前根结点的左孩子，循环执行这一操作，直至根结点的左孩子为空；
    • 若为空，执行出栈操作，执行出栈操作时需要判断当前栈顶元素的左右孩子都已经被遍历了，即root.right === null || root.right === lastVisit，若该条件成立，那么输出栈顶元素，lastVisit设置为空栈顶元素，出栈，当前根结点设置为null，以便于下次继续进行出栈操作；若该条件不成立，那么就将当前根结点设置为栈元素的有孩子
    • 重复上面的操作，直至root为空或者栈为空
  2. 代码实现 
    const postorderTraversal = function(root) {
 let stack = [], arr = [], lastVisit = null
 //当根结点不为空或者栈不为空的情况下遍历
 while(root || stack.length) {
     //当根结点不为空的情况下，入栈，并判断左孩子是否为空，是进行出栈操作，不是，将root指向左孩子
     while(root) {
         stack.push(root)
         root = root.left
     }
     //判断当前根结点的右孩子是否为空或者等于lastVisit，若该条件成立，执行if代码块，否则执行else代码块
     if(root.right === null || root.roght === lastVisit) {
         arr.push(root)
         lastVisit = root
         stack.pop()
         root = null
     } else {
         root = root.right
     }
 }
 return arr
}
CATALOG