⼆叉树的⼏个经典例题
⼆叉树遍历1
题⽬描述
编⼀个程序，读⼊⽤户输⼊的⼀串先序遍历字符串，根据此字符串建⽴⼀个⼆叉树（以指针⽅式存储）。例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表⽰的是空格，空格字符代表空树。建⽴起此⼆叉树以后，再对⼆叉树进⾏中序遍历，输出遍历结果。
输⼊描述:
输⼊包括1⾏字符串，长度不超过100。
输出描述:
可能有多组测试数据，对于每组数据，
输出将输⼊字符串建⽴⼆叉树后中序遍历的序列，每个字符后⾯都有⼀个空格。
每个输出结果占⼀⾏。
输⼊
abc##de#g##f###
输出
c b e g
d f a
思路：递归建树。每次都获取输⼊字符串的当前元素，根据题⽬要求（先序、中序、后序等+其他限制条件）建树。再根据题⽬要求输出即可。
1 #include<bits/stdc++.h>
2using namespace std;
3struct node{
4char data;
5 node *lchild,*rchild;
6 node(char c):data(c),lchild(NULL),rchild(NULL){}
7 };
8string s;
9int loc;
10 node* create(){
11char c=s[loc++];//获取每⼀个字符串元素
12if(c=='#') return NULL;
13 node *t=new node(c);//创建新节点
14 t->lchild=create();
15 t->rchild=create();
16return t;
17 }
18void inorder(node *t){//递归中序
19if(t){
20 inorder(t->lchild);
21 cout<<t->data<<'';
22 inorder(t->rchild);
23 }
24 }
25int main(){
26while(cin>>s){
27 loc=0;
28 node *t=create();//先序遍历建树
29 inorder(t);//中序遍历并输出
30 cout<<endl;
31 }
32return0;
33 }
⼆叉树遍历2
题⽬描述
⼆叉树的前序、中序、后序遍历的定义：前序遍历：对任⼀⼦树，先访问跟，然后遍历其左⼦树，最后遍历其右⼦树；中序遍历：对任⼀⼦树，先遍历其左⼦树，然后访问根，最后遍历其右⼦树；后序遍历：对任⼀⼦树，先遍历其左⼦树，然后遍历其右⼦树，最后访问根。给定⼀棵⼆叉树的前序遍历和中序遍历，求其后序遍历（提⽰：给定前序遍历与中序遍历能够唯⼀确定后序遍历）。
输⼊描述:
两个字符串，其长度n均⼩于等于26。
第⼀⾏为前序遍历，第⼆⾏为中序遍历。
⼆叉树中的结点名称以⼤写字母表⽰：A，B，C....最多26个结点。
输出描述:
输⼊样例可能有多组，对于每组测试样例，
输出⼀⾏，为后序遍历的字符串。
⽰例1
输⼊
ABC
BAC
FDXEAG
XDEFAG
输出
BCA
XEDGAF
思路：由题⽬信息，先序+中序可递归建⽴⼆叉树（还是每次根据条件选取当前⼀个元素加⼊树，在递归遍历即可），再按照题⽬要求输出即可。
1 #include<bits/stdc++.h>
2using namespace std;
3struct node{
4char data;
5 node *lchild,*rchild;
6 node(char c):data(c),lchild(NULL),rchild(NULL){}
7 };
8 node *create(string a,string b){//前序+中序--递归建树
9if(a.size()==0) return NULL;//空字符串--递归出⼝
10char c=a[0];//根节点
11 node *t=new node(c);//创建新节点
12int pos=b.find(c);//到根节点在b中的位置
13 t->lchild=create(a.substr(1,pos),b.substr(0,pos));
14 t->rchild=create(a.substr(pos+1),b.substr(pos+1));
15return t;
16 }
17void postorder(node *t){
18if(t){//后序遍历
19 postorder(t->lchild);
20 postorder(t->rchild);
21 cout<<t->data;
22 }
23 }
24int main(){
25string a,b;
26while(cin>>a>>b){
27 node *t=create(a,b);
28 postorder(t);
29 cout<<endl;
30 }
31return0;
32 }
⼆叉排序树1
题⽬描述
⼆叉排序树，也称为⼆叉查树。可以是⼀颗空树，也可以是⼀颗具有如下特性的⾮空⼆叉树： 1. 若左⼦树⾮空，则左⼦树上所有节点关键字值均不⼤于根节点的关键字值； 2.若右⼦树⾮空，则右⼦树上所有节点关键字值均不⼩于根节点的关键字值； 3. 左、右⼦树本⾝也是⼀颗⼆叉排序树。现在给你N个关键字值各不相同的节点，要求你按顺序插⼊⼀个初始为空树的⼆叉排序树中，每次插⼊后成功后，求相应的⽗亲节点的关键字值，如果没有⽗亲节点，则输出-1。
输⼊描述:
输⼊包含多组测试数据，每组测试数据两⾏。
第⼀⾏，⼀个数字N（N<=100），表⽰待插⼊的节点数。
第⼆⾏，N个互不相同的正整数，表⽰要顺序插⼊节点的关键字值，这些值不超过10^8。
输出描述:
输出共N⾏，每次插⼊节点后，该节点对应的⽗亲节点的关键字值。
⽰例1
输⼊
5
2 5 1
3 4
输出
-
1
2
2
5
3
思路：⼆叉排序树基本思路是按照中序遍历得到递增序列的特点来建树。
1 #include<bits/stdc++.h>
2using namespace std;
3struct node{
4int data;
5 node *lchild,*rchild;
6 node(int x):data(x),lchild(NULL),rchild(NULL){}二叉树前序中序后序图解
7 };
8 node *create(node *t,int x){
9if(t==NULL)
10 t=new node(x);//创建新节点
11else if(x<t->data){
12if(t->lchild==NULL) cout<<t->data<<endl;//如果左⼦树为空，则直接插⼊值，并且当前节点就是⽗节点，输出。否则继续递归建树
13 t->lchild=create(t->lchild,x);
14 }else if(x>t->data){
15if(t->rchild==NULL) cout<<t->data<<endl;
16 t->rchild=create(t->rchild,x);
17 }
18return t;
19 }
20int main(){
21int n;
22while(cin>>n){
23 node *t=NULL;
24for(int i=0;i<n;i++){
25int x;
26 cin>>x;
27if(t==NULL) cout<<-1<<endl;
28 t=create(t,x);
29 }
30 }
31return0;
32 }
⼆叉排序树2
题⽬描述
输⼊⼀系列整数，建⽴⼆叉排序树，并进⾏前序，中序，后序遍历。
输⼊描述:
输⼊第⼀⾏包括⼀个整数n(1<=n<=100)。
接下来的⼀⾏包括n个整数。
输出描述:
可能有多组测试数据，对于每组数据，将题⽬所给数据建⽴⼀个⼆叉排序树，并对⼆叉排序树进⾏前序、中序和后序遍历。每种遍历结果输出⼀⾏。每⾏最后⼀个数据之后有⼀个空格。
输⼊中可能有重复元素，但是输出的⼆叉树遍历序列中重复元素不⽤输出。
⽰例1
输⼊
5
1 6 5 9 8
输出
1 6 5 9 8
1 5 6 8 9
5 8 9
6 1
思路：⼆叉排序树基本思路是按照中序遍历得到递增序列的特点来建树。
1 #include<bits/stdc++.h>
2using namespace std;
3struct node{
4int data;
5 node *lchild,*rchild;
6 node(int x):data(x),lchild(NULL),rchild(NULL){}
7 };
8 node *insert(node *t,int x){//中序建⽴⼆叉排序树~
9if(t==NULL) t=new node(x);
10else if(x<t->data) t->lchild=insert(t->lchild,x);
11else if(x>t->data) t->rchild=insert(t->rchild,x);
12return t;
13 }
14void preorder(node *t){
15if(t){
16 cout<<t->data<<'';
17 preorder(t->lchild);
18 preorder(t->rchild);
19 }
20 }
21void inorder(node *t){
22if(t){
23 inorder(t->lchild);
24 cout<<t->data<<'';
25 inorder(t->rchild);
26 }
27 }
28void postorder(node *t){
29if(t){
30 postorder(t->lchild);
31 postorder(t->rchild);
32 cout<<t->data<<'';
33 }
34 }
35int main(){
36int n;
37while(cin>>n){
38 node *t=NULL;
39for(int i=0;i<n;i++){
40int x;
41 cin>>x;
42 t=insert(t,x);
43 }
44 preorder(t); cout<<endl;
45 inorder(t); cout<<endl;
46 postorder(t); cout<<endl;
47 }
48return0;
49 }
⼆叉排序树3*****题⽬描述
判断两序列是否为同⼀⼆叉搜索树序列
输⼊描述:
开始⼀个数n，(1<=n<=20) 表⽰有n个需要判断，n= 0 的时候输⼊结束。
接下去⼀⾏是⼀个序列，序列长度⼩于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出⼀颗⼆叉搜索树。
接下去的n⾏有n个序列，每个序列格式跟第⼀个序列⼀样，请判断这两个序列是否能组成同⼀颗⼆叉搜索树。
输出描述:
如果序列相同则输出YES，否则输出NO
⽰例1
输⼊
2
567432
543267
576342
输出
NO
思路：先按照中序遍历得到递增序列的特点建⽴⼆叉树，然后再按照先序遍历输出，如果两个序列建⽴的⼆叉树先序遍历结果相同，那么说明为同⼀⼆叉搜索树（因为先序 1 #include<bits/stdc++.h>
2using namespace std;
3int loc;
4struct node{
5char data;
6 node *lchild,*rchild;
7 node(char c):data(c),lchild(NULL),rchild(NULL){}
8 };
9 node* insert(node *t,char x){
10if(t==NULL)
11 t=new node(x);
12else if(x<t->data){
13 t->lchild=insert(t->lchild,x);
14 }
15else if(x>t->data){
16 t->rchild=insert(t->rchild,x);
17 }
18return t;
19 }
20void preorder(node *t,char pre[]){
21if(t){
22 pre[loc++]=t->data;
23 pre[loc]=0;
24 preorder(t->lchild,pre);
25 preorder(t->rchild,pre);
26 }
27 }
28int main(){
29int n;
30while(cin>>n){
31if(n==0)
32break;
33 node *t1=NULL,*t2;
34string s1,s2;
35 loc=0;
36 cin>>s1;
37for(int i=0;i<s1.size();i++){
38 t1=insert(t1,s1[i]);
39 }
40for(int i=0;i<n;i++){
41 t2=NULL;
42 cin>>s2;
43for(int i=0;i<s1.size();i++){
44 t2=insert(t2,s2[i]);
45 }
46char a[24],b[24];
47 preorder(t1,a);
48 loc=0;
49 preorder(t2,b);
50 loc=0;
51string s=strcmp(a,b)==0?"YES":"NO";
52 cout<<s<<endl;
53 }
54 }
55return0;
56 }
⼆叉树性质1
题⽬描述
如上所⽰，由正整数1，2，3……组成了⼀颗特殊⼆叉树。我们已知这个⼆叉树的最后⼀个结点是n。现在的问题是，结点m所在的⼦树中⼀共包括多少个结点。⽐如，n =
12，m = 3那么上图中的结点13，14，15以及后⾯的结点都是不存在的，结点m所在⼦树中包括的结点有3，6，7，12，因此结点m的所在⼦树中共有4个结点。
输⼊描述:
输⼊数据包括多⾏，每⾏给出⼀组测试数据，包括两个整数m，n (1 <= m <= n <= 1000000000)。
输出描述:
对于每⼀组测试数据，输出⼀⾏，该⾏包含⼀个整数，给出结点m所在⼦树中包括的结点的数⽬。
⽰例1
输⼊
3 12
0 0
输出
4
思路：⼆叉树⽗⼦节点的关系。
1 #include<bits/stdc++.h>
2using namespace std;
3int slv(int m,int n){
4if(m>n) return0;
5else return1+slv(2*m,n)+slv(2*m+1,n);//递归。-实际上是完全⼆叉树
7int main(){
8int m,n;
9while(cin>>m>>n){
10 cout<<slv(m,n)<<endl;
11 }
12return0;
13 }
发表评论