题解 | 二叉排序树

#include<iostream>
using namespace std;

struct node{
	int value;
	node* left;
	node* right;
};

//创建一棵树
void createTree(node* root,int value){
	if(root->value==value) return;	//相同的输入直接舍弃
	//根的值比较大，我们应该将其插入到右侧节点
	if(root->value<value){
		if(root->right==NULL){
			node* temp = new node;
			temp->value = value;
			root->right = temp;
		}else{
			createTree(root->right,value);
		}
	}else{
		if(root->left==NULL){
			node* temp = new node;
			temp->value = value;
			root->left = temp;
		}else{
			createTree(root->left,value);
		}
	}
}

//前序遍历一棵树
void formerTravel(node* root){
	if(root==NULL) return;
	cout<<root->value<<" ";
	formerTravel(root->left);
	formerTravel(root->right);
}

//中序遍历一棵树
void middleTravel(node* root){
	if(root==NULL) return;
	middleTravel(root->left);
	cout<<root->value<<" ";
	middleTravel(root->right);
}

//后序遍历一棵树
void afterTravel(node* root){
	if(root==NULL) return;
	afterTravel(root->left);
	afterTravel(root->right);
	cout<<root->value<<" ";
}

/*
 *二叉排序树
 * */
int main(){
	int n;
	while(cin>>n){
		node* root = new node;
		//初始化根节点
		cin>>root->value;
		//创建一颗树
		for(int i = 1;i<n;i++){
			int temp_value = 0;
			cin>>temp_value;
			createTree(root,temp_value);
		}
		//前序遍历一棵树
		formerTravel(root);
		cout<<endl;
		//中序遍历一棵树
		middleTravel(root);
		cout<<endl;
		//后序遍历一棵树
		afterTravel(root);
		cout<<endl;
	}
}