计算机考研复试上机07

14、数据结构

1）二叉树

1.常用操作

struct TreeNode{
	int data;
	TreeNode *leftChild;
	TreeNode *rightChild;
}; 
//前序遍历
void PreOrder(TreeNode *root){
	if(root == NULL) return;
	visit(root->data);
	PreOrder(root->leftChild);
	PreOrder(root->rightChild);
	return;
} 
//层序遍历 
void levelOrder(TreeNode *root){
	queue<TreeNode*> myQueue;
	if(root != NULL) myQueue.push(root);
	while(!myQueue.empty()){
		TreeNode *current = myQueue.front();
		myQueue.pop();
		visit(current->data);
		if(current->leftChild != NULL)
			myQueue.push(current->leftChild);
		if(current->rightChild != NULL)
			myQueue.push(current->rightChild);
	}
}

2.二叉树遍历（清华大学复试上机题）

题目描述：

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一棵二叉树（以指针方式存储）。例如，先序遍历字符串 ABC##DE#G##F###，其中“#”表示空格，空格字符代表空树。建立这棵二叉树后，再对二叉树进行中序遍历，输出遍历结果。

#include <bits/stdc++.h>
using namespace std;

struct TreeNode{
	char data;
	TreeNode *leftChild;
	TreeNode *rightChild;
	TreeNode(char c): data(c), leftChild(NULL), rightChild(NULL){}
}; 

TreeNode *Build(int &position, string str){
	char c = str[position++];
	if(c == '#') return NULL;
	TreeNode *root = new TreeNode(c);
	root->leftChild = Build(position,str);
	root->rightChild = Build(position, str);
	return root;
}

void InOrder(TreeNode *root){
	if(root == NULL) return;
	InOrder(root->leftChild);
	cout<<root->data<<" ";
	InOrder(root->rightChild);
	return;
}

int main(){
	string str;
	while(cin>>str){
		int position = 0;
		TreeNode *root = Build(position, str);
		InOrder(root);
	}
	cout<<endl;
	return 0; 
}

2）二叉排序树

1.二叉排序树（华中科技大学复试上机题）

题目描述：

二叉排序树也称二叉查找树。它可以是一棵空树，也可以是一棵具有如下特性的非空二叉树：1. 若左子树非空，则左子树上所有结点的关键字值均不大于根结点的关键字值。2. 若右子树非空，则右子树上所有结点的关键字值均不小于根结点的关键字值。3. 左、右子树本身也是一棵二叉排序树。 现在给你 N 个关键字值各不相同的结点，要求你按顺序将它们插入一个初始为空树的二叉排序树，每次插入成功后，求相应父结点的关键字值，若没有父结点，则输出-1。

#include <bits/stdc++.h>
using namespace std;

struct TreeNode{
	int data;
	TreeNode *leftChild;
	TreeNode *rightChild;
	TreeNode(int x): data(x),leftChild(NULL),rightChild(NULL){}
};

TreeNode *insert(TreeNode *root,int x,int father){
	if(root == NULL){
		root = new TreeNode(x);
		cout<<father<<endl;
	}else if(x < root->data){
		root->leftChild = insert(root->leftChild,x,root->data);
	}else{
		root->rightChild = insert(root->rightChild,x,root->data);
	}
	return root;
}

int main(){
	int n;
	while(cin>>n){
		TreeNode *root = NULL;
		for(int i = 0;i < n;i++){
			int x;
			cin>>x;
			root = insert(root,x,-1);
		}
	}
	
	return 0; 
}

3）优先队列

1.常用操作

#include <bits/stdc++.h>
using namespace std;

int main(){
	priority_queue<int> queue;
	cout<<queue.size()<<endl;
	queue.push(20);
	queue.push(100);
	queue.push(30);
	queue.push(50);
	cout&