一、递归

先序遍历

void PreOrderRecur(TreeNode *head){
    if(head==NULL) return;
    std::cout<<head->value<<std::endl;
    PreOrderRecur(head->left);  
    PreOrderRecur(head->right;    
}

中序遍历

void InOrderRecur(){
    if(head==NULL) return;
    InOrderRecur(head->left);
    std::cout<<head->value<<std::endl;  
    InOrderRecur(head->right;  
}

后序遍历

void PostOrderRecur(){
    if(head==NULL) return;
    PostOrderRecur(head->left);
    PostOrderRecur(head->right;
    std::cout<<head->value<<std::endl;    
}

二、非递归

先序遍历

孩子结点入栈的时候，是右结点先入栈，保证左结点在上面先出栈

void PreOrderUnRecur(TreeNode *head){
    if(head != NULL){
        stack<int> mystack;
        mystack.push(head);
        while(!mystack.empty()){
            head = mystack.top(); //弹栈
            std::cout<<head->value<<std::endl;
            mystack.pop();
            if(head->right !=NULL) //先右
                mystack.push(head->right);
            if(head->left !=NULL) //再左
                mystack.push(head->left);
        }
    }
}

中序遍历

void InOrderUnRecur(TreeNode *head){
    if(head != NULL){
        stack<int> mystack;
        while(!mystack.empty()){
            if(head != NULL){ //一直向左压栈直到空指针
                mystack.push(head);
                head = head->left;
            }else{
                head = mystack.top(); //以下三句弹栈访问
                mystack.pop();
                std::cout<<head->value<<std::endl;
                head = head->right; //向左，重复以上步骤
            }
        }
    }
}

后序遍历 ！！！

void PostOrderUnRecur(TreeNode *head){
    if(head !=NULL){
        stack<int> mystack;
        mystack.push(head);
        TreeNode *c =NULL;

        while(!mystack.empty()){
            c = mystack.top(); //栈顶结点
            if(c->left != NULL && head ！= c->left && head != c->right) //head 为最近访问的结点
                mystack.push(c->left)
            else if(c->right != NULL && head != c->right)
                mystack.push(c->right)
            else{
                std::cout<<c->val<<std::endl;
                mystack.pop();
                head = c;
            }
                
        }
    }
}