（算法练习）——PAT A1043 Is it a Binary Search Tree

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了（算法练习）——PAT A1043 Is it a Binary Search Tree，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1926字，纯文字阅读大概需要3分钟。

内容图文

《算法笔记》P315
这一题主要是vector的&的用法（第一次见）
判断两个vector是否相等
镜像树的先序、后序遍历

#include <stdio.h>
#include <vector>
using namespace std;

vector<int> origin,pre,preM,post,postM;//保存初始数据、前序、镜像前序、后序、镜像后序 
struct node{
	int data;
	node* left;
	node* right;
};

//插入节点 
void insert(node* &root,int data){//插入用的是&root，一直如此 
	if(root == NULL){
		root = new node;
		root->data = data;
		root->left = root->right = NULL;
	}
	else if(root->data >data) insert(root->left,data);
	else insert(root->right,data);
}

//先序遍历
void preorder(node* root,vector<int>&vi){//用vector容器存储，每次都修改，所以用&vi，下同 
	if(root == NULL) return;
	vi.push_back(root->data);
	preorder(root->left,vi);
	preorder(root->right,vi);
} 

//镜像先序
void preorderMirror(node* root,vector<int>&vi){
	if(root == NULL) return;
	vi.push_back(root->data);
	preorderMirror(root->right,vi);
	preorderMirror(root->left,vi);
}
//后序遍历 
void postorder(node* root,vector<int>&vi){
	if(root == NULL) return;
	postorder(root->left,vi);
	postorder(root->right,vi);
	vi.push_back(root->data);
} 

//镜像后序遍历
void postorderMirror(node* root,vector<int>&vi){
	if(root == NULL) return;
	postorderMirror(root->left,vi);
	postorderMirror(root->right,vi);
	vi.push_back(root->data);
} 

int main(){
	int n,data;
	node* root = NULL;
	scanf("%d",&n);
	for(int i = 0;i <n;i++){
		scanf("%d",&data);
		origin.push_back(data);
		insert(root,data);
	}
	preorder(root,pre);
	preorderMirror(root,preM);
	postorder(root,post);
	postorderMirror(root,postM);
	if(origin == pre){                 //初始序列等于先序序列 
		printf("YES\n");
		for(int i = 0;i <post.size();i++){
			printf("%d",post[i]);
			if(i <post.size()-1) printf(" ");
		}
	}
	else if(origin == preM){          //初始序列等于镜像先序序列 
		printf("YES\n");
		for(int i = 0;i <postM.size();i++){
			printf("%d",postM[i]);
			if(i <postM.size() - 1) printf(" ");
		}
	}
	else{
		printf("NO\n");
	}
	return 0;	
}

• 点赞
• 收藏
• 分享
• • 文章举报

晴空_万里 发布了148 篇原创文章 · 获赞 4 · 访问量 4870 私信 关注

内容总结

以上是互联网集市为您收集整理的（算法练习）——PAT A1043 Is it a Binary Search Tree全部内容，希望文章能够帮你解决（算法练习）——PAT A1043 Is it a Binary Search Tree所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---