• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        


            


            The Fourth Dimension Space
            

            枯葉北風寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安； 不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！  -如夢令
            

            




            
	
					
	
            
		
            
			已知樹的前序遍歷和中序遍歷，求后序遍歷的方法（轉）
		
            
		
            /*    樹中已知先序和中序求后序。
                  如先序為：abdc,中序為：bdac .
                  則程序可以求出后序為：dbca 。此種題型也為數據結構常考題型。
                算法思想：先序遍歷樹的規則為中左右，則說明第一個元素必為樹的根節點，比如上例
            中的a就為根節點,由于中序遍歷為：左中右，再根據根節點a，我們就可以知道，左子樹包含
            元素為：db，右子樹包含元素：c，再把后序進行分解為db和c（根被消去了），然后遞歸的
            進行左子樹的求解（左子樹的中序為：db，后序為：db），遞歸的進行右子樹的求解（即右
            子樹的中序為：c，后序為：c）。如此遞歸到沒有左右子樹為止。
            關于“已知先序和后序求中序”的思考：該問題不可解，因為對于先序和后序不能唯一的確定
            中序，比如先序為 ab，后序為ba，我只能知道根節點為a，而并不能知道b是左子樹還是右子樹
            ，由此可見該問題不可解。當然也可以構造符合中序要求的所有序列。

            2004.12.5
            */
            #include             <stdio.h>
            int find(char c,char A[],int s,int e) /* 找出中序中根的位置。 */
            {
            int i;
            for(i=s;i<=e;i++)
                              if(A[i]==c) return i;
            }
            /* 其中pre[]表示先序序，pre_s為先序的起始位置，pre_e為先序的終止位置。 */
            /* 其中in[]表示中序，in_s為中序的起始位置，in_e為中序的終止位置。 */
            /* pronum()求出pre[pre_s～pre_e]、in[in_s～in_e]構成的后序序列。 */
            void pronum(char pre[],int pre_s,int pre_e,char in[],int in_s,int in_e)
            {
            char c;
            int k;
            if(in_s>in_e)    return ;                 /* 非法子樹，完成。 */
            if(in_s==in_e){printf("%c",in[in_s]); /* 子樹子僅為一個節點時直接輸出并完成。 */
                                          return ;
                              }
            c            =pre[pre_s];                           /* c儲存根節點。 */
            k            =find(c,in,in_s,in_e);                 /* 在中序中找出根節點的位置。 */
            pronum(pre,pre_s            +1,pre_s+k-in_s,in,in_s,k-1); /* 遞歸求解分割的左子樹。 */
            pronum(pre,pre_s            +k-in_s+1,pre_e,in,k+1,in_e); /* 遞歸求解分割的右子樹。 */
            printf(            "%c",c);                         /* 根節點輸出。 */
            }
            main()
            {
            char pre[]="abdc";
            char in[]="bdac";
            printf(            "The result:");
            pronum(pre,            0,strlen(in)-1,in,0,strlen(pre)-1);
            getch();
            }             

            //..

            已知二叉樹的先序和中序求后序－轉貼自CSDN 

            　二叉樹的根結點（根據三種遍歷）只可能在左右（子樹）之間，或這左子樹的左邊，或右子樹的右邊。 
            如果已知先序和中序（如果是中序和后序已知也可以，注意：如果是前序和后序的求中序是不可能實現的），先確定這棵二叉樹。 
            步驟：            1，初始化兩個數組，存放先序合中序。 
            2，對比先序和中序，在中序忠查找先序的第一個元素，則在中序遍歷中將這個元素的左右各元素分成兩部分。即的左邊的部分都在這個元素的左子樹中，右邊的部分都在右子樹中。 
            3，然后從從先序的第二個元素開始繼續上面的步驟。 

            如 先序：            1 2 3 4 5 6 7 8 9 10 11
            后序：            3 2 5 4 1 7 9 8 11 10 6 


            level             1: 1 
            2: 2 3 
            3: 3 4 7 
            4: 5 8 
            5: 9 10 
            6: 11 




            這個太簡單了，用個遞歸就可以，我到是有完整的代碼，如下： 
            // tree.cpp : Defines the entry point for the console application. 
            // 

            #include             "stdafx.h" 
            #include             "string.h" 

            typedef             struct node 
            { 
            char data; 
            struct node *lchild,*rchild; 
            }            BinNode; 
            typedef BinNode             *BinTree; 
            BinNode             *CreateNode(char c) 
            { 
            BinNode             *n1=new BinNode; 
            n1            ->data=c; 
            n1            ->lchild=NULL; 
            n1            ->rchild=NULL; 
            return n1; 
            }             
            int searchchar(char c,char *order) 
            { 
            for(int i=0;i<strlen(order);i++) 
            { 
            if(c==order[i]) 
            return i; 

            }             
            return -1; 
            }             

            BinNode            * CreateTree(char *pre,char *in) 
            { 
            char c=pre[0]; 
            char temppre[100]; 
            char tempin[100]; 
            char *p; 
            int i=0; 
            BinNode            * bnode; 
            if(pre=='\0') 
            return NULL; 

            memset(temppre,            0,100); 
            memset(tempin,            0,100); 

            bnode            =CreateNode(c); 
            i            =searchchar(pre[0],in); 
            if(i==-1) 
            return 0; 
            p            =in; 
            strncpy(tempin,p,i); 
            p            =pre; 
            strncpy(temppre,p            +1,i); 
            bnode            ->lchild=CreateTree(temppre,tempin);//left 

            memset(tempin,            0,100); 
            memset(temppre,            0,100); 

            p            =in+i+1; 
            strncpy(tempin,p,strlen(            in)-i); 
            p            =pre+i+1; 
            strncpy(temppre,p,strlen(            in)-i); 
            bnode            ->rchild=CreateTree(temppre,tempin); //right 
            return bnode; 
            }             

            void POSTORDER(BinNode *t) 
            { 
            if(t) /*二叉樹t非空*/ 
            { 
            POSTORDER(t            ->lchild); /*后序遍歷*t的左子樹*/ 
            POSTORDER(t            ->rchild); /*后序遍歷*t的右子樹*/ 
            printf(            "\t%c",t->data); /*訪問結點*/ 
            }             
            }             

            int main(int argc, char* argv[]) 
            { 
            char preorder[100]; 
            char inorder[100]; 

            BinNode            * Head; 

            do{ 
            printf(            "請輸入前序序列\n"); 
            scanf(            "%s",preorder); 
            printf(            "請輸入中序序序列\n"); 
            scanf(            "%s",inorder); 
            }            while(strlen(preorder)!=strlen(inorder)); 

            Head            =CreateTree(preorder,inorder); 
            printf(            "后序序列為:"); 
            POSTORDER(Head); 
            printf(            "\n"); 
            // printf("%ld",strlen(readin)); 
            return 0; 
            }             

            
本文轉自：http://hi.baidu.com/%B0%D9%BE%FD/blog/item/5fb6cca21e6f51afcbefd0fb.html

		
            
			posted on 2009-03-17 18:20 abilitytao 閱讀(7381) 評論(0)  編輯 收藏 引用  
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



久久久精品国产|
久久影院综合精品|
麻豆AV一区二区三区久久|
无码人妻久久一区二区三区蜜桃|
亚洲七七久久精品中文国产|
久久综合久久美利坚合众国|
亚洲色大成网站www久久九|
久久国产高清字幕中文|
午夜精品久久久久久久无码|
久久久久免费看成人影片|
99久久www免费人成精品|
精品久久亚洲中文无码|
久久97久久97精品免视看|
中文成人无码精品久久久不卡|
久久久久亚洲AV成人网人人网站|
久久久久亚洲AV片无码下载蜜桃
|
狠狠色噜噜狠狠狠狠狠色综合久久|
午夜不卡888久久|
狠狠综合久久综合88亚洲|
99久久精品免费观看国产|
亚洲日本va中文字幕久久|
国产精品日韩深夜福利久久|
99国产欧美精品久久久蜜芽|
色天使久久综合网天天|
久久成人影院精品777|
亚洲午夜久久久影院|
色天使久久综合网天天|
久久久国产精品福利免费|
久久免费美女视频|
色88久久久久高潮综合影院|
香蕉99久久国产综合精品宅男自
|
久久无码中文字幕东京热|
欧美久久精品一级c片片|
一本久道久久综合狠狠爱|
日韩va亚洲va欧美va久久|
国产99久久久国产精免费|
99久久www免费人成精品|
93精91精品国产综合久久香蕉|
日韩AV无码久久一区二区|
色综合久久综合中文综合网|
国产精品欧美久久久天天影视|