二叉树的遍历

• 前序遍历
• 中序遍历
• 后序遍历

前序遍历

DLR，访问顺序：根节点、左子树、右子树

递归：

void PreOrder(BTree T){
  if(T != NULL) {
    visit(T);
    PreOrder(T->left);
    PreOrder(T->right);
  }
}

中序遍历

LDR，访问顺序：左子树、根节点、右子树

递归：

void InOrder(BTree T){
  if(T != NULL) {
    InOrder(T->left);
    visit(T);
    InOrder(T->right);
  }
}

非递归（栈）：

void InOrder(BTree T) {
  stack<BTree> st;
  auto p = T;
  if (T != NULL) {
    do{
      while(p != NULL){
				// visit(p);   // pre-order
        st.push(p);
        p = p->left;
      }
      p = st.top();
      st.pop();
      visit(p);
      p = p->right;
    } while (!(p == NULL && st.empty()));
  }
}

感觉do-while有点奇怪，记得试着改下。

后序遍历

LRD，访问顺序：左子树、右子树、根节点

递归：

void PostOrder(BTree T){
  if(T != NULL) {
    PostOrder(T->left);
    PostOrder(T->right);
    visit(T);
  }
}

非递归方法需要注意的问题是，当指针p指向某一个节点时，不能马上对它进行访问，要先遍历左子树，因此p先进栈；左子树遍历完后，再遍历该节点（退栈）时，还不能访问，要先遍历右子树，p再次进栈。所以需要引入一个标识变量flag，为0表示节点暂不访问，为1表示可以访问，需要两个栈，一个栈存节点，一个栈存对应的flag

void PostOrder(BTree T){
  stack<BTree> nodes;
  stack<int> flags;
  auto p = T;
  assert(T != NULL);
  do {
    while(p != NULL){
      nodes.push(p);
      flags.push(0);
      p = p->left;
    }
    p = nodes.top();
    flag = flags.top();
    nodes.pop();
    flags.pop();
    if(flag == 0){
      nodes.push(p);
      flags.push(1);
      p = p->right;
    } else {
      visit(p);
      p = NULL;
    }
  }while(!(p == NULL && nodes.empty()));
}

赏

谢谢你请我吃糖果