[数据结构与算法]《算法笔记》读书记录DAY_36

CHAPTER_9? 提高篇(3)——数据结构(2)

9.4.3二叉查找树的性质

二叉查找树有一个重要性质：对二叉查找树进行中序遍历，遍历的结果是有序的。

另外，如果合理地调整二叉查找树的形态，使得每个子树上的节点尽量都有两个孩子，这样整个BST的高低就会尽可能低，即高度大概在log(N)级别，N是节点个数。能实现这个要求的是一颗平衡二叉树(AVL)，参考9.5节。

下面通过一道例题来练习二叉排序树相关。

题目：

给出N个正整数作为一颗二叉排序树的结点插入顺序，问：这串序列是否是该二叉排序树的先序序列或是该二叉排序树的镜像树的先序序列。

镜像树是指交换二叉树的所有结点的左右子树而形成的树。

如果是二叉排序树的先序序列或是该二叉排序树的镜像树的先序序列，则输出YES；否则，输出NO。

输入格式：

每个输入包含一个测试用例。对于每一个用例，第一行给出正整数N，N表示结点的个数。接下来在第二行分别给出N个节点的数据，每个数据间用空格分隔。

输出格式：

对于每一个用例，输出YES或者NO。

输入样例1：

7

8 6 5 7 10 8 11

输出样例1：

YES? ?//是先序序列

输入样例2：

7

8 10 11 8 6 7 5

输出样例2：

YES? ?//是镜像树的先序序列

?输入样例3：

7

8 6 8 5 10 9 11

输出样例3：

NO? ?//既不是先序序列，也不是镜像树的先序序列

思路：

通过给定的序列，构建出二叉排序树。对镜像树的先序遍历只需要在原树的先序遍历时交换左右子树的访问顺序即可。注意使用vector来存放初始序列、先序序列、镜像树的先序序列，这样可以直接进行比较。这是因为当vector内元素为基本数据类型时，可以直接用比较符号(==、>=、!=等)进行判断。

参考代码：

#include <iostream>
#include <vector>

using namespace std;
vector<int> origin,pre,preM;

struct node{
	int data;
	node *left,*right;
};

void insert(node* &root,int x) {
	if(root==NULL) {
		root=new node;
		root->data=x;
		root->left=root->right=NULL;
		return;
	}
	if(x<root->data)
		insert(root->left,x);
	else
		insert(root->right,x);
}

void preOrder(node* root) {
	if(root==NULL)
		return;
	pre.push_back(root->data);
	preOrder(root->left);
	preOrder(root->right);
}

void preOrderMirror(node* root) {
	if(root==NULL)
		return;
	preM.push_back(root->data);
	preOrderMirror(root->right);
	preOrderMirror(root->left);
}


int main() {
	int n,data;
	node *root=NULL;
	cin>>n;
	for(int i=0;i<n;i++) {
		cin>>data;
		origin.push_back(data);
		insert(root,data);
	}
	preOrder(root);
	preOrderMirror(root);
	if(origin==pre||origin==preM)
		cout<<"YES"<<endl;
	else
		cout<<"NO"<<endl;
	return 0;
}