二叉排序树

二叉排序树

Time Limit: 1000MS  Memory Limit: 65536KB Submit  Statistic  Discuss

Problem Description

二叉排序树的定义是：或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。 今天我们要判断两序列是否为同一二叉排序树

Input

开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。 接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉排序树。 接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉排序树。(数据保证不会有空树)

Output

 

Example Input

2 123456789 987654321 432156789 0

Example Output

NO NO

#include <iostream> #include <stdlib.h> #include <string.h> #include <stdio.h> using namespace std; struct tree {     int data;     tree *lchild,*rchild; }; tree *creat(tree *root,char e) {     if(root==NULL)     {         root = new tree;         root->lchild = root->rchild = NULL;         root->data = e;     }     else     {         if(e<root->data)         {             root->lchild = creat(root->lchild,e);         }         else         {             root->rchild = creat(root->rchild,e);         }     }     return root; } char God[123],God1[123]; int L; bool Judge(tree *r1,tree *r2) {     if(r1==NULL && r2==NULL)     {         return true;     }     else if(r1==NULL || r2==NULL)     {         return false;     }     if(r1->data!=r2->data)     {         return false;     }     if(Judge(r1->lchild,r2->lchild) && Judge(r1->rchild,r2->rchild))     {         return true;     }     return false; } int main() {     int n;     while(scanf("%d",&n),n!=0)     {         char str1[123],str2[123];         scanf("%s",str1);         int len = strlen(str1);         tree *root1 = NULL;         for(int i=0;i<len;i++)         {           root1 = creat(root1,str1[i]);         }         while(n--)         {             tree *root2 = NULL;             scanf("%s",str2);             int len2 = strlen(str2);             for(int i=0;i<len2;i++)             {                 root2 = creat(root2,str2[i]);             }         L=0;         if(Judge(root1,root2))         {             printf("YES\n");         }         else         {             printf("NO\n");         }         }     }     return 0; }

转载于:https://www.cnblogs.com/CCCrunner/p/6444576.html

相关资源：JAVA上百实例源码以及开源项目