根据先序中序遍历建树【模板】-白红宇

主要就是通过先序找到当前子树根节点，再用中序遍历分子树，不断递归下去。
#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #define INF 0x3f3f3f3fusing namespace std;template 
                    
                     Type stringToNum(const string& str){ istringstream iss(str); Type num; iss >> num; return num; }//======================================================typedef struct node{ int m_key; node * m_pLeft,*m_pRight;}BinaryTreeNode;//BinaryTreeNode* constructTree(int* preOrder,int preLen,int* sMidOrder, int midLen){ BinaryTreeNode* constructRoot(int* preOrder, int* midOrder, int len){ //先根遍历（前序遍历）的第一个值就是根节点的key int rootKey=preOrder[0]; BinaryTreeNode* root=new BinaryTreeNode; root->m_key=rootKey; root->m_pLeft=root->m_pRight=NULL; if(len==1 && *preOrder==*midOrder)//只有一个节点 return root; //在中根遍历（中序遍历）中找到根节点 int* rootMidOrder=midOrder; int leftLen=0; //左子树节点数 while(*rootMidOrder!=rootKey&&rootMidOrder<=(midOrder+len-1)){ ++rootMidOrder; ++leftLen; } if(*rootMidOrder!=rootKey)//在中根序列未找到根节点，输入错误 return NULL; if(leftLen>0){ //构建左子树 root->m_pLeft=constructRoot(preOrder+1,midOrder,leftLen); } if(len-leftLen-1>0){ //构建右子树 root->m_pRight=constructRoot(preOrder+leftLen+1,rootMidOrder+1,len-leftLen-1); } return root;}BinaryTreeNode* construct(int* preOrder,int* midOrder,int len){ if(preOrder==NULL||midOrder==NULL||len<=0) return NULL; return constructRoot(preOrder,midOrder,len);}//先根遍历void preOrderRecursionPrint(BinaryTreeNode* root){ if(root==NULL) return; cout<
                     
                      m_key<
                      
                       m_pLeft); preOrderRecursionPrint(root->m_pRight);}int main(){ //freopen("input.txt","r",stdin); //先根序列 int preOrder[8]={ 1,2,4,7,3,5,6,8}; //中根序列 int midOrder[8]={ 4,7,2,1,5,3,8,6}; BinaryTreeNode * treeRoot = construct(preOrder,midOrder,8); preOrderRecursionPrint(treeRoot); return 0;}
输出如下：
这里写图片描述