二叉树

递归方法太简单了，这里就贴上几种不同的非递归实现，前中后

//iteration traverse
//travePreIterTail
template<typename T> template <typename VST>
void BinTree<T>::travePreIterTail(BinNodePosi(T) x, VST &visit){
    std::stack<BinNodePosi(T)> preStack;
    preStack.push(x);
    while(!preStack.empty()){
        BinNodePosi(T) ret=preStack.top();
        preStack.pop();
        visit(ret->data);
        if(ret->rchild){
            preStack.push(ret->rchild);
        }
        if(ret->lchild){
            preStack.push(ret->lchild);
        }
    }
}



//traverseIter
template <typename T> template<typename VST>
void BinTree<T>::travePreIterLeft(BinNodePosi(T) x, std::stack<BinNodePosi(T)> &S, VST& visit){
    while(x){
        visit(x->data);
        if(x->rchild){
            S.push(x->rchild);
        }
            x=x->lchild;
    }

}

template <typename T> template <typename VST>
void BinTree<T>::traverPreIter(BinNodePosi(T) x,VST& visit){
    std::stack<BinNodePosi(T)> S;
    while(true){
        travePreIterLeft(x,S,visit);
        if(S.empty()){break;}
        else{
        x=S.top();
        S.pop();
        }
    }

}

template <class T> 
void BinTree<T>::traverInIterLeft(BinNodePosi(T) x,std::stack<BinNodePosi(T)> &S){
    while(x){
        S.push(x);
        x=x->lchild;
    }
}

template <class T> template <class VST>
void BinTree<T>::traverInIterV1(BinNodePosi(T) x,VST& visit){
    std::stack<BinNodePosi(T)> S;
    while(true){
        traverInIterLeft(x,S);
        if(S.empty()) break;
        x=S.top();
        visit(x->data);
        S.pop();
        x=x->rchild;
    }
}

template <typename T> template <typename VST>
void BinTree<T>::traverInIterV2(BinNodePosi(T) x,VST& visit){
    std::stack<BinNodePosi(T)> S;
    while(true){
    if(x){
        S.push(x);
        x=x->lchild;
    }
    else if(!S.empty()){
        x=S.top();
        S.pop();
        visit(x->data);
            x=x->rchild;
    }
    else {
        break;
    }
    }
}

template <typename T> template<typename VST>
void BinTree<T>::traverInIterV3(BinNodePosi(T) x, VST& visit){
    while(HasLChild((*x))){
        x=x->lchild;
    }
    while(true){
            visit(x->data);
            x=x->succ();
            if(!x){
                break;
            }
    }
}


//direct succ of InTraverse
template<class T>
BinNodePosi(T) BinNode<T>::succ(){
    BinNodePosi(T) directSuccPoint=this;
    if(rchild){
        directSuccPoint=rchild;
        while(HasLChild((*directSuccPoint))){
            directSuccPoint=directSuccPoint->lchild;
        }
    }
    else{
        while((directSuccPoint!=nullptr)&&(IsRChild((*directSuccPoint)))){
            directSuccPoint= directSuccPoint->parent;
        }
        if(directSuccPoint!=nullptr){
        directSuccPoint=directSuccPoint->parent;
        }
    }
    return directSuccPoint;
}

//
template <class T>
void BinTree<T>::traversePostLeft(std::stack<BinNodePosi(T)> &S){
    while(BinNodePosi(T) temp=S.top()){
        if(HasLChild((*temp))){
            if(HasRChild((*temp))){
                S.push(temp->rchild);
            }
            S.push(temp->lchild);
        }
        else{
            //if(temp->rchild) can't  because the last top elem must be nullptr
            S.push(temp->rchild);
        }
    }
    S.pop();//pop the nullptr
} 
template <typename T> template <typename VST>
void BinTree<T>::traverPostIter(BinNodePosi(T) x, VST& visit){
    std::stack<BinNodePosi(T)> S;
    if(x)
    S.push(x);
    while(!S.empty()){
        if(S.top()!=x->parent){
            traversePostLeft(S);
        }
        x=S.top();
        S.pop();
        visit(x->data);
    }
}

template <typename T>
void static preShow(BinTree<T> &tree){
    show<T> preTemp;
    tree.traverPreIter(tree.root(),preTemp);
    //tree.travePre_R(tree.root(),preTemp);
}


template<typename T>
void static inShow(BinTree<T> &tree){
    show<T> inTemp;
    tree.traverInIterV2(tree.root(),inTemp);
}

template <typename T>
void static postShow(BinTree<T> &tree){
    show<T> postTemp;
    tree.traverPostIter(tree.root(),postTemp);
}