题解 | #二叉搜索树#

//踩坑：1.递归Preorder写错了！
//2.idx的++，写成n++
#include <cstring>
#include <string>

using namespace std;
struct  Tree {				//树的数据结构  注意下面的指针
	char data;
	Tree* left;
	Tree* right;
};
void insertBST(char data, Tree*& root) {  //BST一开始是空的，根据data输入建立BST
		Tree* pnew = new Tree;				//set up  新结点
		pnew->data = data;					//		  新结点初始化   （3步：数值，空指针）
		pnew->left = NULL;
		pnew->right = NULL;

		if (root == NULL)
		{					//根是空的，根就是新来的  结点
			root = pnew;
		}
		else {
			Tree* pPre = root;				//造两个指针，father:   Pre 跟随者，    son:   Cur 探路者！
			Tree* pCur;
			while (true) {
				if (data < pPre->data) {	    //一级判断：新来的数，比根节点小
					pCur = pPre->left;
					if (pCur == NULL) {
						pPre->left = pnew;
						break;					//二级：当左子树是空，那么正好pnew插左子树
					}
					else {
						pPre = pCur;           //二级：当左子树不空：让pPre降级为pCur-----继续往左边走，继续循环
					}
				}
				if (data > pPre->data) {
					pCur = pPre->right;
					if (pCur == NULL) {
						pPre->right = pnew;
						break;
					}
					else pPre = pCur;
				}

			}
		}


	}
    string Inorder(Tree* root) {	//sequence of mid
		if (root == NULL) {
			return"";
		}
		else return Inorder(root->left) + root->data + Inorder(root->right);
	}

	string Preorder(Tree* root) {	//sequence of pre
		if (root == NULL) {
			return"";
		}
		else return  root->data + Preorder(root->left) + Preorder(root->right);
	}

	int main() {

		int n;
		while (scanf("%d", &n) != EOF) {
			if (n == 0) {
				break;
			}

			char str1[100];
			scanf("%s", str1);
			Tree* root1 = NULL;
			for (int i = 0; str1[i] != '\0'; i++) {	//str1

				insertBST(str1[i], root1);
			}

			string mid1 = Inorder(root1);
			string pre1 = Preorder(root1);

			char str2[100];
			for (int idx = 0; idx < n; idx++) {	 //处理字符串2 的大循环----字符串2可以有多个，而1只有一个
				scanf("%s", str2);
				Tree* root2 = NULL;

				for (int i = 0; str2[i] != '\0'; i++) {	//str2

					insertBST(str2[i], root2);
				}

				string mid2 = Inorder(root2);
				string pre2 = Preorder(root2);
				if (mid1 == mid2 && pre1 == pre2) {
					printf("YES\n");
                    
				}
				else printf("NO\n");

			}

		}

	}