對(duì)于一棵二叉樹一般有三種遍歷方式，先序遍歷（preOrder）、中序遍歷(inOrder)、后序遍歷(postOrder)。

同時(shí)這里還介紹了二叉樹的 層次遍歷(levelOrder)

每種遍歷都有遞歸的實(shí)現(xiàn)和非遞歸的實(shí)現(xiàn)。

1、preOrder

對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行遍歷，并將right節(jié)點(diǎn)push到一個(gè)stack中

//遞歸實(shí)現(xiàn)
void preOrder1(BinTree *root)     //遞歸前序遍歷 
{
    if(root!=NULL)
    {
        cout<<root->data<<" ";
        preOrder1(root->lchild);
        preOrder1(root->rchild);
    }
}

//非遞歸
void preOrder2(BinTree *root)     //非遞歸前序遍歷 
{
    stack<BinTree*> s;
    BinTree *p=root;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            cout<<p->data<<" ";
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            s.pop();
            p=p->rchild;
        }
    }
}

2、inOrder

通過(guò)一個(gè)stack存儲(chǔ)遍歷的中心節(jié)點(diǎn)，知道最左邊的節(jié)點(diǎn)，然后對(duì)stack進(jìn)行pop操作。

//遞歸實(shí)現(xiàn)
void inOrder1(BinTree *root)      //遞歸中序遍歷
{
    if(root!=NULL)
    {
        inOrder1(root->lchild);
        cout<<root->data<<" ";
        inOrder1(root->rchild);
    }
} 
//非遞歸實(shí)現(xiàn)
void inOrder2(BinTree *root)      //非遞歸中序遍歷
{
    stack<BinTree*> s;
    BinTree *p=root;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            cout<<p->data<<" ";
            s.pop();
            p=p->rchild;
        }
    }    
} 

3、postOrder

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

//遞歸

void postOrder1(BinTree *root)    //遞歸后序遍歷
{
    if(root!=NULL)
    {
        postOrder1(root->lchild);
        postOrder1(root->rchild);
        cout<<root->data<<" ";
    }    
} 

//非遞歸
void postOrder(BinTree *root)     //非遞歸后序遍歷
{
    stack<BinTree*> s;
    BinTree *cur;                      //當(dāng)前結(jié)點(diǎn) 
    BinTree *pre=NULL;                 //前一次訪問(wèn)的結(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<<" ";  //如果當(dāng)前結(jié)點(diǎn)沒(méi)有孩子結(jié)點(diǎn)或者孩子節(jié)點(diǎn)都已被訪問(wèn)過(guò) 
              s.pop();
            pre=cur; 
        }
        else
        {
            if(cur->rchild!=NULL)
                s.push(cur->rchild);
            if(cur->lchild!=NULL)    
                s.push(cur->lchild);
        }
    }    
}

4、層次遍歷

一次從左到右輸出一顆二叉樹的 每一層元素。

定義兩個(gè)queue，將其中一個(gè)queue中每個(gè)元素的左右節(jié)點(diǎn)一次push進(jìn)另一個(gè)queue中，直到該隊(duì)列為空。

然后訪問(wèn)另一queue執(zhí)行同樣的操作。

//leetcode中遍歷的方法
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode *> in1,in2;
        vector<vector<int>> re;
        if (root == NULL) return re;
        in1.push(root);
        while (!in1.empty()||!in2.empty()){
            vector<int> temp;
            if (!in1.empty()){
                while (!in1.empty()){
                    TreeNode    *p = in1.front();
                    in1.pop();
                    temp.push_back(p->val);
                    if (p->left != NULL) in2.push(p->left);
                    if (p->right!= NULL) in2.push(p->right);
                }
            }
            else {
                while (!in2.empty()){
                    TreeNode    *p = in2.front();
                    in2.pop();
                    temp.push_back(p->val);
                    if (p->left != NULL) in1.push(p->left);
                    if (p->right != NULL) in1.push(p->right);
                }
            }
            re.push_back(temp);
        }
        return re;
    }
};

總結(jié)

以上是生活随笔為你收集整理的二叉树的遍历的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。