数据结构第三次上机实验

堆排序

• 产生随机数并实现堆排序
• 统计平均比较次数

在艰苦卓绝地抄书以后，还是存在奇怪的现象……前三个顺序不对，所以投机取巧悄悄在前面手动排序……唉，太菜了我就不放代码了反正是错的。

二叉查找树

二叉查找树是一棵可为空的二叉树，若非空则其所有结点之关键词互异，且中根遍历形成按关键词递增序排列的结点序列。二叉查找树中的任一结点P，它的左子树中结点的关键词都小于P的关键词，而右子树中结点的关键词都大于P的关键词，并且结点P的左右子树也都是二叉查找树

这个我做出来了……

#include<iostream>
#include<Windows.h>
using namespace std;
class tree {
public:
	int data = 0;
	tree* right = NULL;
	tree * left = NULL;
	tree(int a) {
		data = a;
	}
};
tree* root = NULL;
bool inO(tree* t) {
	if (t == NULL) {
		return false;
	}
	else {
		inO(t->left);
		cout << " [" << t->data << "] ";
		inO(t->right);
	}
	return true;
}
tree* CF(tree* t, int num, int data) {
	if (t == NULL) {
		root = new(tree)(data);
		cout << "新数据\n";
		inO(root);
		cout << "\n";
		return root;
	}
	else if (t->data == data) {
		cout << "找到 " << num << "层\n";
		inO(root);
		cout << "\n";
		return t;
	}
	else if (t->data > data) {
		if (t->left == NULL) {
			t->left = new(tree)(data);
			cout << "新数据\n";
			inO(root);
			cout << "\n";
			return t->left;
		}
		return CF(t->left, num + 1, data);
	}
	else if (t->data < data) {
		if (t->right == NULL) {
			t->right = new(tree)(data);
			cout << "新数据\n";
			inO(root);
			cout << "\n";
			return t->right;
		}
		return CF(t->right, num + 1, data);
	}
}
int main() {
	int num = 0;
	while (num != -100) {
		cin >> num;
		CF(root, 0, num);
	}
}