程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> SDUT 3343 數據結構實驗之二叉樹四:還原二叉樹,sdut3343

SDUT 3343 數據結構實驗之二叉樹四:還原二叉樹,sdut3343

編輯:C++入門知識

SDUT 3343 數據結構實驗之二叉樹四:還原二叉樹,sdut3343


數據結構實驗之二叉樹四:還原二叉樹

Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic

Problem Description

給定一棵二叉樹的先序遍歷序列和中序遍歷序列,要求計算該二叉樹的高度。

Input

輸入數據有多組,每組數據第一行輸入1個正整數N(1 <= N <= 50)為樹中結點總數,隨後2行先後給出先序和中序遍歷序列,均是長度為N的不包含重復英文字母(區分大小寫)的字符串。

 

Output

 輸出一個整數,即該二叉樹的高度。

Example Input

9 
ABDFGHIEC
FDHGIBEAC

Example Output

5

DQE:

本題為恢復二叉樹,給出先序序列及中序序列,在二叉樹的恢復問題中,已知先序和中序或者已知後序和中序即可恢復二叉樹,原理為先序和後序可以獲得根節點,從而分割中序序列得到左子樹及右子樹的中序序列,由此遞歸完成二叉樹的恢復,本題采用指針+引用遞歸恢復,需對指針有一定的理解再閱讀本代碼。

 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 struct Tree
 7 {
 8     char c;
 9     Tree *lt,*rt;
10 };
11 
12 Tree *creat(char *&xx,char *zx)
13 {
14     if(*zx=='\0')
15         return NULL;
16     char *x,*y;
17     Tree *r=new Tree;
18     int i=0;
19     while(zx[i]!='\0')
20     {
21         if(*xx==zx[i])
22         {
23             r->c=zx[i];
24             zx[i]='\0';
25             x=zx;
26             y=zx+i+1;
27             xx++;
28             r->lt=creat(xx,x);
29             r->rt=creat(xx,y);
30             break;
31         }
32         i++;
33     }
34     return r;
35 }
36 
37 int dev(Tree *r)
38 {
39     if(r==NULL)
40         return 0;
41     int l=dev(r->lt),rr=dev(r->rt);
42     int m=l>rr?l:rr;
43     return m+1;
44 }
45 
46 int main()
47 {
48     char xx[55],zx[55],*p;
49     Tree *root;
50     int n;
51     while(scanf("%d",&n)!=EOF)
52     {
53         scanf("%s%s",xx,zx);
54         p=xx;
55         root=creat(p,zx);
56         printf("%d\n",dev(root));
57     }
58     return 0;
59 }
60 
61 /***************************************************
62 User name: ***
63 Result: Accepted
64 Take time: 0ms
65 Take Memory: 160KB
66 Submit time: 2016-11-03 19:06:10
67 ****************************************************/

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved