题解 | #二叉搜索树#

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//思路：构造二叉排序原始树和后续树，之后调用equaltree函数判断是否相等
//注意：二叉排序时候，先在循环中建立好树，以及将字符数组转化为数字数组的方法，还有对数字数组初始化要么{0}，为全0，要么一个一个赋值
typedef struct Tnode {
  int data;
  struct Tnode* lchild;
  struct Tnode* rchild;
} Tnode;
Tnode* maketree(char* num) {
  Tnode* cur = (Tnode*)calloc(1, sizeof(Tnode));

  int tmp[20];//字符转化后的数字数组
  for (int i = 0; i < 20; i++) {
    tmp[i] = -1;
  }
  for (int i = 0; i < 20; i++) {
    if (num[i] == '\0') {
      break;
    }
    tmp[i] = num[i] - '0';
  }
  cur->data = tmp[0];
  Tnode* root = cur;
  int i = 1;
  while (tmp[i] != -1) {

    while (1) {
      if (tmp[i] > cur->data) {
        if (cur->rchild == NULL) {
          cur->rchild = (Tnode*)calloc(1, sizeof(Tnode));
          cur->rchild->data = tmp[i];
          break;
        }
        cur = cur->rchild;
      } else if (tmp[i] < cur->data) {
        if (cur->lchild == NULL) {
          cur->lchild = (Tnode*)calloc(1, sizeof(Tnode));
          cur->lchild->data = tmp[i];
          break;
        }
        cur = cur->lchild;
      }
    }
    i++;
    cur = root;
  }
  return root;

}
int flag = 1;//辅助判断树是否相等的全局变量
void equaltree(Tnode* ori, Tnode* now) //递归判断树是否相等
{
  if (now == NULL && ori == NULL) {
    return ;
  }
  if (ori->data != now->data) {
    flag = 0;
    return;

  }
  equaltree(ori->lchild, now->lchild);
  equaltree(ori->rchild, now->rchild);
  return ;
}
int main() {
  int n;
  while (scanf("%d\n", &n) != EOF) {
    char a[20];
    scanf("%s", &a);
    Tnode* origin = maketree(a);
    for (int i = 0; i < n; i++) {
      char b[20];
      scanf("%s", &b);
      Tnode* tmp = maketree(b);
      equaltree(origin, tmp);
      if (flag == 0) {
        printf("NO\n");
      } else {
        printf("YES\n");
      }
      flag = 1;
    }



  }
}