题解 | #二叉排序树#

比较经典的C写法

#include <cstdio>
#include <iostream>
#include <cstdlib>

using namespace std;

typedef struct treenode{
	int data;
	struct treenode* lchild;
	struct treenode* rchild;
}Treenode;

Treenode* Build(Treenode* T, int x){//充分理解形参 
	if(!T){
		T = (Treenode*)malloc(sizeof(Treenode));
		T->data = x;
		T->lchild = NULL;
		T->rchild = NULL;
		return T;
	}else{
		if(x < T->data){
			T->lchild = Build(T->lchild, x);
		}else if(x > T->data){
			T->rchild = Build(T->rchild, x);
		}
	}
	return T;
}

void Preorder(Treenode* T, int &tag){
	if(!T){
		return;
	}
	if(tag){
		printf(" ");
	}else{
		tag = 1;
	}
	printf("%d", T->data);
	Preorder(T->lchild, tag);
	Preorder(T->rchild, tag);
}

void Inorder(Treenode* T, int &tag){
	if(!T){
		return;
	}
	Inorder(T->lchild, tag);
	if(tag){
		printf(" ");
	}else{
		tag = 1;
	}
	printf("%d", T->data);
	Inorder(T->rchild, tag);
}

void Postorder(Treenode* T, int &tag){
	if(!T){
		return;
	}
	Postorder(T->lchild, tag);
	Postorder(T->rchild, tag);
	if(tag){//这件事情一定是在输出之前做 
		printf(" ");
	}else{
		tag = 1;
	}
	printf("%d", T->data);
}

int main(){
	int n;
	while(scanf("%d", &n) != EOF){
		int x;
		Treenode* T;
		T = NULL;
		for(int i=0; i<n; i++){
			scanf("%d", &x);
			T = Build(T, x);
		}
		int tag = 0;
		Preorder(T, tag);
		printf("\n"); tag = 0;
		Inorder(T, tag);
		printf("\n"); tag = 0;
		Postorder(T, tag);
		printf("\n");
	}
	return 0;
}