KY-233二叉排序树

描述

输入一系列整数，建立二叉排序树，并进行前序，中序，后序遍历。

输入描述：

输入第一行包括一个整数n(1<=n<=100)。 接下来的一行包括n个整数。

输出描述：

可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。 每种遍历结果输出一行。每行最后一个数据之后有一个空格。 输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。   -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 分两种方法： 1.使用"引用"——&

#include
#include
#include
#include
#include

using namespace std;

typedef struct TNode{
    int data;
    struct TNode *lchild,*rchild;
}TNode,*BiTree;

void Insert(BiTree &T,int n);
void PreTrav(BiTree T);
void MidTrav(BiTree T);
void PostTrav(BiTree T);

int main()
{
    int n,x;
    while (~scanf("%d",&n))
    {
        BiTree T = NULL;
        for (int i = 0; i < n; i++)
        {
            scanf("%d",&x);
            Insert(T,x);
        }
        PreTrav(T);
        printf("\n");
        MidTrav(T);
        printf("\n");
        PostTrav(T);
        printf("\n");
    }
    
}
//使用引用的话，直接对变量自身操作：可以直接：Insert(T->lchild,n)。
//不使用引用:T->lchild = Insert(T->lchild,n)。要对对应子树赋值，否则在函数内的形式变量操作是不会赋给T->lchild的。
void Insert(BiTree &T,int n)
{
    if (T == NULL)
    {
        T = (TNode*)malloc(sizeof(TNode));
        T->data = n;
        T->lchild = T->rchild = NULL;
    }
    else if (T->data > n)
    {
        Insert(T->lchild,n);
    }
    else if (T->data < n)
    {
        Insert(T->rchild,n);
    }
}
void PreTrav(BiTree T)
{
    if (T)
    {
        printf("%d ",T->data);
        PreTrav(T->lchild);
        PreTrav(T->rchild);
    }
}
void MidTrav(BiTree T)
{
    if (T)
    {
        MidTrav(T->lchild);
        printf("%d ",T->data);
        MidTrav(T->rchild);
    }
}
void PostTrav(BiTree T)
{
    if (T)
    {
        PostTrav(T->lchild);
        PostTrav(T->rchild);
        printf("%d ",T->data);
    }
}

2.不使用引用

//注意，当不使用引用—&时，在插入构造二叉树时，每一步都要给对应的子树赋值，否则无效
#include 
#include 
typedef struct BTNode{
	int data;
	BTNode * lchild;
	BTNode * rchild;
}BTNode;
/*	插入构造平衡二叉树	*/
BTNode * Insert(BTNode *T,int x){
	if(T==NULL){
		T=(BTNode*)malloc(sizeof(BTNode));
		T->data = x;
		T->lchild = T->rchild = NULL;
		return T;
	}else if(x < T->data){
		T->lchild = Insert(T->lchild,x);
	}else if(x > T->data){
		T->rchild = Insert(T->rchild,x);
	}
	return T;
}

/*	先序遍历	*/
void PreOrder(BTNode *T){
	if(T){
		printf("%d ",T->data);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
} 
/*	中序遍历	*/
void InOrder(BTNode *T){
	if(T){
		InOrder(T->lchild);
		printf("%d ",T->data);
		InOrder(T->rchild);
	}
}
/*	后序遍历	*/
void EndOrder(BTNode *T){
	if(T){
		EndOrder(T->lchild);
		EndOrder(T->rchild);
		printf("%d ",T->data);
	}
}

int main(){
	int n,x;
	while(scanf("%d",&n) != EOF){
		BTNode *T=NULL;
		for(int i=0;i