二叉搜索树的遍历

题目描述
给定一组无序整数，以第一个元素为根节点，按顺序插入结点生成一棵二叉搜索树，并对其进行中序遍历和先序遍历。

输入描述
输入包括多组数据，每组数据包含两行：第一行为整数m(1<=m<=3000)，表示该组数据中整数的数目，第二行给出m个整数，相邻整数间用一个空格间隔。最后一组数据后紧跟着包含0的一行输入，标识输入的结束。

输出描述
每组输入产生两行输出，第一行是中序遍历结果，第二行是先序遍历结果，每个整数后面带一个空格，每行中第一个整数前无空格。

输入样例
9
10 4 16 9 8 15 21 3 12
6
20 19 16 15 45 48 0

输出样例
3 4 8 9 10 12 15 16 21
10 4 3 9 8 16 15 12 21
15 16 19 20 45 48
20 19 16 15 45 48

Yizuodi的答案

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
 
typedef struct NODE{
    NODE* lchild;
    NODE* rchild;
    int val;
}node;
 
node* CreatSearchTree(int value[],int size){
    int flag=0;
    node* pt = (node*)malloc(sizeof(node));
    node* cur;
    node* temp;
    
    pt->lchild = pt->rchild = NULL;
    pt->val = value[0];
    
    flag = 0;
    
    for(int i = 1;i<size;i++){
        temp = pt;
        while(temp != NULL){
            if(value[i] < temp->val){
                cur = temp;
                flag = -1;
                temp = temp->lchild;
            } 
            else{
                cur = temp;
                flag = 1;
                temp = temp->rchild;
            }
            
            
        }
        
        if(flag == -1){
            cur->lchild = (node*)malloc(sizeof(node));
            cur->lchild->val = value[i];
            cur->lchild->lchild = cur->lchild->rchild = NULL;
        }
        
        else if(flag == 1){
            cur->rchild = (node*)malloc(sizeof(node));
            cur->rchild->val = value[i];
            cur->rchild->lchild = cur->rchild->lchild = NULL;
        }
    } 
    return pt;
} 
 
 
 
void preorder(node* pt){
    if(pt != NULL){
        cout<<pt->val<<' ';
        preorder(pt->lchild);
        preorder(pt->rchild);
    }
}
 
void inorder(node* pt){
    if(pt != NULL){
        inorder(pt->lchild);
        cout<<pt->val<<' ';
        inorder(pt->rchild);
    }
}
 
int a[3001];
 
int main(){
    int n;
    while(cin>>n && n){
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        node* pt=CreatSearchTree(a,n);
        inorder(pt);
        cout<<endl;
        preorder(pt);
        cout<<endl;
        
    }
    return 0;
}