一、遞歸

先序遍歷

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;    
}

二吃度、非遞歸

先序遍歷

孩子結(jié)點入棧的時候甩挫，是右結(jié)點先入棧，保證左結(jié)點在上面先出棧

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(); //棧頂結(jié)點
            if(c->left != NULL && head 亦渗！= c->left && head != c->right) //head 為最近訪問的結(jié)點
                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;
            }
                
        }
    }
}