数据结构与算法——二叉树遍历

template<typename T>
void PreOrder(BinaryTreeNode<T>* root){
    stack<BinaryTreeNode<T>*> aStack;
    BinaryTreeNode<T>* pointer = root;
    aStack.push(nullptr);                       // 栈底监视哨
    while(pointer){                             // 或者 !aStack.empty()
        Visit(pointer);                         // 访问当前结点
        if(pointer->rightchild() != nullptr){   // 右孩子入栈
            aStack.push(pointer->rightchild());
        }
        if(pointer->leftchild() != nullptr){    // 左路下降
            pointer = pointer->leftchild();
        }else{                                  // 左子树访问完毕，转向访问右子树
            pointer = aStack.top();
            aStack.pop();
        }
    }
}

template<typename T>
void InOrder(BinaryTreeNode<T>* root){
    stack<BinaryTreeNode<T>*> aStack;
    BinaryTreeNode<T>* pointer = root;
    while(!aStack.empty() || pointer){
        if(pointer){
            // Visit(pointer);                         // 前序访问点
            aStack.push(pointer);                   // 当前结点入栈
            pointer = pointer->leftchild();         // 指向左子树
        } // endif
        else{                                       // 左子树访问完毕，转向右子树
            pointer = aStack.top();
            aStack.pop();                           // 栈顶元素退栈
            Visit(pointer);                         // 访问当前结点
            pointer = pointer->rightchild();        // 转向右孩子
        } // endelse
    } // endwhile
}

enum class Tags{Left,Right};            // 枚举类型标志位
template<typename T>
class StackElement{
    BinaryTreeNode<T>* pointer;         // 二叉树结点指针
    Tags tag;                           // 标志位
};

template<typename T>
void PostOrder(BinaryTreeNode<T>* root){
    StackElement<T> element;
    stack<StackElement<T>> aStack;
    BinaryTreeNode<T>* pointer = root;
    while(!aStack.empty() || pointer){
        while(pointer){                         // 非空指针入栈，并沿左路下降
            element.pointer = pointer;
            element.tag = Left;
            aStack.push(element);                   
            pointer = pointer->leftchild(); 
        } 
        element = aStack.top();
        aStack.pop();
        pointer = element.pointer;
        if(element.tag == Left){                // 如果是从左子树返回
            element.tag = Right;
            aStack.push(element);               // 置标志位为 Right 
            pointer = pointer->rightchild();
        } // endif
        else{                                   // 从右子树返回
            Visit(pointer);                     // 访问当前结点
            pointer = nullptr;                  // 将 pointer 置空，以继续弹栈
        } // endelse
    } // endwhile
}