文章

20

粉丝

224

获赞

56

访问

137.3k

头像
建树后比较先序遍历结果是否相同
P1317 浙江大学机试题
发布于2022年2月8日 16:25
阅读数 5.6k

对每个序列建树,然后将n个序列对应的二叉搜索树的先序遍历结果和第一个序列对应的二叉搜索树的先序遍历结果进行比较,若相同,则输出YES,否则输出NO。

#include<iostream>
#include<vector>
using namespace std;

typedef struct node {
	char data;
	struct node *lchild, *rchild;
} *BitTree;

// reference 存储第一个序列对应的二叉搜索树的先序遍历结果,each 存储每颗二叉树的先序遍历结果 
vector<char> reference, each;

// 建立二叉搜索树
void InsertBitTree(BitTree &T, char x) {
	if (T == NULL) {
		T = new node;
		T->data = x;
		T->lchild = NULL;
		T->rchild = NULL;
		return;
	} else if (T->data > x) InsertBitTree(T->lchild, x);
	else InsertBitTree(T->rchild, x);
}

// 先序遍历二叉搜索树,并将遍历结果存进 each 数组中
void PreOrderTraverse(BitTree T) {
	if (T == NULL) return;
	each.push_back(T->data);
	PreOrderTraverse(T->lchild);
	PreOrderTraverse(T->rchild);
}

int main() {
	int n;
	string ref, seq;
	while (cin >> n) {
		if (n == 0) return 0;
		cin >> ref;
		// 得到第一个序列对应的二叉搜索树的先序遍历结果,即reference
		BitTree T = NULL;
		for (int ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发