二叉树遍历非递归写法之大统一

69 阅读 0 评论 46 点赞

我是靠谱客的博主爱笑百褶裙，最近开发中收集的这篇文章主要介绍二叉树遍历非递归写法之大统一，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在学习二叉树遍历时，大家都很容易接受递归写法，好理解。对于非递归写法，基本思想是用栈消除递归，但是教材上的前序、中序和后序基本上三个写法，还很难理解。博主亲身经历，找工作中，考查二叉树遍历的非递归写法还是常见的。所以决心整理出此文，方便理解和记忆二叉树遍历。

来复习一下二叉树的递归遍历。

[cpp]  
   view plain 
   copy 
    
   
 struct TreeNode {  
     int data;  
     TreeNode * left, * right;  
 };  
   
 void preOrderTraverse(TreeNode * root, void (*visit)(TreeNode *)) {  
     if (root) {  
         visit(root);  
         preOrderTraverse(root->left, visit);  
         preOrderTraverse(root->right, visit);  
     }  
 }  
   
 void inOrderTraverse(TreeNode * root, void (*visit)(TreeNode *)) {  
     if (root) {          
         inOrderTraverse(root->left, visit);  
         visit(root);  
         inOrderTraverse(root->right, visit);  
     }  
 }  
   
 void postOrderTraverse(TreeNode * root, void (*visit)(TreeNode *)) {  
     if (root) {  
         postOrderTraverse(root->left, visit);  
         postOrderTraverse(root->right, visit);  
         visit(root);          
     }  
 }  

首先，博主找到了一篇类似论文，《更简单的非递归遍历二叉树的方法》，该文非常漂亮的将三种遍历方法统一起来，除了有三行代码的顺序不一样外。该实现中，对每个节点定义了一个pair对，通过改变局部入栈顺序实现整体遍历的不同。

本文意图使用常见的二叉树遍历的形式，简洁的实现这三种遍历。

void preOrderTraverseNonrecursive(TreeNode * root, void (*visit)(TreeNode *)) {
stack<TreeNode *> s;
TreeNode * p = root;
while(p != NULL || !s.empty()) {
while(p != NULL) {
visit(p);
  s.push(p);
p = p->left;
}
  if (!s.empty()) {
  p = s.top();
  p = p->right;
  s.pop();
}
}
}

void inOrderTraverseNonrecursive(TreeNode * root, void (*visit)(TreeNode *)) {
stack<TreeNode *> s;
TreeNode * p = root;
while(p != NULL || !s.empty()) {
while(p != NULL) {
  s.push(p);
p = p->left;
}
  if (!s.empty()) {
  p = s.top();
  visit(p);
  p = p->right;
  s.pop();
}
}
}

void postOrderTraverseNonrecursive(TreeNode * root, void (*visit)(TreeNode *)) {
stack<TreeNode *> s;
TreeNode * p = root, *pre = NULL;
while(p != NULL || !s.empty()) {
while(p != NULL) {
  s.push(p);
p = p->left;
}
  if (!s.empty()) {
  p = s.top();
  if( p->right == NULL || p->right == pre) {
  visit(p);

pre = p;

p = NULL;

  s.pop();
  }
  else {
  p = p->right;
  }
}
}
}

在前序遍历的代码中，最外层是while循环直到栈空且p为空，里面的while循环，不停访问根节点p，且迭代p=p->right，直到p为空。此时，从root开始的所有左分支的根节点均已被访问。到if分支时，取栈顶节点，切换到其右子树开始迭代。

前序遍历和中序遍历区别仅在于visit函数的调用位置不同。中序和后序的区别在于调用visit的时机不一致。教材上的实现中，后序遍历需要一个标志来记录当前节点是否被访问过。在本文的实现中，通过一个pre指针记录被访问的最后一个元素，通过p->right==pre的比较来确认p是否被访问过。当然，直接访问p的另一情形是p没有右孩子。在这样的实现下，中序和后序的区别尽可能小。三种实现中，代码结构较一致，只有较少的变动。

希望本文可以方便那些学习非递归遍历二叉树的同学。

欢迎大家留言讨论！