例题10.4二叉排序树（华科）

例题10.4二叉排序树（华科）

关键：二叉排序树的插入、前序、中序、后序遍历

#include<vector>
using namespace std;

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};

TreeNode* insert(TreeNode* root, int x) {
	if (root == NULL) {
		root = new TreeNode(x);
	}
	else if (x < root->val) {
		root->left = insert(root->left, x);
	}
	else if (x > root->val) {
		root->right = insert(root->right, x);
	}
	return root;
}

void preOrder(TreeNode* root) {
	if (root == nullptr)
		return;
	cout << root->val<<" ";
	if (root->left != nullptr) {
		preOrder(root->left);
	}
	if (root->right != nullptr) {
		preOrder(root->right);
	}
}

void InOrder(TreeNode* root) {
	if (root == nullptr)
		return;
	if (root->left != nullptr) {
		InOrder(root->left);
	}
	cout << root->val << " ";
	if (root->right != nullptr) {
		InOrder(root->right);
	}
}

void postOrder(TreeNode* root) {
	if (root == nullptr)
		return;
	if (root->left != nullptr) {
		postOrder(root->left);
	}
	if (root->right != nullptr) {
		postOrder(root->right);
	}
	cout << root->val << " ";
}

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);
		}
		preOrder(root);
		cout << endl;
		InOrder(root);
		cout << endl;
		postOrder(root);
		cout << endl;
	}
	return 0;
}