二叉树的先序、中序和后续遍历

二叉树的先序、中序和后续遍历

typedef struct TreeNode * BinTree;
struct TreeNode{
    int val;
    BinTree Left;
    BinTree Right;
};

• 递归写法

  void PreOrderTraversal(BinTree BT){
    if(!BT) return;
    printf("%d  ", BT->val);
    PreOrderTraversal(BT->Left);
    PreOrderTraversal(BT->Right);
  }
  void InOrderTraversal(BinTree BT){
    if(!BT) return;
    InOrderTraversal(BT->Left);
    printf("%d  ", BT->val);
    InOrderTraversal(BT->Right);
  }
  void PostOrderTraversal(BinTree BT){
    if(!BT) return;
    PostOrderTraversal(BT->Left);
    PostOrderTraversal(BT->Right);
    printf("%d  ", BT->val);
  }

• 非递归写法

  void PreOrderTraversal(BinTree BT){
    BinTree T = BT;
    stack<BinTree> s;
    while(T || !s.empty()){
        while(T){
            printf("%d  ", T->val);
            s.push(T);
            T = T->Left;
        }
        if(!s.empty()){
            T = s.top();
            s.pop();
            T = T->Right;
        }
    }
  }
  void InOrderTraversal(BinTree BT){
    BinTree T = BT;
    stack<BinTree> s;
    while(T || !s.empty()){
        while(T){
            s.push(T);
            T = T->Left;
        }
        if(!s.empty()){
            T = s.top();
            s.pop();
            printf("%d  ", T->val);
            T = T->Right;
        }
    }
  }
  void PostOrderTraversal(BinTree BT){
    BinTree T = BT;
    stack<BinTree> s;
    stack<BinTree> s_r;
    while(T || !s.empty()){
        while(T){
            s.push(T);
            T = T->Left;
        }
        if(!s.empty()){
            T = s.top();
            s.pop();
            s_r.push(T);
            T = T->Right;
            BinTree T1 = T;
            if(!T1){
                while(!s_r.empty() && T1 == s_r.top()->Right){
                    T1 = s_r.top();
                    s_r.pop();
                    printf("%d  ", T1->val);
                }
            }
        }
    }
  }

本文的主要重点就是在非递归写法的后续遍历中，使用额外的一个堆栈记录向右侧的遍历，当向右侧遍历到NULL的时候，开始从栈顶输出，同时判断是不是栈顶的右侧结点决定是否继续输出，直到不是右侧结点或者栈为空时停止输出