【洛谷】P1305 新二叉树

题目链接

题目描述

输入一串二叉树，用遍历前序打出。

输入输出格式

输入格式：

第一行为二叉树的节点数n。(n≤26)

后面n行，每一个字母为节点，后两个字母分别为其左右儿子。

空节点用*表示

输出格式：

前序排列的二叉树

输入输出样例

输入样例1：

6
abc
bdi
cj*
d**
i**
j**

输出样例1：

abdicj

看题解是根结点在第一行。如果不在第一行是会有一点点麻烦。

根结点在第一行的AC代码：

 1 ////CSDN博客：https://blog.csdn.net/qq_40889820
 2 #include<iostream>
 3 #include<sstream>
 4 #include<algorithm>
 5 #include<string>
 6 #include<cstring>
 7 #include<iomanip>
 8 #include<vector>
 9 #include<cmath>
10 #include<ctime>
11 #include<stack>
12 #include<queue>
13 #include<map>
14 #define mem(a,b) memset(a,b,sizeof(a))
15 #define e 2.71828182
16 #define Pi 3.141592654
17 using namespace std;
18 struct node
19 {
20         char ele;
21     node* lc;
22     node* rc;    
23     node(char c)
24     {
25         ele=c;lc=rc=NULL;
26     }
27 }; 
28 node* root=NULL;
29 node* Find(char ch,node* n)
30 {
31     if(n==NULL) return NULL;
32     if(n->ele==ch) return n;
33     node* ans=Find(ch,n->lc);//先找左子树 
34     if(ans) return ans;//找到了就返回 
35     else return Find(ch,n->rc); //左子树没找到在右子树找 
36     
37 }
38 void add_2node(string str)
39 {
40     char c=str[0],l=str[1],r=str[2];
41     node* pos=Find(c,root);
42     node* lchild=new node(l);
43     node* rchild=new node(r);
44     pos->lc=lchild;
45     pos->rc=rchild;
46     return;
47 }
48 void preorder(node* n)
49 {
50     if(n->ele=='*'||n==NULL) return;
51     cout<<n->ele;
52     preorder(n->lc);
53     preorder(n->rc);
54 }
55 int main()
56 {
57     int n;
58     cin>>n;
59     for(int i=1;i<=n;i++)
60     {
61         string str;
62         cin>>str;
63         if(i==1) root=new node(str[0]);//题目中根结点在第一行 
64         add_2node(str);
65     }
66     preorder(root);
67 }

View Code

根结点不在第一行（不知道A没AC代码）：

 1 ////CSDN博客：https://blog.csdn.net/qq_40889820
 2 #include<iostream>
 3 #include<sstream>
 4 #include<algorithm>
 5 #include<string>
 6 #include<cstring>
 7 #include<iomanip>
 8 #include<vector>
 9 #include<cmath>
10 #include<ctime>
11 #include<stack>
12 #include<queue>
13 #include<map>
14 #define mem(a,b) memset(a,b,sizeof(a))
15 #define e 2.71828182
16 #define Pi 3.141592654
17 using namespace std;
18 struct node
19 {
20         char ele;
21     node* lc;
22     node* rc;    
23     node(char c)
24     {
25         ele=c;lc=rc=NULL;
26     }
27 }; 
28 node* root=NULL;
29 node* Find(char ch,node* n)
30 {
31     if(n==NULL) return NULL;
32     if(n->ele==ch) return n;
33     node* ans=Find(ch,n->lc);//先找左子树 
34     if(ans) return ans;//找到了就返回 
35     else return Find(ch,n->rc); //左子树没找到在右子树找 
36     
37 }
38 void add_2node(string str)
39 {
40     char c=str[0],l=str[1],r=str[2];
41     node* pos=Find(c,root);
42     if(pos!=NULL)
43     {
44         pos->lc=new node(l);
45         pos->rc=new node(r);
46     } 
47     //原先的根结点是新读入结点的左子结点 
48     else if((pos=Find(l,root))!=NULL)
49     {
50         node* ne=new node(c);
51         ne->lc=root;
52         ne->rc=new node(r);
53         root=ne;
54     } 
55     //原先的根结点是新读入结点的右子结点 
56     else 
57     {
58         node* ne=new node(c);
59         ne->rc=root;
60         ne->lc=new node(l);
61         root=ne;
62     }
63     return;
64 }
65 void preorder(node* n)
66 {
67     if(n->ele=='*'||n==NULL) return;
68     cout<<n->ele;
69     preorder(n->lc);
70     preorder(n->rc);
71 }
72 int main()
73 {
74     int n;
75     cin>>n;
76     for(int i=1;i<=n;i++)
77     {
78         string str;
79         cin>>str;
80         if(i==1) root=new node(str[0]);//先假定在第一行 
81         add_2node(str);
82     }
83     preorder(root);
84 }

View Code