BJFU_数据结构习题_288二叉排序树的判定

╰+哭是因爲堅強的太久メ 2023-05-30 06:21 9阅读 0赞

欢迎登录北京林业大学OJ系统  
[http://www.bjfuacm.com][http_www.bjfuacm.com]

### 288二叉排序树的判定 ###

**描述**  
假设二叉树每个结点的元素均为一个单字符，根据给定的字符序列按照先序遍历的顺序递归创建该树的二叉链表，然后判断该二叉树是否为二叉排序树。  
**输入**  
多组数据，每组数据有一行。每行为一个二叉树对应的前序序列（其中‘\#’表示空树）。当序列为“\#”时，输入结束。  
**输出**  
每组数据输出1行，若此二叉树为二叉排序树则输出“YES”，否则输出“NO”。  
**输入样例 1**  
ba\#\#c\#\#  
ca\#\#b\#\#

#  #

**输出样例 1**  
YES  
NO  
**思路：利用二叉树中序遍历数据递增的特点**

#include<iostream>
    using namespace std;
    int flag;
    char c[100];
    int k;
    typedef struct BiTNode
    {
        
    	char data;
    	struct BiTNode *lchild,*rchild;
    }BiTNode,*BiTree;
    void CreateBiTree(BiTree &T,char S[],int &i)
    {
        
    	if(S[i]=='#')
    		T=NULL;
    	else
    	{
        
    		T=new BiTNode;
    		T->data=S[i];
    		CreateBiTree(T->lchild,S,++i);
    		CreateBiTree(T->rchild,S,++i);
    	}
    }
    void InOrderTraverse(BiTree T)
    {
        
    	if(T)
    	{
        
    		InOrderTraverse(T->lchild);
    		c[++k]=T->data;
          	if(k>1&&c[k-1]>T->data)
            {
         	
              	flag=0;
            	return;
            }
    		InOrderTraverse(T->rchild);
    	}
    }
    int main()
    {
        
    	char S[100];
    	while(cin>>S&&S[0]!='#')
    	{
        
    		int i=-1;
    		flag=1;
    		k=0;
    	  	BiTree T;
    		CreateBiTree(T,S,++i);
    		InOrderTraverse(T);
    		if(flag)
    			cout<<"YES"<<endl;
    		else
    			cout<<"NO"<<endl;
    	}
    	return 0;
    }

[http_www.bjfuacm.com]: http://www.bjfuacm.com