前序

// 遞歸
public void preOrderTraverse(TreeNode root) {  
        if (root != null) {  
            System.out.print(root.val+"  ");  
            preOrderTraverse1(root.left);  
            preOrderTraverse1(root.right);  
        }  
    }  

// 非遞歸
public void preOrderTraverse(TreeNode root) {  
        LinkedList<TreeNode> stack = new LinkedList<>();  
        TreeNode pNode = root;  
        while (pNode != null || !stack.isEmpty()) {  
            if (pNode != null) {  
                System.out.print(pNode.val+"  ");  
                stack.push(pNode);  
                pNode = pNode.left;  
            } else { 
                TreeNode node = stack.pop();  
                pNode = node.right;  
            }  
        }  
    }  

中序

public void inOrderTraverse(TreeNode root) {  
        LinkedList<TreeNode> stack = new LinkedList<>();  
        TreeNode pNode = root;  
        while (pNode != null || !stack.isEmpty()) {  
            if (pNode != null) {  
                stack.push(pNode);  
                pNode = pNode.left;  
            } else { //pNode == null && !stack.isEmpty()  
                TreeNode node = stack.pop();  
                System.out.print(node.val+"  ");  
                pNode = node.right;  
            }  
        }  
    }  

后序

兩種策略

1. 對于任一結(jié)點(diǎn)P，將其入棧，然后沿其左子樹一直往下搜索。直到搜索到?jīng)]有左孩子的結(jié)點(diǎn)，此時該結(jié)點(diǎn)出如今棧頂，可是此時不能將其出棧并訪問，因此其右孩子還為被訪問。

void postOrder3(BinTree *root)     //非遞歸后序遍歷
{
    stack<BinTree*> s;
    BinTree *cur;                      //當(dāng)前結(jié)點(diǎn) 
    BinTree *pre=NULL;                 //前一次訪問的結(jié)點(diǎn) 
    s.push(root);
    while(!s.empty())
    {
        cur=s.top();
        if((cur->lchild==NULL&&cur->rchild==NULL)||
           (pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
        {
            cout<<cur->data<<" ";  //假設(shè)當(dāng)前結(jié)點(diǎn)沒有孩子結(jié)點(diǎn)或者孩子節(jié)點(diǎn)都已被訪問過 
              s.pop();
            pre=cur; 
        }
        else
        {
            if(cur->rchild!=NULL)
                s.push(cur->rchild);
            if(cur->lchild!=NULL)    
                s.push(cur->lchild);
        }
    }    
}

2. 要保證根結(jié)點(diǎn)在左孩子和右孩子訪問之后才干訪問，因此對于任一結(jié)點(diǎn)P。先將其入棧。假設(shè)P不存在左孩子和右孩子。則能夠直接訪問它；或者P存在左孩子或者右孩子。可是其左孩子和右孩子都已被訪問過了。則相同能夠直接訪問該結(jié)點(diǎn)。若非上述兩種情況。則將P的右孩子和左孩子依次入棧。這樣就保證了每次取棧頂元素的時候，左孩子在右孩子前面被訪問。左孩子和右孩子都在根結(jié)點(diǎn)前面被訪問。

void postOrder2(BinTree *root)    //非遞歸后序遍歷
{
    stack<BTNode*> s;
    BinTree *p=root;
    BTNode *temp;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)              //沿左子樹一直往下搜索。直至出現(xiàn)沒有左子樹的結(jié)點(diǎn) 
        {
            BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
            btn->btnode=p;
            btn->isFirst=true;
            s.push(btn);
            p=p->lchild;
        }
        if(!s.empty())
        {
            temp=s.top();
            s.pop();
            if(temp->isFirst==true)     //表示是第一次出如今棧頂 
             {
                temp->isFirst=false;
                s.push(temp);
                p=temp->btnode->rchild;    
            }
            else                        //第二次出如今棧頂 
             {
                cout<<temp->btnode->data<<" ";
                p=NULL;
            }
        }
    }    
} 

廣度

public void levelTraverse(TreeNode root) {  
        if (root == null) {  
            return;  
        }  
        LinkedList<TreeNode> queue = new LinkedList<>();  
        queue.offer(root);  
        while (!queue.isEmpty()) {  
            TreeNode node = queue.poll();  
            System.out.print(node.val+"  ");  
            if (node.left != null) {  
                queue.offer(node.left);  
            }  
            if (node.right != null) {  
                queue.offer(node.right);  
            }  
        }  
    }