二叉树遍历算法总结

三类：

• 栈
  • 系统栈
  • 自己实现的栈
• 线索：Morris preorder/inorder/postorder traversal
• 其他edge-crawling方式：Schorr-Waite graph marking algorithm、Lindstrom-Dwyer algorithm

#include <algorithm>
#include <cstdio>
#include <queue>
#include <stack>
using namespace std;

struct Node {
  int key;
  int s; // only used by Schorr-Waite
  Node *l, *r;
  Node(int key, Node *l, Node *r) : key(key), l(l), r(r), s(0) {}
  void visit() const {
    printf("%d\n", key);
  }
};

enum Type { PREORDER, INORDER, POSTORDER };

/*
preorder模拟栈版：栈中存放的节点`x`表示之后待遍历`x`的子树。
*/
void preorder(Node *p)
{
  if (p) {
    p->visit();
    preorder(p->l);
    preorder(p->r);
  }
}

/*
inorder模拟栈版：栈中存放的节点`x`表示`x`待访问，且之后遍历`x`的右子树。
*/
void inorder(Node *p)
{
  if (p) {
    inorder(p->l);
    p->visit();
    inorder(p->r);
  }
}

void postorder(Node *p)
{
  if (p) {
    postorder(p->l);
    postorder(p->r);
    p->visit();
  }
}

void preorder_stack(Node *p)
{
  stack<Node *> s;
  for(;;) {
    while (p) {
      p->visit();
      if (p->r)
        s.push(p->r);
      p = p->l;
    }
    if (s.empty()) break;
    p = s.top();
    s.pop();
  }
}

void inorder_stack(Node *p)
{
  stack<Node *> s;
  for(;;) {
    while (p) {
      s.push(p);
      p = p->l;
    }
    if (s.empty()) break;
    p = s.top();
    s.pop();
    p->visit();
    p = p->r;
  }
}

/*
栈中存放的节点`x`表示两种阶段之一：
1. 当前在访问`x`左子树，之后待遍历`x`的右子树，然后访问`x`。
2. 当前在访问`x`的右子树，之后待访问`x`。

祖先节点进入阶段2的时刻晚于后裔节点。
外层循环开始处即`while (p) {`行，以下两个条件之一满足：
1. `p`非NULL，需要遍历`p`子树，栈上存放`p`的所有祖先。
2. `p`为NULL，栈上是栈顶及栈顶的所有祖先，下一个访问的是栈顶。

遍历一棵子树的方式是沿着左孩子链接下溯并把沿途节点都压栈，直到遇到NULL。
若遇到的最后一个节点`x`有右孩子`y`，则当前指针置为`y`，`x`及`x`的一些连续的祖先进入阶段2；
否则(第二个while循环实现这一复杂逻辑)说明`x`已在阶段2，访问`x`，
同时`x`一些连续的祖先也进入阶段2了，也需要访问并从栈中弹出。
*/
void postorder_stack(Node *p)
{
  stack<Node *> s;
  for(;;) {
    while (p) {
      s.push(p);
      p = p->l;
    }
    while (! s.empty() && s.top()->r == p) {
      p = s.top();
      s.pop();
      p->visit();
    }
    if (s.empty()) break;
    p = s.top()->r;
  }
}

void postorder2_stack(Node *p)
{
  stack<Node *> s;
  for(;;) {
    while (p) {
      if (p->r)
        s.push(p->r);
      s.push(p);
      p = p->l;
    }
    if (s.empty()) break;
    p = s.top();
    s.pop();
    if (! s.empty() && p->r == s.top()) {
      s.pop();
      s.push(p);
      p = p->r;
    } else {
      p->visit();
      p = NULL;
    }
  }
}

/*
按层级顺序访问，使用队列进行BFS
*/
void level_order(Node *p)
{
  queue<Node *> q;
  if (p) {
    q.push(p);
    while (! q.empty()) {
      p = q.front();
      q.pop();
      p->visit();
      if (p->l)
        q.push(p->l);
      if (p->r)
        q.push(p->r);
    }
  }
}

/*
preorder或inorder可以实现O(1)额外空间的遍历，
方法是把右孩子为空的节点的右孩子改造成中序后继的线索指针。
*/
void morris_traversal(Node *p, Type t)
{
  while (p) {
    Node *q = p->l;
    if (q) {
      while (q->r && q->r != p) q = q->r;
      if (q->r == p)
        q->r = NULL;
      else {
        if (t == PREORDER)
          p->visit();
        q->r = p;
        p = p->l;
        continue;
      }
    } else if (t == PREORDER)
      p->visit();
    if (t == INORDER)
      p->visit();
    p = p->r;
  }
}

// morris_postorder_traversal的辅助函数
void reverse_right_chain(Node *x, Node *y)
{
  Node *p = x, *q = x->r, *r;
  while (p != y) {
    r = q->r;
    q->r = p;
    p = q;
    q = r;
  }
}

/*
增量构造线索进行post-order遍历比较复杂
*/
void morris_postorder_traversal(Node *p)
{
  Node aux;
  aux.l = p;
  aux.r = NULL;
  p = &aux;
  while (p) {
    Node *q = p->l;
    if (q) {
      while (q->r && q->r != p) q = q->r;
      if (q->r == p) {
        reverse_right_chain(p->l, q);
        for (Node *r = q; ; r = r->r) {
          r->visit();
          if (r == p->l) break;
        }
        reverse_right_chain(q, p->l);
        q->r = NULL;
      } else {
        q->r = p;
        p = p->l;
        continue;
      }
    }
    p = p->r;
  }
}

/* Schorr-Waite graph marking algorithm
 *
 * 该算法需要在节点信息里额外维护一个域 s，表示遍历过程中的访问次数，有如下几种取值：
 * 0: 尚未访问
 * 1: 访问过1次(preorder)，尚未遍历其左右子树
 * 2: 访问过2次(inorder)，已遍历其左子树，尚未遍历其右子树
 * 3: 访问过3次(postorder)，已遍历其左右子树
 *
 * 访问到 x 时，其祖先节点及它们的子树遍历进度(在遍历左子树还是右子树)是通过栈维护的。
 * 该算法把祖先节点下溯的指针翻转，再通过设置一个父节点指针 p 以把祖先节点组织为一个链。
 * 通过 s 可以知道各祖先节点当前在遍历左子树还是右子树。
 *
 * 若注释掉代码中的 x->s = 0; 则在算法执行完后遍历到的节点的 s 值为3，可以判断节点是否被访问过。
 *
 * 该算法可用于遍历一般的有向图，也需要注释掉 x->s = 0。带有 q 个指针域的节点将被访问 q+1 次。
 */

void schorr_waite(Node *x, Type t)
{
  if (! x) return;
  Node *y, *p = NULL;
  for(;;) {
    if ((int)t == (int)x->s)
      x->visit();
    if (x->s < 2) {
      x->s++;
      y = x->s == 1 ? x->l : x->r;
      if (y && y->s == 0) {
        (x->s == 1 ? x->l : x->r) = p;
        p = x;
        x = y;
      }
    } else {
      x->s = 0;               // reset to 0
      if (! p) return;
      y = x;
      x = p;
      if (x->s == 1)
        p = x->l, x->l = y;
      else
        p = x->r, x->r = y;
    }
  }
}

// http://www.cs.cornell.edu/courses/cs312/2007fa/lectures/lec21-schorr-waite.pdf
// 下面是一种变体，也可用于一般有向图，每个节点都有两个指针域
// 原始的Schorr-Waite在下溯时把指针和 p 交换，上溯时再交换回来
// 该方法使用四指针置换和三指针置换来统一几种逻辑判断

void schorr_waite_alternative(Node *p, Type t)
{
  Node *q = (Node *)-1;
  while (p != (Node *)-1) {
    if ((int)t == (int)p->s)
      p->visit();
    p->s++;
    if (p->s == 3 || p->l && p->l->s == 0) {
      Node *r = p->l;
      p->l = p->r;
      p->r = q;
      q = p;
      p = r;
    } else {
      Node *r = p->l;
      p->l = p->r;
      p->r = q;
      q = r;
    }
  }
}

// Lindstrom-Dwyer algorithm
// Schorr-Waite的变体，对于二叉树，上面 schorr_waite_alternative 的代码可以进一步简化
// 考察条件 p->s == 3 || p->l && p->l->s == 0
// 若 p->s != 3 则有 1 <= p->s && p->s <= 2
// 此时 p->l 为原节点的左子树或右子树，因为是树，不存在其他节点的指向它们
// 因此 p->l 若非 NULL 则必有 p->l->s != 0
// 该条件只有在 p->l == NULL 时不成立。即使不成立，我们依然可以套用四指针置换
// 但需要把 p(此时为NULL) 设为 q，把 q 设为 NULL
// 之后 s 仅用于判断节点访问次数，不再参与逻辑控制
// 如果不在乎一个节点调用 visit 三次的话，可以省去 s

void lindstrom_dwyer(Node *p)
{
  Node *q = (Node *)-1;
  while (p != (Node *)-1) {
    p->visit();
    Node *r = p->l;
    p->l = p->r;
    p->r = q;
    q = p;
    p = r;
    if (! p) p = q, q = NULL;
  }
}

int main()
{
  Node *a[7];
  for (int i = 7; i--; )
    a[i] = new Node(i, i*2+1 < 7 ? a[i*2+1] : NULL, i*2+2 < 7 ? a[i*2+2] : NULL);
  preorder(a[0]);
  inorder(a[0]);
  postorder(a[0]);
  level_order(a[0]);
  morris_traversal(a[0], PREORDER);
  morris_traversal(a[0], INORDER);
  preorder_stack(a[0]);
  inorder_stack(a[0]);
  postorder_stack(a[0]);
  postorder2_stack(a[0]);
  schorr_waite(a[0], PREORDER);
  schorr_waite(a[0], INORDER);
  schorr_waite(a[0], POSTORDER);
  schorr_waite_alternative(a[0], PREORDER);
  schorr_waite_alternative(a[0], INORDER);
  schorr_waite_alternative(a[0], POSTORDER);
  lindstrom_dwyer(a[0]);
}