目錄

成都創(chuàng)新互聯(lián)公司是一家專業(yè)從事成都網(wǎng)站設(shè)計(jì)、網(wǎng)站制作的網(wǎng)絡(luò)公司。作為專業(yè)網(wǎng)絡(luò)公司,成都創(chuàng)新互聯(lián)公司依托的技術(shù)實(shí)力、以及多年的網(wǎng)站運(yùn)營經(jīng)驗(yàn),為您提供專業(yè)的成都網(wǎng)站建設(shè)、全網(wǎng)整合營銷推廣及網(wǎng)站設(shè)計(jì)開發(fā)服務(wù)！

非遞歸實(shí)現(xiàn)二叉樹的前序遍歷?

非遞歸實(shí)現(xiàn)二叉樹的中序遍歷

非遞歸實(shí)現(xiàn)二叉樹的后序遍歷

根據(jù)二叉樹的前序和中序遍歷結(jié)果還原二叉樹?

根據(jù)二叉樹的中序和后序遍歷結(jié)果還原二叉樹

---

非遞歸遍歷需要借助棧。?

非遞歸實(shí)現(xiàn)二叉樹的前序遍歷?

前序遍歷：二叉樹的前序遍歷：按照訪問根節(jié)點(diǎn)——左子樹——右子樹的方式遍歷這棵樹，而在訪問左子樹或者右子樹的時(shí)候，我們按照同樣的方式遍歷，直到遍歷完整棵樹。

1. 如果樹為空，直接返回

2. 如果樹非空：從根節(jié)點(diǎn)位置開始遍歷，因?yàn)榍靶虮闅v規(guī)則：根節(jié)點(diǎn)、左子樹、右子樹

a. 沿著根節(jié)點(diǎn)一直往左走，將所經(jīng)過路徑中的節(jié)點(diǎn)依次入棧，并訪問。

? b. 取棧頂元素，該元素取到后，其左子樹要么為空，要么已經(jīng)遍歷，可以直接遍歷該節(jié)點(diǎn)，對(duì)于該節(jié)點(diǎn)，其左子樹已經(jīng)遍歷，該節(jié)點(diǎn)也已經(jīng)遍歷，剩余其右子樹沒有遍歷，將其左子樹當(dāng)成一棵新的樹開始遍歷，繼續(xù)a步驟

vectorpreorderTraversal(TreeNode* root) {
        vectorv;
        stackst;
        TreeNode*cur = root;
        while(cur || !st.empty())
        {
            //循環(huán)每走一次迭代，就是在訪問一棵樹的開始

            //訪問左路節(jié)點(diǎn)，左路節(jié)點(diǎn)入棧
            while(cur)
            {
                st.push(cur);
                v.push_back(cur->val);
                cur = cur->left;
            }

            //取出節(jié)點(diǎn)，訪問右路節(jié)點(diǎn)
            TreeNode* top = st.top();
            st.pop();

            //子問題形式訪問右子樹
            cur = top->right;
        }
        return v;
    }

非遞歸實(shí)現(xiàn)二叉樹的中序遍歷

中序遍歷：按照訪問左子樹——根節(jié)點(diǎn)——右子樹的方式遍歷這棵樹，而在訪問左子樹或者右子樹的時(shí)候我們按照同樣的方式遍歷，直到遍歷完整棵樹。

中序遍歷中，從棧中彈出的節(jié)點(diǎn)，其左子樹是訪問完了，可以直接訪問該節(jié)點(diǎn)，然后接下來訪問右子樹。

1. 如果樹為空，直接返回

2. 如果樹非空：從根節(jié)點(diǎn)位置開始遍歷，因?yàn)榍靶虮闅v規(guī)則：左子樹、根節(jié)點(diǎn)、右子樹

a. 沿著根節(jié)點(diǎn)一直往左走，將所經(jīng)過路徑中的節(jié)點(diǎn)依次入棧，并訪問。

? b. 取棧頂元素，該元素取到后，其左子樹要么為空，要么已經(jīng)遍歷，可以直接遍歷該節(jié)點(diǎn)，對(duì)于該節(jié)點(diǎn)，其左子樹已經(jīng)遍歷，該節(jié)點(diǎn)也已經(jīng)遍歷，剩余其右子樹沒有遍歷，將其左子樹當(dāng)成一棵新的樹開始遍歷，繼續(xù)a步驟

vectorinorderTraversal(TreeNode* root) {
        vectorv;
        stackst;
        TreeNode*cur = root;
        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* top = st.top();
            st.pop();

            v.push_back(top->val);

            cur = top->right;
        }
        return v;
    }

非遞歸實(shí)現(xiàn)二叉樹的后序遍歷

后序遍歷：按照訪問左子樹——右子樹——根節(jié)點(diǎn)的方式遍歷這棵樹，而在訪問左子樹或者右子樹的時(shí)候我們按照同樣的方式遍歷，直到遍歷完整棵樹。

后序遍歷中，從棧中彈出的節(jié)點(diǎn)，我們只能確定其左子樹肯定訪問完了，但是無法確定右子樹是否訪問過。因此，我們?cè)诤笮虮闅v中，引入了一個(gè)prev來記錄歷史訪問記錄。

1. 如果樹為空，直接返回

2. 如果樹非空：從根節(jié)點(diǎn)位置開始遍歷，但此時(shí)根節(jié)點(diǎn)不能遍歷，因?yàn)楹笮虮闅v規(guī)則：左子樹、右子樹、根節(jié)點(diǎn)

?????a. 沿著根節(jié)點(diǎn)一直往左走，將所經(jīng)過路徑中的節(jié)點(diǎn)依次入棧

?????b. 取棧頂元素，該元素取到后，其左子樹要么為空，要么已經(jīng)遍歷，但是此時(shí)該節(jié)點(diǎn)不能遍歷，除非其右子樹不存在或者其右子樹已經(jīng)遍歷，才可以遍歷該節(jié)點(diǎn)，如果該節(jié)點(diǎn)右子樹沒有遍歷，將其右子樹作為一棵新的二叉樹遍歷，繼續(xù)a

• 當(dāng)訪問完一棵子樹的時(shí)候，我們用prev指向該節(jié)點(diǎn)。
• 這樣，在回溯到父節(jié)點(diǎn)的時(shí)候，我們可以依據(jù)prev是指向左子節(jié)點(diǎn)，還是右子節(jié)點(diǎn)，來判斷父節(jié)點(diǎn)的訪問情況。
  

vectorpostorderTraversal(TreeNode* root) {
        vectorv;
        stackst;
        TreeNode* cur = root;
        TreeNode* prev = nullptr;
        while(cur || !st.empty())
        {
            while(cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            TreeNode* top = st.top();
            //現(xiàn)在需要確定的是是否有右子樹，或者右子樹是否訪問過
            //如果沒有右子樹，或者右子樹訪問完了，也就是上一個(gè)訪問的節(jié)點(diǎn)是右子節(jié)點(diǎn)時(shí)
            //說明可以訪問當(dāng)前節(jié)點(diǎn)
            if(top->right == nullptr || top->right == prev)
            {
                v.push_back(top->val);
                //更新歷史訪問記錄，這樣回溯的時(shí)候父節(jié)點(diǎn)可以由此判斷右子樹是否訪問完成
                prev = top;
                st.pop();
            }
            else
            {
                //右子樹沒有訪問過，訪問右子樹
                cur = top->right;
            }
            
        }
        return v;
    }

根據(jù)二叉樹的前序和中序遍歷結(jié)果還原二叉樹?

1. 從前序遍歷結(jié)果中獲取到樹的根節(jié)點(diǎn)

2. 在中序遍歷結(jié)果中確定根節(jié)點(diǎn)的位置，按照該位置將中序遍歷結(jié)果分為兩部分

左半部分是根節(jié)點(diǎn)的左子樹，遞歸創(chuàng)建根節(jié)點(diǎn)的左子樹

右半部分是根節(jié)點(diǎn)的右子樹，遞歸創(chuàng)建根節(jié)點(diǎn)的右子樹

TreeNode* _buildTree(vector& preorder, vector& inorder,int& previ,int inbegin,int inend) {
        if(inbegin >inend)
            return NULL;
        TreeNode* root = new TreeNode(preorder[previ]);
        int rooti = inbegin;
        while(rooti<= inend)
        {
            if(inorder[rooti] == preorder[previ])
                break;
            else
                ++rooti;
                
        }
        ++previ;
        //[inbegin rooti-1] rooti [rooti+1,inend]
        root->left = _buildTree(preorder,inorder,previ,inbegin,rooti-1);
        root->right = _buildTree(preorder,inorder,previ,rooti+1,inend);
        return root;
    }
    TreeNode* buildTree(vector& preorder, vector& inorder) {
        int previ = 0;
       return  _buildTree(preorder,inorder,previ,0,inorder.size()-1);
    }

根據(jù)二叉樹的中序和后序遍歷結(jié)果還原二叉樹

1. 從后序遍歷結(jié)果中獲取到樹的根節(jié)點(diǎn)，注意：后序遍歷規(guī)則：左子樹、右子樹、根節(jié)點(diǎn)，因此應(yīng)該從后往前獲取根節(jié)點(diǎn)

2. 在中序遍歷結(jié)果中確定根節(jié)點(diǎn)的位置，按照該位置將中序遍歷結(jié)果分為兩部分

右半部分是根節(jié)點(diǎn)的右子樹，遞歸創(chuàng)建根節(jié)點(diǎn)的右子樹---->注意先要還原根的右子樹

左半部分是根節(jié)點(diǎn)的左子樹，遞歸創(chuàng)建根節(jié)點(diǎn)的左子樹

TreeNode* _buildTree(vector& inorder, vector& postorder,int& posti,int inbegin,int inend) {
        if(inbegin >inend)
            return NULL;
        TreeNode* root = new TreeNode(postorder[posti]);
        int rooti = inbegin;
        while(rooti<= inend)
        {
            if(postorder[posti] == inorder[rooti])
                break;
            else
                ++rooti;
        }
        --posti;
        root->right = _buildTree(inorder,postorder,posti,rooti+1,inend);
        root->left = _buildTree(inorder,postorder,posti,inbegin,rooti-1);
        
        return root;
    }
    TreeNode* buildTree(vector& inorder, vector& postorder) {
        int posti = postorder.size()-1;
        return _buildTree(inorder,postorder,posti,0,inorder.size()-1);
    }

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章題目：非遞歸實(shí)現(xiàn)二叉樹的前序、中序、后序遍歷-創(chuàng)新互聯(lián)
分享路徑：http://weahome.cn/article/djgsph.html