4016-二叉排序树的判定（C++，附思路）_c++判别是否是二叉排序树

描述

假设二叉树每个结点的元素均为一个单字符，根据给定的字符序列按照先序遍历的顺序递归创建该树的二叉链表，然后判断该二叉树是否为二叉排序树。

输入

多组数据，每组数据有一行。每行为一个二叉树对应的前序序列（其中‘#’表示空树）。当序列为“#”时，输入结束。

输出

每组数据输出1行，若此二叉树为二叉排序树则输出“YES”，否则输出“NO”。

输入样例 1 

ba##c##
ca##b##
#

输出样例 1

YES
NO

思路：

这道题用到了二叉树的创建和遍历的思路，以及二叉排序树的定义，如果忘了记得先去复习！

设置一个全局变量flag用来存储该树是否是二叉排序树。

在遍历树的时候，如果该树有左右两个节点，那么比较两个节点里的data和当前根节点的data大小，只要有一个不符合大小关系就置flag=1并return，否则继续按先序遍历遍历该树的左右节点，只有其中一个叶子节点的情况同理。

最后看输出，只要flag==0就是YES，否则输出NO。

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<stack>
#include<set>
#include<map>
using namespace std;
 
int flag = 0;
typedef struct BNode
{
	char data;
	struct BNode* lchild, * rchild;
}*BTree, BNode;
void Create(BTree& bt, string s, int &i)
{
	if (s[i] == '#')
		bt = NULL;
	else
	{
		bt = new BNode;
		bt->data =s[i];
		Create(bt->lchild, s,++i);
		Create(bt->rchild, s,++i);
	}
}
void Traverse(BTree bt)
{
	if (bt)
	{
		if (bt->lchild && bt->rchild)
		{
			if (bt->lchild->data > bt->data || bt->rchild->data < bt->data)
			{
				flag = 1;
				return;
			}
			else
			{
				Traverse(bt->lchild);
				Traverse(bt->rchild);
			}
		}
		else if (bt->lchild && !bt->rchild)
		{
			if (bt->lchild->data > bt->data)
			{
				flag = 1;
				return;
			}
			else Traverse(bt->lchild);
		}
		else if (!bt->lchild && bt->rchild)
		{
			if (bt->rchild->data < bt->data)
			{
				flag = 1;
				return;
			}
			else Traverse(bt->rchild);
		}
	}
 
}
int main()
{
	string s;
	while (cin >> s && s != "#")
	{
		BTree bt;
		int i = -1;
		Create(bt, s, ++i);
		Traverse(bt);
		if (flag == 0)
			cout << "YES" << endl;
		else cout << "NO" << endl;
		flag = 0;
	}
	return 0;
}