输入包括1行字符串，长度不超过100。
可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。
abc##de#g##f###
c b e g d f a
1 #include<bits/stdc++.h> 2 using namespace std; 3 struct node{ 4 char data; 5 node *lchild,*rchild; 6 node(char c):data(c),lchild(NULL),rchild(NULL){} 7 }; 8 string s; 9 int loc; 10 node* create(){ 11 char c=s[loc++];//获取每一个字符串元素 12 if(c==‘#‘) return NULL; 13 node *t=new node(c);//创建新节点 14 t->lchild=create(); 15 t->rchild=create(); 16 return t; 17 } 18 void inorder(node *t){//递归中序 19 if(t){ 20 inorder(t->lchild); 21 cout<<t->data<<‘ ‘; 22 inorder(t->rchild); 23 } 24 } 25 int main(){ 26 while(cin>>s){ 27 loc=0; 28 node *t=create();//先序遍历建树 29 inorder(t);//中序遍历 并输出 30 cout<<endl; 31 } 32 return 0; 33 }
二叉树遍历2
两个字符串，其长度n均小于等于26。 第一行为前序遍历，第二行为中序遍历。 二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。
输入样例可能有多组，对于每组测试样例， 输出一行，为后序遍历的字符串。
ABC BAC FDXEAG XDEFAG
BCA XEDGAF
1 #include<bits/stdc++.h> 2 using namespace std; 3 struct node{ 4 char data; 5 node *lchild,*rchild; 6 node(char c):data(c),lchild(NULL),rchild(NULL){} 7 }; 8 node *create(string a,string b){//前序+中序--递归建树 9 if(a.size()==0) return NULL;//空字符串--递归出口 10 char c=a[0];//根节点 11 node *t=new node(c);//创建新节点 12 int 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)); 15 return t; 16 } 17 void postorder(node *t){ 18 if(t){//后序遍历 19 postorder(t->lchild); 20 postorder(t->rchild); 21 cout<<t->data; 22 } 23 } 24 int main(){ 25 string a,b; 26 while(cin>>a>>b){ 27 node *t=create(a,b); 28 postorder(t); 29 cout<<endl; 30 } 31 return 0; 32 }
二叉排序树1
输入包含多组测试数据，每组测试数据两行。 第一行，一个数字N（N<=100），表示待插入的节点数。 第二行，N个互不相同的正整数，表示要顺序插入节点的关键字值，这些值不超过10^8。
输出共N行，每次插入节点后，该节点对应的父亲节点的关键字值。
5 2 5 1 3 4
-1 2 2 5 3
1 #include<bits/stdc++.h> 2 using namespace std; 3 struct node{ 4 int data; 5 node *lchild,*rchild; 6 node(int x):data(x),lchild(NULL),rchild(NULL){} 7 }; 8 node *create(node *t,int x){ 9 if(t==NULL) 10 t=new node(x);//创建新节点 11 else if(x<t->data){ 12 if(t->lchild==NULL) cout<<t->data<<endl;//如果左子树为空，则直接插入值，并且当前节点就是父节点，输出。否则继续递归建树 13 t->lchild=create(t->lchild,x); 14 }else if(x>t->data){ 15 if(t->rchild==NULL) cout<<t->data<<endl; 16 t->rchild=create(t->rchild,x); 17 } 18 return t; 19 } 20 int main(){ 21 int n; 22 while(cin>>n){ 23 node *t=NULL; 24 for(int i=0;i<n;i++){ 25 int x; 26 cin>>x; 27 if(t==NULL) cout<<-1<<endl; 28 t=create(t,x); 29 } 30 } 31 return 0; 32 }
二叉排序树2
输入第一行包括一个整数n(1<=n<=100)。 接下来的一行包括n个整数。
可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。 每种遍历结果输出一行。每行最后一个数据之后有一个空格。 输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。
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> 2 using namespace std; 3 struct node{ 4 int data; 5 node *lchild,*rchild; 6 node(int x):data(x),lchild(NULL),rchild(NULL){} 7 }; 8 node *insert(node *t,int x){//中序建立二叉排序树~ 9 if(t==NULL) t=new node(x); 10 else if(x<t->data) t->lchild=insert(t->lchild,x); 11 else if(x>t->data) t->rchild=insert(t->rchild,x); 12 return t; 13 } 14 void preorder(node *t){ 15 if(t){ 16 cout<<t->data<<‘ ‘; 17 preorder(t->lchild); 18 preorder(t->rchild); 19 } 20 } 21 void inorder(node *t){ 22 if(t){ 23 inorder(t->lchild); 24 cout<<t->data<<‘ ‘; 25 inorder(t->rchild); 26 } 27 } 28 void postorder(node *t){ 29 if(t){ 30 postorder(t->lchild); 31 postorder(t->rchild); 32 cout<<t->data<<‘ ‘; 33 } 34 } 35 int main(){ 36 int n; 37 while(cin>>n){ 38 node *t=NULL; 39 for(int i=0;i<n;i++){ 40 int 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 } 48 return 0; 49 }
二叉排序树3
开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。 接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。 接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。
如果序列相同则输出YES，否则输出NO
2 567432 543267 576342 0
YES NO
1 #include<bits/stdc++.h> 2 using namespace std; 3 int loc; 4 struct node{ 5 char data; 6 node *lchild,*rchild; 7 node(char c):data(c),lchild(NULL),rchild(NULL){} 8 }; 9 node* insert(node *t,char x){ 10 if(t==NULL) 11 t=new node(x); 12 else if(x<t->data){ 13 t->lchild=insert(t->lchild,x); 14 } 15 else if(x>t->data){ 16 t->rchild=insert(t->rchild,x); 17 } 18 return t; 19 } 20 void preorder(node *t,char pre[]){ 21 if(t){ 22 pre[loc++]=t->data; 23 pre[loc]=0; 24 preorder(t->lchild,pre); 25 preorder(t->rchild,pre); 26 } 27 } 28 int main(){ 29 int n; 30 while(cin>>n){ 31 if(n==0) 32 break; 33 node *t1=NULL,*t2; 34 string s1,s2; 35 loc=0; 36 cin>>s1; 37 for(int i=0;i<s1.size();i++){ 38 t1=insert(t1,s1[i]); 39 } 40 for(int i=0;i<n;i++){ 41 t2=NULL; 42 cin>>s2; 43 for(int i=0;i<s1.size();i++){ 44 t2=insert(t2,s2[i]); 45 } 46 char a[24],b[24]; 47 preorder(t1,a); 48 loc=0; 49 preorder(t2,b); 50 loc=0; 51 string s=strcmp(a,b)==0?"YES":"NO"; 52 cout<<s<<endl; 53 } 54 } 55 return 0; 56 }
二叉树性质1
输入数据包括多行，每行给出一组测试数据，包括两个整数m，n (1 <= m <= n <= 1000000000)。
对于每一组测试数据，输出一行，该行包含一个整数，给出结点m所在子树中包括的结点的数目。
3 12 0 0
4
1 #include<bits/stdc++.h> 2 using namespace std; 3 int slv(int m,int n){ 4 if(m>n) return 0; 5 else return 1+slv(2*m,n)+slv(2*m+1,n);//递归。-实际上是完全二叉树 6 } 7 int main(){ 8 int m,n; 9 while(cin>>m>>n){ 10 cout<<slv(m,n)<<endl; 11 } 12 return 0; 13 }
原文：https://www.cnblogs.com/YanShaoDian/p/12688358.html