问题描述：
对输入的两个序列生成二叉排序树，判断他们是否是相同的二叉排序树。
输入：
2 要比较的次数 1-20之间
567432 主比较字符串，下面的2个字符串都和它进行比较 长度小于10
543267
576342
输出： YES
NO
问题分析：
要比较两棵二叉排序树是否相等，需要判断包含中序遍历的两种遍历方式是否相同才可以。
算法：
1.对输入的主比较序列生成二叉排序树T1;
2.对T1进行前、中遍历，结果存放在字符数组st1中
3.对每一个需要比较的字符串和1,2进行相同的操作生成字符数组st2.
4.比较str1，str2是否相同得出结果。
代码实现：
#include <iostream> #include<stdio.h> #include<string.h> /* run this program using the console pauser or add your own getch, system("pause") or input loop */ using namespace std; char str1[22]; //存放前序和后序的遍历结果 char str2[22]; //存放前序和后序的遍历结果 int size1, size2; //二叉树结构 struct Node { Node * lchild; Node * rchild; int c; }Tree[220]; int loc = 0; Node* create() { Node *T = &Tree[loc]; T->lchild = T->rchild = NULL; loc++; return T; } //插入函数(x插入二叉排序树T中) Node* Insert(Node *T, int x) { if (T == NULL) { T = create(); T->c = x; } else if (x<T->c) { T->lchild = Insert(T->lchild, x); } else { T->rchild = Insert(T->rchild, x); } return T; } //前序遍历 void preOrder(Node *T, char *str,int &size) { //访问根 //strcat(str,T->c+'0'); //str[strlen(str) - 1] = T->c + '0'; str[size++] = T->c+'0'; if (T->lchild != NULL) { preOrder(T->lchild, str,size); } if (T->rchild != NULL) { preOrder(T->rchild, str,size); } } void midOrder(Node *T, char *str,int &size) { if (T->lchild != NULL) { midOrder(T->lchild, str,size); } //访问根 //str[strlen(str) - 1] = T->c + '0'; str[size++] = T->c+'0'; if (T->rchild != NULL) { midOrder(T->rchild, str,size); } } int n; char str[11]; int main(int argc, char *argv[]) { //1.生成主比较字符串的前、中遍历结果 cout << "输入比较次数：" << endl; cin >> n; cout << endl; Node *T = NULL; cout << "输入主比较字符串：" << endl; cin >> str; cout << endl; for (int i = 0; i<strlen(str); i++) { T = Insert(T, str[i] - '0'); } size1 = 0; preOrder(T, str1,size1); midOrder(T, str1,size1); //cout << str1<<endl; //2. 输入n个比较字符串 while (n--) { //2.1 生成二叉排序树 Node *tmp=NULL; char str_tmp[11]; cout << "输入次比较字符串" << endl; cin >> str_tmp; for (int i = 0; i<strlen(str_tmp); i++) { tmp = Insert(tmp, str_tmp[i] - '0'); } //2.2生成前、中遍历结果 size2 = 0; preOrder(tmp, str2,size2); midOrder(tmp, str2,size2); //3.比较主比较字符串的前、中序列和比较字符串的前、中序列是否相同。 printf("主比较字符串遍历结果：%s ， 次比较字符串遍历结果：%s", str1, str2); if (strcmp(str1, str2) != 0) { cout <<endl<< "比较结果：NO" << endl; } else { cout << endl<< "比较结果：YES" << endl; } cout << endl; } getchar(); getchar(); getchar(); return 0; }
代码分析：
在对字符数组进行添加时候采用手动设置一个计数器。
