1.	二叉树的深度及结点最远距离 【问题描述】考研真题：求二叉树的深度及二叉树中最远两个结点的距离。 【输入形式】拓展的前序遍历序列 【输出形式】深度和距离 【样例输入】AB#C##DE#G#H##F## 【样例输出】5 6

#include<iostream>
#include<string.h>
using namespace std;
#define elemtype char
elemtype a[101];struct node
{node *l;node *r;elemtype data;
};node*creat(elemtype a[],int len,int& i)
{if(a[i]!='#' && i<len){node *r=new node;r->data=a[i];r->l=creat(a,len,++i);r->r=creat(a,len,++i);return r;}elsereturn NULL;
}int getdeep(node *s,int cout,int& deep)
{if(s!=NULL){deep = max(deep,cout);getdeep(s->l,cout+1,deep);getdeep(s->r,cout+1,deep);return deep;}elsereturn 0;
}void getdistant(node *s,int& dis)
{if(s==NULL)return ;int i,j,deep=0;i=getdeep(s->l,1,deep);deep=0;j=getdeep(s->r,1,deep);if(i+j>dis) dis=i+j;if(s->l) getdistant(s->l,dis);if(s->r) getdistant(s->r,dis);
}int main()
{cin >> a;int len=strlen(a);node*s;	int deep=0,i=0,dis=1;s=creat(a,len,i);deep=getdeep(s,1,deep);getdistant(s,dis);cout << deep <<" " << dis;return 0 ;
}

2.	二叉树结点的共同祖先问题 【问题描述】假设二叉树采用二叉链表方式存储，root指向根结点，p所指结点和q所指结点为二叉树中的两个不同结点，且互不成为根到该结点的路径上的点，编程求解距离它们最近的共同祖先。 【输入形式】二叉树的前序和中序遍历序列，用以创建该二叉树的链式存储结构；以及二叉树的两个结点数据 x 和 y 【输出形式】结点数据值为 x 和结点数据值为 y 的最近的共同祖先，若没有共同祖先则输出NULL，请注意一个结点本身不能成为另一个结点的共同祖先。 【样例输入】 GABDCEF BDAEFCG DF 【样例输出】 A

#include<iostream>
#include<string.h>
using namespace std;
char pre[101],mid[101];struct node
{char data;node *l;node *r;
};//x:前序左，y:前序右，s:中序左，q:中序右 
node*build(int x,int y,int s,int q)
{if(x>y || s>q)return NULL;int i;node *a=new node;a->data=pre[x];for(i=s;i<=q;i++){if(pre[x]==mid[i])break;}a->l=build(x+1, x+i-s ,s , i-1);a->r=build(x+i-s+1 ,y ,i+1,q);return a;
}node*find(node *root,node *a1,node *b1)
{if(root==NULL)return NULL;if(root->data==a1->data || root->data==b1->data)return root;node *a2=find(root->l,a1,b1);node *b2=find(root->r,a1,b1);if(a2!=NULL && b2!=NULL)return root;if(a2!=NULL)return a2;if(b2!=NULL)return b2;elsereturn NULL;
}int main()
{cin >> pre >> mid ;int len=strlen(pre);node *root;root = build(0,len-1,0,len-1);char a,b;cin >> a >> b;node *a1=new node;node *b1=new node;node *s1=new node;a1->data=a;b1->data=b;s1 = find(root,a1,b1);if(s1!=NULL && s1->data!=root->data){cout << s1->data;}else cout << "NULL";return 0;
}

3.	中序线索二叉树 【问题描述】创建一棵二叉树，接着中序线索化该二叉树，然后编写相应函数遍历该中序线索二叉树 【编码要求】线索二叉树遍历过程中不能使用递归、不能使用栈。 【输入形式】二叉树拓展的前序遍历序列 【输出形式】中序遍历序列 【样例输入】AB#D##CE### 【样例输出】BDAEC

#include<iostream>
#include<string.h> 
using namespace std;
char a[101];struct node//定义结构类型 
{char data;node*l;node*r;int ltag,rtag;
};node*creat(char a[],int& len,int& i)//对传入的字符串进行处理 
{if(a[i]!='#' && i<len){node *r=new node;r->data=a[i];r->ltag=r->rtag=0;r->l=creat(a,len,++i);r->r=creat(a,len,++i);return r;}elsereturn NULL;
}node *pre=NULL;
void Inthread(node *root)//创建中序线索数 
{if(root!=NULL){Inthread(root->l);if(root->l==NULL){root->l=pre;root->ltag=1;}if(pre!=NULL && pre->r==NULL){pre->r=root;pre->rtag=1;}pre=root;Inthread(root->r);}
}void Inorder(node *root)//中序遍历二叉树 
{node *r;r=root;while(r!=NULL && r->ltag==0 &&r->l!=NULL)r=r->l;while(r!=NULL){cout << r->data;if(r->rtag==1)r=r->r;else{r=r->r;while(r!=NULL && r->ltag==0 &&r->l!=NULL)r=r->l;}}
}int main()
{cin >> a;int len=strlen(a);node*s;int i=0;s=creat(a,len,i);Inthread(s);Inorder(s);return 0;
}

4.	二叉树左右子树交换操作 【问题描述】二叉树按照二叉链表的方式存储。编写程序，计算二叉树中叶子结点的数目并输出；编写程序，将二叉树的每个结点的左、右子树进行交换，请注意不是只交换结点的data值，而是左、右孩子指针指向的交换，最后输出交换后的二叉树的后序遍历序列。 【输入形式】二叉树的前序遍历序列，空指针的位置输入字符# 【输出形式】叶子结点的数目；左右子树交换后，后序遍历的序列，空子树的位置输出字符# 【样例输入】 ABE##F##CG### 【样例输出】 3 ###GC##F##EBA

#include<iostream>
#include<string.h>
using namespace std;
char elem[101];struct node
{char data;node *l;node *r;
};node*creat(char elem[],int len,int& i)//处理字符串 
{if(i<len && elem[i]!='#'){node *r=new node;r->data=elem[i];r->l=creat(elem,len,++i);r->r=creat(elem,len,++i);return r;}elsereturn NULL;
}void exchange(node *root)//交换左右子树 
{node *r=new node;if(root!=NULL){r=root->l;root->l=root->r;root->r=r;exchange(root->l);exchange(root->r);}
}int count=0;
void yezi(node*root)
{if(root!=NULL){yezi(root->l);yezi(root->r);if(root->l==NULL && root->r==NULL)count++;}
}void Post_order(node *root)
{if(root!=NULL){Post_order(root->l);Post_order(root->r);cout << root->data;}elsecout << '#';
}int main()
{cin >> elem;int len = strlen(elem);int i,cout1=0;for(i=0;i<len-1;i++)//计算叶子结点的数量 {if(elem[i]=='#' && elem[i+1]=='#' &&elem[i+2]!='#')cout1++;}cout << cout1;cout << '\n' ;int j=0;node *root1;root1 = creat(elem,len,j);yezi(root1);cout << count << endl;exchange(root1);Post_order(root1);return 0;
}

5.	数组循环右移K位 【问题描述】将一个数组中的元素循环右移K位，要求只使用一个元素大小的附加存储空间，时间复杂度为O(n)。 【样例输入】 1 2 3 4 5 6 7 8 0 2 【样例输出】 7 8 1 2 3 4 5 6 【提示】0代表输入结束

#include<stdio.h>
#include<string.h>int main()
{int elem1[101],elem2[101];int i,j,k;for(i=0;i<101;i++){scanf("%d",&elem1[i]);if(elem1[i]==0)break;}int len=i;i=0;//for(int cou=0;cou<len;cou++)//{//	printf("%d ",elem1[cou]);//}//printf("%d",len);scanf("%d",&k);if( k>len )k=k%len;int a=len-k;for(j=0;j<k;j++){elem2[j]=elem1[a];a++;}for(j=k;j<len;j++){elem2[j]=elem1[i];i++;}for(int cou=0;cou<len;cou++){printf("%d ",elem2[cou]);}return 0;
}