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

這種題一般有二種形式，共同點是都已知中序序列。如果沒有中序序列，是無法唯一確定一棵樹的。   <1>已知二叉樹的前序序列和中序序列，求解樹。   1、確定樹的根節點。樹根是當前樹中所有元素在前序遍歷中最先出現的元素。   2、求解樹的子樹。找出根節點在中序遍歷中的位置，根左邊的所有元素就是左子樹，根右邊的所有元素就是右子樹。若根節點左邊或右邊為空，則該方向子樹為空；若根節點   邊和右邊都為空，則根節點已經為葉子節點。   3、遞歸求解樹。將左子樹和右子樹分別看成一棵二叉樹，重復1、2、3步，直到所有的節點完成定位。   <2>、已知二叉樹的後序序列和中序序列，求解樹。   1、確定樹的根。樹根是當前樹中所有元素在後序遍歷中最後出現的元素。   2、求解樹的子樹。找出根節點在中序遍歷中的位置，根左邊的所有元素就是左子樹，根右邊的所有元素就是右子樹。若根節點左邊或右邊為空，則該方向子樹為空；若根節點   邊和右邊都為空，則根節點已經為葉子節點。   3、遞歸求解樹。將左子樹和右子樹分別看成一棵二叉樹，重復1、2、3步，直到所有的節點完成定位。   測試用例：       <1>先序 中序 求 後序   輸入：   先序序列：ABCDEGF     中序序列：CBEGDFA   輸出後序：CGEFDBA   代碼：     [cpp] /*      PreIndex: 前序序列字符串中子樹的第一個節點在PreArray[]中的下標      InIndex:  中序序列字符串中子樹的第一個節點在InArray[]中的下標      subTreeLen: 子樹的字符串序列的長度      PreArray： 先序序列數組      InArray：中序序列數組  */   void PreInCreateTree(BiTree &T,int PreIndex,int InIndex,int subTreeLen){       //subTreeLen < 0 子樹為空        if(subTreeLen <= 0){           T = NULL;           return;       }       else{           T = (BiTree)malloc(sizeof(BiTNode));           //創建根節點            T->data = PreArray[PreIndex];           //找到該節點在中序序列中的位置            int index = strchr(InArray,PreArray[PreIndex]) - InArray;           //左子樹結點個數            int LenF = index - InIndex;           //創建左子樹            PreInCreateTree(T->lchild,PreIndex + 1,InIndex,LenF);           //右子樹結點個數(總結點 - 根節點 - 左子樹結點)            int LenR = subTreeLen - 1 - LenF;           //創建右子樹            PreInCreateTree(T->rchild,PreIndex + LenF + 1,index + 1,LenR);       }   }     /* PreIndex: 前序序列字符串中子樹的第一個節點在PreArray[]中的下標     InIndex:  中序序列字符串中子樹的第一個節點在InArray[]中的下標 subTreeLen: 子樹的字符串序列的長度 PreArray： 先序序列數組 InArray：中序序列數組 */ void PreInCreateTree(BiTree &T,int PreIndex,int InIndex,int subTreeLen){ //subTreeLen < 0 子樹為空 if(subTreeLen <= 0){ T = NULL; return; } else{ T = (BiTree)malloc(sizeof(BiTNode)); //創建根節點 T->data = PreArray[PreIndex]; //找到該節點在中序序列中的位置 int index = strchr(InArray,PreArray[PreIndex]) - InArray; //左子樹結點個數 int LenF = index - InIndex; //創建左子樹 PreInCreateTree(T->lchild,PreIndex + 1,InIndex,LenF); //右子樹結點個數(總結點 - 根節點 - 左子樹結點) int LenR = subTreeLen - 1 - LenF; //創建右子樹 PreInCreateTree(T->rchild,PreIndex + LenF + 1,index + 1,LenR); } } 主函數調用：     [cpp]  BiTree T;       PreInCreateTree(T,0,0,strlen(InArray));       PostOrder(T);     BiTree T; PreInCreateTree(T,0,0,strlen(InArray)); PostOrder(T);   <2>中序 後序 求先序   輸入：   中序序列：CBEGDFA   後序序列：CGEFDBA   輸出先序：ABCDEGF         代碼：     [cpp]  /*      PostIndex: 後序序列字符串中子樹的最後一個節點在PreArray[]中的下標      InIndex:  中序序列字符串中子樹的第一個節點在InArray[]中的下標      subTreeLen: 子樹的字符串序列的長度      PostArray： 後序序列數組      InArray：中序序列數組  */   void PostInCreateTree(BiTree &T,int PostIndex,int InIndex,int subTreeLen){       //subTreeLen < 0 子樹為空        if(subTreeLen <= 0){           T = NULL;           return;       }       else{           T = (BiTree)malloc(sizeof(BiTNode));           //創建根節點            T->data = PostArray[PostIndex];           //找到該節點在中序序列中的位置            int index = strchr(InArray,PostArray[PostIndex]) - InArray;           //左子樹結點個數            int LenF = index - InIndex;           //創建左子樹            PostInCreateTree(T->lchild,PostIndex - (subTreeLen - 1 - LenF) - 1,InIndex,LenF);           //右子樹結點個數(總結點 - 根節點 - 左子樹結點)            int LenR = subTreeLen - 1 - LenF;           //創建右子樹            PostInCreateTree(T->rchild,PostIndex-1,index + 1,LenR);       }   }     /* PostIndex: 後序序列字符串中子樹的最後一個節點在PreArray[]中的下標     InIndex:  中序序列字符串中子樹的第一個節點在InArray[]中的下標 subTreeLen: 子樹的字符串序列的長度 PostArray： 後序序列數組 InArray：中序序列數組 */ void PostInCreateTree(BiTree &T,int PostIndex,int InIndex,int subTreeLen){ //subTreeLen < 0 子樹為空 if(subTreeLen <= 0){ T = NULL; return; } else{ T = (BiTree)malloc(sizeof(BiTNode)); //創建根節點 T->data = PostArray[PostIndex]; //找到該節點在中序序列中的位置 int index = strchr(InArray,PostArray[PostIndex]) - InArray; //左子樹結點個數 int LenF = index - InIndex; //創建左子樹 PostInCreateTree(T->lchild,PostIndex - (subTreeLen - 1 - LenF) - 1,InIndex,LenF); //右子樹結點個數(總結點 - 根節點 - 左子樹結點) int LenR = subTreeLen - 1 - LenF; //創建右子樹 PostInCreateTree(T->rchild,PostIndex-1,index + 1,LenR); } } 主函數調用：     [cpp]  ?BiTree T2;       PostInCreateTree(T2,strlen(PostArray) - 1,0,strlen(InArray));       PreOrder(T2);     BiTree T2; PostInCreateTree(T2,strlen(PostArray) - 1,0,strlen(InArray)); PreOrder(T2);                   完整代碼：     [cpp]  #include<iostream>    #include<string>    using namespace std;      //二叉樹結點    typedef struct BiTNode{       //數據        char data;       //左右孩子指針        struct BiTNode *lchild,*rchild;   }BiTNode,*BiTree;      //先序序列    char PreArray[101] = "ABCDEGF";   //中序序列    char InArray[101] = "CBEGDFA";   //後序序列    char PostArray[101] = "CGEFDBA";   /*      PreIndex: 前序序列字符串中子樹的第一個節點在PreArray[]中的下標      InIndex:  中序序列字符串中子樹的第一個節點在InArray[]中的下標      subTreeLen: 子樹的字符串序列的長度      PreArray： 先序序列數組      InArray：中序序列數組  */   void PreInCreateTree(BiTree &T,int PreIndex,int InIndex,int subTreeLen){       //subTreeLen < 0 子樹為空        if(subTreeLen <= 0){           T = NULL;           return;       }       else{           T = (BiTree)malloc(sizeof(BiTNode));           //創建根節點            T->data = PreArray[PreIndex];           //找到該節點在中序序列中的位置            int index = strchr(InArray,PreArray[PreIndex]) - InArray;           //左子樹結點個數            int LenF = index - InIndex;           //創建左子樹            PreInCreateTree(T->lchild,PreIndex + 1,InIndex,LenF);           //右子樹結點個數(總結點 - 根節點 - 左子樹結點)            int LenR = subTreeLen - 1 - LenF;           //創建右子樹            PreInCreateTree(T->rchild,PreIndex + LenF + 1,index + 1,LenR);       }   }   /*      PostIndex: 後序序列字符串中子樹的最後一個節點在PreArray[]中的下標      InIndex:  中序序列字符串中子樹的第一個節點在InArray[]中的下標      subTreeLen: 子樹的字符串序列的長度      PostArray： 後序序列數組      InArray：中序序列數組  */   void PostInCreateTree(BiTree &T,int PostIndex,int InIndex,int subTreeLen){       //subTreeLen < 0 子樹為空        if(subTreeLen <= 0){           T = NULL;           return;       }       else{           T = (BiTree)malloc(sizeof(BiTNode));           //創建根節點            T->data = PostArray[PostIndex];           //找到該節點在中序序列中的位置            int index = strchr(InArray,PostArray[PostIndex]) - InArray;           //左子樹結點個數            int LenF = index - InIndex;           //創建左子樹            PostInCreateTree(T->lchild,PostIndex - (subTreeLen - 1 - LenF) - 1,InIndex,LenF);           //右子樹結點個數(總結點 - 根節點 - 左子樹結點)            int LenR = subTreeLen - 1 - LenF;           //創建右子樹            PostInCreateTree(T->rchild,PostIndex-1,index + 1,LenR);       }   }   //先序遍歷      void PreOrder(BiTree T){         if(T != NULL){             //訪問根節點              printf("%c ",T->data);           //訪問左子結點              PreOrder(T->lchild);             //訪問右子結點              PreOrder(T->rchild);          }     }     //後序遍歷      void PostOrder(BiTree T){         if(T != NULL){             //訪問左子結點              PostOrder(T->lchild);             //訪問右子結點              PostOrder(T->rchild);            //訪問根節點              printf("%c ",T->data);       }     }     int main()   {       BiTree T;       PreInCreateTree(T,0,0,strlen(InArray));       PostOrder(T);       printf("\n");       BiTree T2;       PostInCreateTree(T2,strlen(PostArray) - 1,0,strlen(InArray));       PreOrder(T2);       return 0;   }     #include<iostream> #include<string> using namespace std;   //二叉樹結點 typedef struct BiTNode{ //數據 char data; //左右孩子指針 struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;   //先序序列 char PreArray[101] = "ABCDEGF"; //中序序列 char InArray[101] = "CBEGDFA"; //後序序列 char PostArray[101] = "CGEFDBA"; /* PreIndex: 前序序列字符串中子樹的第一個節點在PreArray[]中的下標     InIndex:  中序序列字符串中子樹的第一個節點在InArray[]中的下標 subTreeLen: 子樹的字符串序列的長度 PreArray： 先序序列數組 InArray：中序序列數組 */ void PreInCreateTree(BiTree &T,int PreIndex,int InIndex,int subTreeLen){ //subTreeLen < 0 子樹為空 if(subTreeLen <= 0){ T = NULL; return; } else{ T = (BiTree)malloc(sizeof(BiTNode)); //創建根節點 T->data = PreArray[PreIndex]; //找到該節點在中序序列中的位置 int index = strchr(InArray,PreArray[PreIndex]) - InArray; //左子樹結點個數 int LenF = index - InIndex; //創建左子樹 PreInCreateTree(T->lchild,PreIndex + 1,InIndex,LenF); //右子樹結點個數(總結點 - 根節點 - 左子樹結點) int LenR = subTreeLen - 1 - LenF; //創建右子樹 PreInCreateTree(T->rchild,PreIndex + LenF + 1,index + 1,LenR); } } /* PostIndex: 後序序列字符串中子樹的最後一個節點在PreArray[]中的下標     InIndex:  中序序列字符串中子樹的第一個節點在InArray[]中的下標 subTreeLen: 子樹的字符串序列的長度 PostArray： 後序序列數組 InArray：中序序列數組 */ void PostInCreateTree(BiTree &T,int PostIndex,int InIndex,int subTreeLen){ //subTreeLen < 0 子樹為空 if(subTreeLen <= 0){ T = NULL; return; } else{ T = (BiTree)malloc(sizeof(BiTNode)); //創建根節點 T->data = PostArray[PostIndex]; //找到該節點在中序序列中的位置 int index = strchr(InArray,PostArray[PostIndex]) - InArray; //左子樹結點個數 int LenF = index - InIndex; //創建左子樹 PostInCreateTree(T->lchild,PostIndex - (subTreeLen - 1 - LenF) - 1,InIndex,LenF); //右子樹結點個數(總結點 - 根節點 - 左子樹結點) int LenR = subTreeLen - 1 - LenF; //創建右子樹 PostInCreateTree(T->rchild,PostIndex-1,index + 1,LenR); } } //先序遍歷   void PreOrder(BiTree T){       if(T != NULL){   //訪問根節點   printf("%c ",T->data);         //訪問左子結點           PreOrder(T->lchild);           //訪問右子結點           PreOrder(T->rchild);        }   }   //後序遍歷   void PostOrder(BiTree T){       if(T != NULL){           //訪問左子結點           PostOrder(T->lchild);           //訪問右子結點           PostOrder(T->rchild);  //訪問根節點   printf("%c ",T->data);     }   }   int main() { BiTree T; PreInCreateTree(T,0,0,strlen(InArray)); PostOrder(T); printf("\n"); BiTree T2; PostInCreateTree(T2,strlen(PostArray) - 1,0,strlen(InArray)); PreOrder(T2);     return 0; }