题解 | #二叉排序树#

#include<iostream>
#include<cstdio>
#include<string>

using namespace std;

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

const int MAXN = 100 + 10;

int arr[MAXN];

void PreOrder(TreeNode* root) {
	if(root == nullptr) {
		return;
	}
	printf("%d ",root->data);
	PreOrder(root->leftChild);
	PreOrder(root->rightChild);
	return;
}
void InOrder(TreeNode* root) {
	if(root == nullptr) {
		return;
	}
	InOrder(root->leftChild);
	printf("%d ",root->data);
	InOrder(root->rightChild);
	return;
}
void PostOrder(TreeNode* root) {
	if(root == nullptr) {
		return;
	}
	PostOrder(root->leftChild);
	PostOrder(root->rightChild);
	printf("%d ",root->data);
	return;
}

TreeNode* Build(TreeNode* root,int x) {  //root为根节点，x为构建时需要的值
	if(root == nullptr) {
		root = new TreeNode(x);
	} else if(x < root->data) {  //
		root->leftChild = Build(root->leftChild,x);
	} else if(x > root->data) {
		root->rightChild = Build(root->rightChild,x);
	}
	return root;
}

int main() {
	int n;
	while(scanf("%d",&n) != EOF) {
		TreeNode* root = nullptr;
		while(n--) {
			int x;
			scanf("%d",&x);
			root = Build(root,x);
		}
		PreOrder(root);
		printf("\n");
		InOrder(root);
		printf("\n");
		PostOrder(root);
        printf("\n");
	}
	return 0;
}