二叉树的遍历问题

先序遍历

根->左子树->右子树

递归实现

void preOrder(BiTNode *root) {
  if (root != NULL) {
    visit(root);
    preOrder(root->lchild);
    preOrder(root->rchild);
  }
}

非递归实现

通过分析先序遍历可以提取出以下特点：

1. 先序遍历先访问根结点，然后循环访问左子树的根结点；
2. 循环访问至最深层时是二叉树最左边的叶子结点；
3. 最后访问结点对应父结点的右子树。

当访问右子树时，可以把右子树第一个结点作为新的根结点，则循环完成闭环。

非递归结构都需要使用栈，且需要使用一个指针控制遍历过程。由于遍历完成后栈和遍历指针都为空，因此可以先做如下定义：

void preOrder(BiTNode *root) {
  stack<BiTNode*> s; // 结点栈 
  BiTNode *p = root; // 遍历指针
  while (p || !s.empty()) {
    /* code */
  }
}

处理根结点后循环处理左子树，循环到最深层的叶子结点后，需要返回访问对应父结点的右子树，因此还需要保存每次循环的父结点。

同时，当循环到最深层的叶子结点后，继续访问左子树为空 NULL，之后才访问对应父结点的右子树，因此可以通过判断 p 是否为空来决定动作：

if (p) {
  // 循环访问左子树
  visit(p);
  s.push(p);
  p = p->lchild;
} else {
  // 返回访问右子树
  p = s.top();
  s.pop();
  p = p->rchild;
}

完整代码如下：

void preOrder(BiTNode *root) {
  stack<BiTNode*> s;
  BiTNode *p = root;
  while (p || !s.empty()) {
    if (p) {
      visit(p);
      s.push(p);
      p = p->lchild;
    } else {
      p = s.top();
      s.pop();
      p = p->rchild;
    }
  }
}

中序遍历

左子树->根->右子树

递归实现

void inOrder(BiTNode *root) {
  if (root != NULL) {
    preOrder(root->lchild);
    visit(root);
    preOrder(root->rchild);
  }
}

非递归实现

分析方法和先序一致，首先确定特点：

1. 中序遍历不断循环进入根结点的左子树，首先访问循环最深层即二叉树最左边的叶子结点；
2. 然后访问该结点对应的父结点；
3. 最后访问该父结点的右子树；

当访问右子树时，可以把右子树第一个结点作为新的根结点，则循环完成闭环。循环过程和先序遍历基本一致，只是访问结点的时机不同。完整代码如下：

void inOrder(BiTNode *root) {
  stack<BiTNode*> s;
  BiTNode *p = root;
  while (p || !s.empty()) {
    if (p) {
      s.push(p);
      p = p->lchild;
    } else {
      p = s.top();
      s.pop();
      visit(p);
      p = p->rchild;
    }
  }
}

后序遍历

左子树->右子树->根

递归实现

void postOrder(BiTNode *root) {
  if (root != NULL) {
    preOrder(root->lchild);
    preOrder(root->rchild);
    visit(root);
  }
}

非递归实现

后序遍历相对比较复杂，不过首先还是确定特点：

1. 后续遍历不断循环进入根结点的左子树，首先访问循环最深层即二叉树最左边的叶子结点；
2. 然后访问该结点对应父结点的右子树；
3. 最后访问该父结点。

不过此时这个循环无法顺利完成闭环，而是会形成局部的死循环，导致死循环发生的问题包括：

问题1：首先为了能在访问最左边叶子结点后直接访问该结点对应父结点的右子树，可以通过判断父结点是否有右子树来控制，关键在于访问完右子树后需要回到父结点。此时如果不控制遍历指针，就会不断访问该右子树最右边的叶子结点形成死循环。

若要正常运行，就需要在访问完右子树最右边的叶子结点后就访问该结点的父结点，即直接访问栈顶元素。此时可令遍历指针 p 为 NULL：

if (p) {
  s.push(p);
  p = p->lchild;
} else {
  p = s.top();
  if (p->rchild) { // 如果父结点有右子树就进入右子树
    p = p->rchild;
  } else { // 否则直接访问该结点
    s.pop();
    visit(p); 
    p = NULL;
  }
}

问题2：解决问题1之后，死循环的问题并未得到解决，因为从上述代码可知，获取栈顶元素后还会判断是否有右子树，如果有就直接进入右子树，这样一来还是会形成死循环。

为了解决这个问题，需要新增一个指针 t，用来保存上一次访问的结点，这样一来在判断结点是否有右子树的同时再判断该右子树是否已经被访问过，从而避免进入死循环。解决这个问题之后，整个循环即可形成完整的闭环。完整的代码如下：

void postOrder(BiTNode *root) {
  stack<BiTNode*> s;
  BiTNode *p = root;
  BiTNode *t = NULL;
  while (p || !s.empty()) {
    if (p) {
      s.push(p);
      p = p->lchild;
    } else {
      p = s.top();
      if (p->rchild && p->rchild != t) {
        p = p->rchild;
      } else {
        s.pop();
        visit(p);
        t = p;
        p = NULL;
      }
    }
  }
}

层序遍历

按层次从左往右访问，借助队列实现

void layerOrder(BiTNode *root) {
  queue<BiTNode*> q;
  BiTNode *p;
  q.push(root);
  while (!q.empty()) {
    p = q.pop();
    visit(p);
    if (p->lchild != NULL) q.push(p->lchild);
    if (p->rchild != NULL) q.push(p->rchild);
  }
}

根据遍历序列重建二叉树

这里以先序遍历序列(pre[n]) + 中序遍历序列(in[n])为例，其他三种原理一致。

BiTNode *createByPreIn(int preL, int preR, int inL, int inR) {
  if (preL > preR) {
    return NULL; // 先序序列长度为0，即树已建成
  }

  BiTNode *root = new BiTNode;
  root->data = pre[preL]; // 先序序列第一个为根结点

  int k, numLeft;
  for (k = inL; k <= inR; k++) {
    if (in[k] == pre[preL]) break;
  }
  numLeft = k - inL; // 左子树结点数

  // 左子树的先序区间为 [preL+1, preL+numLeft]，中序区间为 [inL, k - 1]
  root->lchild = createByPreIn(preL + 1, preL + numLeft, inL, k - 1);
  // 右子树的先序区间为 [preL+numLeft+1, preR]，中序区间为 [k+1, inR]
  root->rchild = createByPreIn(preL + numLeft + 1, preR, k + 1, inR);

  return root; // 返回根结点地址
}