63      阿裏雲  技術社區[雲棲]

[算法係列之二]二叉樹各種遍曆

【簡介】

樹形結構是一類重要的非線性數據結構，其中以樹和二叉樹最為常用。

二叉樹是每個結點最多有兩個子樹的有序樹。通常子樹的根被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用作二叉查找樹和二叉堆或是二叉排序樹。二叉樹的每個結點至多隻有二棵子樹(不存在度大於2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的 i -1次方個結點；深度為k的二叉樹至多有2^(k) -1個結點；對任何一棵二叉樹T，如果其終端結點數(即葉子結點數)為n0，度為2的結點數為n2，則n0 = n2 + 1。

二叉樹的鏈式存儲結構是一類重要的數據結構，其形式定義如下：

或者

// 二叉樹節點結構
struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};

【二叉樹的創建】

通過讀入一個字符串，建立二叉樹的算法如下：

或者

// 1.創建二叉樹
void CreateTree(TreeNode* &root){
    int val;
    //按先序次序輸入二叉樹中結點的值,‘-1’表示空樹
    cin>>val;
    // 空節點
    if(val == -1){
        root = nullptr;
        return;
    }//if
    root = new TreeNode(val);
    //構造左子樹
    CreateTree(root->left);
    //構造右子樹
    CreateTree(root->right);
}

層次建立二叉樹：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 創建二叉樹
TreeNode* CreateTreeByLevel(vector<char> num){
    int len = num.size();
    if(len == 0){
        return NULL;
    }//if
    queue<TreeNode*> queue;
    int index = 0;
    // 創建根節點
    TreeNode *root = new TreeNode(num[index++]);
    // 入隊列
    queue.push(root);
    TreeNode *p = NULL;
    while(!queue.empty() && index < len){
        // 出隊列
        p = queue.front();
        queue.pop();
        // 左節點
        if(index < len && num[index] != -1){
            // 如果不空創建一個節點
            TreeNode *leftNode = new TreeNode(num[index]);
            p->left = leftNode;
            queue.push(leftNode);
        }
        index++;
        // 右節點
        if(index < len && num[index] != -1){
            // 如果不空創建一個節點
            TreeNode *rightNode = new TreeNode(num[index]);
            p->right = rightNode;
            queue.push(rightNode);
        }
        index++;
    }//while
    return root;
}

創建如上二叉樹輸入：

15 11 20 8 14 -1 -1 -1 -1 13 -1

【二叉樹的遍曆】

遍曆是對樹的一種最基本的運算，所謂遍曆二叉樹，就是按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且隻被訪問一次。由於二叉樹是非線性結構，因此，樹的遍曆實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。

【遞歸算法】

【非遞歸算法】

【先序遍曆】

【思路】：訪問T->data後，將T入棧，遍曆左子樹；遍曆完左子樹返回時，棧頂元素應為T，出棧，再先序遍曆T的右子樹。

// 先序遍曆
void PreOrder(TreeNode* root){
    if(root == NULL){
        return;
    }
    stack<TreeNode*> stack;
    stack.push(root);
    TreeNode *p = NULL;
    while(!stack.empty()){
        p = stack.top();
        stack.pop();
        cout<<p->val<<endl;
        // 右子節點不空壓入棧中
        if(p->right){
            stack.push(p->right);
        }
        // 左子節點不空壓入棧中
        if(p->left){
            stack.push(p->left);
        }
    }//while
}

【中序遍曆】

【思路】：T是要遍曆樹的根指針，中序遍曆要求在遍曆完左子樹後，訪問根，再遍曆右子樹。
         先將T入棧，遍曆左子樹；遍曆完左子樹返回時，棧頂元素應為T，出棧，訪問T->data，再中序遍曆T的右子樹。

【後序遍曆】

【思路】：T是要遍曆樹的根指針，後序遍曆要求在遍曆完左右子樹後，再訪問根。需要判斷根結點的左右子樹是否均遍曆過。

或者

    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> result;
        if(root == nullptr){
            return result;
        }//if
        stack<TreeNode*> s;
        s.push(root);
        TreeNode *node;
        while(!s.empty()){
            node = s.top();
            s.pop();
            result.insert(result.begin(),node->val);
            // 左子樹
            if(node->left){
                s.push(node->left);
            }//if
            // 右子樹
            if(node->right){
                s.push(node->right);
            }//if
        }//while
        return result;
    }

【層次遍曆】

【思路】：按從頂向下，從左至右的順序來逐層訪問每個節點，層次遍曆的過程中需要用隊列。

【測試】

輸入：（先序）

15 11 8 -1 -1 14 13 -1 -1 -1 20 -1 -1

輸出：

代碼一：

    /*-------------------------------------
    *   日期：2015-03-25
    *   作者：SJF0115
    *   題目: 二叉樹各種遍曆
    *   來源：
    *   博客：
    ------------------------------------*/
    #include <iostream>
    #include <vector>
    #include <stack>
    #include <queue>
    using namespace std;

    // 二叉樹節點結構
    struct TreeNode{
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x):val(x),left(nullptr),right(nullptr){}
    };
    // 1.創建二叉樹
    void CreateTree(TreeNode* &root){
        int val;
        //按先序次序輸入二叉樹中結點的值,‘-1’表示空樹
        cin>>val;
        // 空節點
        if(val == -1){
            root = nullptr;
            return;
        }//if
        root = new TreeNode(val);
        //構造左子樹
        CreateTree(root->left);
        //構造右子樹
        CreateTree(root->right);
    }
    // 2.1 遞歸先序遍曆
    void PreOrder(TreeNode* root,vector<int> &result){
        if(root == nullptr){
            return;
        }//if
        result.push_back(root->val);
        // 左子樹
        PreOrder(root->left,result);
        // 右子樹
        PreOrder(root->right,result);
    }
    // 2.2 非遞歸先序遍曆
    void PreOrder2(TreeNode* root,vector<int> &result){
        if(root == nullptr){
            return;
        }//if
        stack<TreeNode*> s;
        s.push(root);
        TreeNode *node;
        while(!s.empty()){
            node = s.top();
            s.pop();
            result.push_back(node->val);
            // 右子樹
            if(node->right){
                s.push(node->right);
            }//if
            // 左子樹
            if(node->left){
                s.push(node->left);
            }//if
        }//while
    }
    // 3.1 遞歸中序遍曆
    void InOrder(TreeNode* root,vector<int> &result){
        if(root == nullptr){
            return;
        }//if
        // 左子樹
        InOrder(root->left,result);
        result.push_back(root->val);
        // 右子樹
        InOrder(root->right,result);
    }
    // 3.2 非遞歸中序遍曆
    void InOrder2(TreeNode* root,vector<int> &result){
        if(root == nullptr){
            return;
        }//if
        stack<TreeNode*> s;
        TreeNode *node = root;
        while(node != nullptr || !s.empty()){
            // 左子樹
            if(node != nullptr){
                s.push(node);
                node = node->left;
            }//if
            // 右子樹
            else{
                node = s.top();
                s.pop();
                result.push_back(node->val);
                node = node->right;
            }
        }//while
    }
    // 4.1 遞歸後序遍曆
    void PostOrder(TreeNode* root,vector<int> &result){
        if(root == nullptr){
            return;
        }//if
        // 左子樹
        PostOrder(root->left,result);
        // 右子樹
        PostOrder(root->right,result);
        result.push_back(root->val);
    }
    // 4.2 非遞歸後序遍曆
    void PostOrder2(TreeNode *root,vector<int> &result) {
        if(root == nullptr){
            return;
        }//if
        stack<TreeNode*> s;
        s.push(root);
        TreeNode *node;
        while(!s.empty()){
            node = s.top();
            s.pop();
            result.insert(result.begin(),node->val);
            // 左子樹
            if(node->left){
                s.push(node->left);
            }//if
            // 右子樹
            if(node->right){
                s.push(node->right);
            }//if
        }//while
    }
    // 5 層次遍曆
    void LevelOrder(TreeNode* root,vector<int> &result){
        if(root == nullptr){
            return;
        }//if
        queue<TreeNode*> queue;
        queue.push(root);
        TreeNode *node;
        while(!queue.empty()){
            node = queue.front();
            queue.pop();
            result.push_back(node->val);
            // 左子樹
            if(node->left){
                queue.push(node->left);
            }//if
            // 右子樹
            if(node->right){
                queue.push(node->right);
            }//if
        }//while
    }
    // 輸出結果
    void Print(vector<int> result){
        int size = result.size();
        for(int i = 0;i < size;++i){
            cout<<result[i]<<" ";
        }//for
        cout<<endl;
    }
    int main(){
        freopen("C:\\Users\\Administrator\\Desktop\\c++.txt", "r", stdin);
        TreeNode* root = nullptr;
        vector<int> result;
        // 創建二叉樹
        cout<<"1. 創建二叉樹"<<endl;
        CreateTree(root);
        cout<<"-----------------------------"<<endl;

        cout<<"2.1 遞歸先序遍曆"<<endl;
        PreOrder(root,result);
        Print(result);
        result.clear();
        cout<<"-----------------------------"<<endl;

        cout<<"2.2 非遞歸先序遍曆"<<endl;
        PreOrder2(root,result);
        Print(result);
        result.clear();
        cout<<"-----------------------------"<<endl;

        cout<<"3.1 遞歸中序遍曆"<<endl;
        InOrder(root,result);
        Print(result);
        result.clear();
        cout<<"-----------------------------"<<endl;

        cout<<"3.2 非遞歸中序遍曆"<<endl;
        InOrder2(root,result);
        Print(result);
        result.clear();
        cout<<"-----------------------------"<<endl;

        cout<<"4.1 遞歸後序遍曆"<<endl;
        PostOrder(root,result);
        Print(result);
        result.clear();
        cout<<"-----------------------------"<<endl;

        cout<<"4.2 非遞歸後序遍曆"<<endl;
        PostOrder2(root,result);
        Print(result);
        result.clear();
        cout<<"-----------------------------"<<endl;

        cout<<"5 層次遍曆"<<endl;
        LevelOrder(root,result);
        Print(result);
        result.clear();
        cout<<"-----------------------------"<<endl;
        return 0;
    }

測試用例：

輸入：

ABC##DE#G##F###

輸出：

代碼二：

最後更新：2017-04-03 12:56:27

  上一篇： 淺談C#中new、override、virtual關鍵字的區別

  下一篇： 麵試經之一道淘汰85%麵試者的百度開發者麵試題