閱讀908 返回首頁    go 技術社區[雲棲]

[算法係列之三]二叉樹中序前序序列(或後序)求解樹

【思路】

這種題一般有二種形式，共同點是都已知中序序列。如果沒有中序序列，是無法唯一確定一棵樹的。

<1>已知二叉樹的前序序列和中序序列，求解樹。

1、確定樹的根節點。樹根是當前樹中所有元素在前序遍曆中最先出現的元素。

2、求解樹的子樹。找出根節點在中序遍曆中的位置，根左邊的所有元素就是左子樹，根右邊的所有元素就是右子樹。若根節點左邊或右邊為空，則該方向子樹為空；若根節點

邊和右邊都為空，則根節點已經為葉子節點。

3、遞歸求解樹。將左子樹和右子樹分別看成一棵二叉樹，重複1、2、3步，直到所有的節點完成定位。

<2>、已知二叉樹的後序序列和中序序列，求解樹。

1、確定樹的根。樹根是當前樹中所有元素在後序遍曆中最後出現的元素。

2、求解樹的子樹。找出根節點在中序遍曆中的位置，根左邊的所有元素就是左子樹，根右邊的所有元素就是右子樹。若根節點左邊或右邊為空，則該方向子樹為空；若根節點

邊和右邊都為空，則根節點已經為葉子節點。

3、遞歸求解樹。將左子樹和右子樹分別看成一棵二叉樹，重複1、2、3步，直到所有的節點完成定位。

測試用例：


【先序 中序 求 後序】

輸入：

先序序列：ABCDEGF

中序序列：CBEGDFA

輸出後序：CGEFDBA

代碼：

  1. /* 
  2.     PreIndex: 前序序列字符串中子樹的第一個節點在PreArray[]中的下標 
  3.     InIndex:  中序序列字符串中子樹的第一個節點在InArray[]中的下標 
  4.     subTreeLen: 子樹的字符串序列的長度 
  5.     PreArray： 先序序列數組 
  6.     InArray：中序序列數組 
  7. */  
  8. void PreInCreateTree(BiTree &T,int PreIndex,int InIndex,int subTreeLen){  
  9.     //subTreeLen < 0 子樹為空  
  10.     if(subTreeLen <= 0){  
  11.         T = NULL;  
  12.         return;  
  13.     }  
  14.     else{  
  15.         T = (BiTree)malloc(sizeof(BiTNode));  
  16.         //創建根節點  
  17.         T->data = PreArray[PreIndex];  
  18.         //找到該節點在中序序列中的位置  
  19.         int index = strchr(InArray,PreArray[PreIndex]) - InArray;  
  20.         //左子樹結點個數  
  21.         int LenF = index - InIndex;  
  22.         //創建左子樹  
  23.         PreInCreateTree(T->lchild,PreIndex + 1,InIndex,LenF);  
  24.         //右子樹結點個數(總結點 - 根節點 - 左子樹結點)  
  25.         int LenR = subTreeLen - 1 - LenF;  
  26.         //創建右子樹  
  27.         PreInCreateTree(T->rchild,PreIndex + LenF + 1,index + 1,LenR);  
  28.     }  
  29. }  

主函數調用：

  1. BiTree T;  
  2.     PreInCreateTree(T,0,0,strlen(InArray));  
  3.     PostOrder(T);  



另一種算法：

  1. /* 
  2.     PreS       先序序列的第一個元素下標 
  3.     PreE       先序序列的最後一個元素下標 
  4.     InS        中序序列的第一個元素下標  
  5.     InE        先序序列的最後一個元素下標   
  6.     PreArray   先序序列數組 
  7.     InArray    中序序列數組 
  8. */  
  9. void PreInCreateTree(BiTree &T,int PreS ,int PreE ,int InS ,int InE){  
  10.     int RootIndex;  
  11.     //先序第一個字符  
  12.     T = (BiTree)malloc(sizeof(BiTNode));   
  13.     T->data = PreArray[PreS];  
  14.     //尋找該結點在中序序列中的位置  
  15.     for(int i = InS;i <= InE;i++){  
  16.         if(T->data == InArray[i]){  
  17.             RootIndex = i;  
  18.             break;  
  19.         }  
  20.     }  
  21.     //根結點的左子樹不為空  
  22.     if(RootIndex != InS){  
  23.         //以根節點的左結點為根建樹  
  24.         PreInCreateTree(T->lchild,PreS+1,(RootIndex-InS)+PreS,InS,RootIndex-1);  
  25.     }  
  26.     else{  
  27.         T->lchild = NULL;  
  28.     }  
  29.     //根結點的右子樹不為空  
  30.     if(RootIndex != InE){  
  31.         //以根節點的右結點為根建樹  
  32.         PreInCreateTree(T->rchild,PreS+1+(RootIndex-InS),PreE,RootIndex+1,InE);  
  33.     }  
  34.     else{  
  35.         T->rchild = NULL;  
  36.     }  
  37. }  
主函數調用：
  1. PreInCreateTree(T,0,strlen(PreArray)-1,0,strlen(InArray)-1);   


/*---------------------------------------
*   日期：2015-04-28
*   作者：SJF0115
*   題目: 105.Construct Binary Tree from Preorder and Inorder Traversal
*   網址：https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
*   結果：AC
*   來源：LeetCode
*   博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        int size = preorder.size();
        if(size <= 0){
            return nullptr;
        }//if
        return PreInBuildTree(preorder,inorder,0,0,size);
    }
private:
    TreeNode* PreInBuildTree(vector<int> &preorder,vector<int> &inorder,int preIndex,int inIndex,int size){
        if(size <= 0){
            return nullptr;
        }//if
        // 根節點
        TreeNode* root = new TreeNode(preorder[preIndex]);
        // 尋找根節點在中序遍曆數組的下標
        int index = 0;
        for(int i = 0;i < size;++i){
            if(preorder[preIndex] == inorder[inIndex+i]){
                index = inIndex+i;
                break;
            }//if
        }//for
        // 左子樹個數
        int leftSize = index - inIndex;
        // 右子樹個數
        int rightSize = size - leftSize - 1;
        // 左子樹
        root->left = PreInBuildTree(preorder,inorder,preIndex+1,inIndex,leftSize);
        // 右子樹
        root->right = PreInBuildTree(preorder,inorder,preIndex+1+leftSize,index+1,rightSize);
        return root;
    }
};

void PostOrder(TreeNode* root){
    if(root){
        PostOrder(root->left);
        PostOrder(root->right);
        cout<<root->val<<endl;
    }//if
}

int main(){
    Solution solution;
    vector<int> preorder = {1,2,4,8,5,3,6,7};
    vector<int> inorder = {8,4,2,5,1,6,3,7};
    TreeNode* root = solution.buildTree(preorder,inorder);
    // 輸出
    PostOrder(root);
    return 0;
}



具體講解請看：點擊打開鏈接


【中序 後序 求先序】

輸入：

中序序列：CBEGDFA

後序序列：CGEFDBA

輸出先序：ABCDEGF


代碼：

  1. /* 
  2.     PostIndex: 後序序列字符串中子樹的最後一個節點在PreArray[]中的下標 
  3.     InIndex:  中序序列字符串中子樹的第一個節點在InArray[]中的下標 
  4.     subTreeLen: 子樹的字符串序列的長度 
  5.     PostArray： 後序序列數組 
  6.     InArray：中序序列數組 
  7. */  
  8. void PostInCreateTree(BiTree &T,int PostIndex,int InIndex,int subTreeLen){  
  9.     //subTreeLen < 0 子樹為空  
  10.     if(subTreeLen <= 0){  
  11.         T = NULL;  
  12.         return;  
  13.     }  
  14.     else{  
  15.         T = (BiTree)malloc(sizeof(BiTNode));  
  16.         //創建根節點  
  17.         T->data = PostArray[PostIndex];  
  18.         //找到該節點在中序序列中的位置  
  19.         int index = strchr(InArray,PostArray[PostIndex]) - InArray;  
  20.         //左子樹結點個數  
  21.         int LenF = index - InIndex;  
  22.         //創建左子樹  
  23.         PostInCreateTree(T->lchild,PostIndex - (subTreeLen - 1 - LenF) - 1,InIndex,LenF);  
  24.         //右子樹結點個數(總結點 - 根節點 - 左子樹結點)  
  25.         int LenR = subTreeLen - 1 - LenF;  
  26.         //創建右子樹  
  27.         PostInCreateTree(T->rchild,PostIndex-1,index + 1,LenR);  
  28.     }  
  29. }  

主函數調用：

  1. BiTree T2;  
  2.     PostInCreateTree(T2,strlen(PostArray) - 1,0,strlen(InArray));  
  3.     PreOrder(T2);   

/*---------------------------------------
*   日期：2015-05-01
*   作者：SJF0115
*   題目: 106.Construct Binary Tree from Inorder and Postorder Traversal
*   網址：https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
*   結果：AC
*   來源：LeetCode
*   博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
using namespace std;

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

class Solution {
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        int size = inorder.size();
        if(size <= 0){
            return nullptr;
        }//if
        return InPostBuildTree(inorder,postorder,0,size-1,size);
    }
private:
    TreeNode* InPostBuildTree(vector<int> &inorder,vector<int> &postorder,int inIndex,int postIndex,int size){
        if(size <= 0){
            return nullptr;
        }//if
        // 根節點
        TreeNode* root = new TreeNode(postorder[postIndex]);
        // 尋找postorder[postIndex]在中序序列中的下標
        int index = 0;
        for(int i = 0;i < size;++i){
            if(postorder[postIndex] == inorder[inIndex+i]){
                index = inIndex+i;
                break;
            }//if
        }//for
        int leftSize = index - inIndex;
        int rightSize = size - leftSize - 1;
        root->left = InPostBuildTree(inorder,postorder,inIndex,postIndex-1-rightSize,leftSize);
        root->right = InPostBuildTree(inorder,postorder,index+1,postIndex-1,rightSize);
        return root;
    }
};

void PreOrder(TreeNode* root){
    if(root){
        cout<<root->val<<endl;
        PreOrder(root->left);
        PreOrder(root->right);
    }//if
}

int main() {
    Solution solution;
    vector<int> inorder = {8,4,2,5,1,6,3,7};
    vector<int> postorder = {8,4,5,2,6,7,3,1};
    TreeNode* root = solution.buildTree(inorder,postorder);
    PreOrder(root);
}




完整代碼：

  1. #include<iostream>  
  2. #include<string>  
  3. using namespace std;  
  4.   
  5. //二叉樹結點  
  6. typedef struct BiTNode{  
  7.     //數據  
  8.     char data;  
  9.     //左右孩子指針  
  10.     struct BiTNode *lchild,*rchild;  
  11. }BiTNode,*BiTree;  
  12.   
  13. //先序序列  
  14. char PreArray[101] = "ABCDEGF";  
  15. //中序序列  
  16. char InArray[101] = "CBEGDFA";  
  17. //後序序列  
  18. char PostArray[101] = "CGEFDBA";  
  19. /* 
  20.     PreIndex: 前序序列字符串中子樹的第一個節點在PreArray[]中的下標 
  21.     InIndex:  中序序列字符串中子樹的第一個節點在InArray[]中的下標 
  22.     subTreeLen: 子樹的字符串序列的長度 
  23.     PreArray： 先序序列數組 
  24.     InArray：中序序列數組 
  25. */  
  26. void PreInCreateTree(BiTree &T,int PreIndex,int InIndex,int subTreeLen){  
  27.     //subTreeLen < 0 子樹為空  
  28.     if(subTreeLen <= 0){  
  29.         T = NULL;  
  30.         return;  
  31.     }  
  32.     else{  
  33.         T = (BiTree)malloc(sizeof(BiTNode));  
  34.         //創建根節點  
  35.         T->data = PreArray[PreIndex];  
  36.         //找到該節點在中序序列中的位置  
  37.         int index = strchr(InArray,PreArray[PreIndex]) - InArray;  
  38.         //左子樹結點個數  
  39.         int LenF = index - InIndex;  
  40.         //創建左子樹  
  41.         PreInCreateTree(T->lchild,PreIndex + 1,InIndex,LenF);  
  42.         //右子樹結點個數(總結點 - 根節點 - 左子樹結點)  
  43.         int LenR = subTreeLen - 1 - LenF;  
  44.         //創建右子樹  
  45.         PreInCreateTree(T->rchild,PreIndex + LenF + 1,index + 1,LenR);  
  46.     }  
  47. }  
  48. /* 
  49.     PostIndex: 後序序列字符串中子樹的最後一個節點在PreArray[]中的下標 
  50.     InIndex:  中序序列字符串中子樹的第一個節點在InArray[]中的下標 
  51.     subTreeLen: 子樹的字符串序列的長度 
  52.     PostArray： 後序序列數組 
  53.     InArray：中序序列數組 
  54. */  
  55. void PostInCreateTree(BiTree &T,int PostIndex,int InIndex,int subTreeLen){  
  56.     //subTreeLen < 0 子樹為空  
  57.     if(subTreeLen <= 0){  
  58.         T = NULL;  
  59.         return;  
  60.     }  
  61.     else{  
  62.         T = (BiTree)malloc(sizeof(BiTNode));  
  63.         //創建根節點  
  64.         T->data = PostArray[PostIndex];  
  65.         //找到該節點在中序序列中的位置  
  66.         int index = strchr(InArray,PostArray[PostIndex]) - InArray;  
  67.         //左子樹結點個數  
  68.         int LenF = index - InIndex;  
  69.         //創建左子樹  
  70.         PostInCreateTree(T->lchild,PostIndex - (subTreeLen - 1 - LenF) - 1,InIndex,LenF);  
  71.         //右子樹結點個數(總結點 - 根節點 - 左子樹結點)  
  72.         int LenR = subTreeLen - 1 - LenF;  
  73.         //創建右子樹  
  74.         PostInCreateTree(T->rchild,PostIndex-1,index + 1,LenR);  
  75.     }  
  76. }  
  77. //先序遍曆    
  78. void PreOrder(BiTree T){    
  79.     if(T != NULL){    
  80.         //訪問根節點    
  81.         printf("%c ",T->data);  
  82.         //訪問左子結點    
  83.         PreOrder(T->lchild);    
  84.         //訪問右子結點    
  85.         PreOrder(T->rchild);     
  86.     }    
  87. }    
  88. //後序遍曆    
  89. void PostOrder(BiTree T){    
  90.     if(T != NULL){    
  91.         //訪問左子結點    
  92.         PostOrder(T->lchild);    
  93.         //訪問右子結點    
  94.         PostOrder(T->rchild);   
  95.         //訪問根節點    
  96.         printf("%c ",T->data);  
  97.     }    
  98. }    
  99. int main()  
  100. {  
  101.     BiTree T;  
  102.     PreInCreateTree(T,0,0,strlen(InArray));  
  103.     PostOrder(T);  
  104.     printf("\n");  
  105.     BiTree T2;  
  106.     PostInCreateTree(T2,strlen(PostArray) - 1,0,strlen(InArray));  
  107.     PreOrder(T2);  
  108.     return 0;  
  109. }  

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

  上一篇：go Office 2010 安裝過程中出錯
  下一篇：go ASP.NET 數據庫訪問通用工具