描述

二叉查找树(Binary Search Tree)，(又:二叉搜索树，二叉排序树)它或者是一棵空树，或者是具有下列性质的二叉树: 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。

输入

请输入一串不同的正整数，以-1结束，该序列表示插入顺序
例如

90 77 100 99 98 80 60 76 -1

图示

输出

这棵树的先序中序和后序

c++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <stdio.h>
#include <stack>
using namespace std;
#define md 1000000007;
struct  tree
{
    tree * lson;
    tree * rson;
    int value;
};
tree * head;
void build( tree * tmp,int cc){
    if(tmp->value>cc){
        if(tmp->lson!=NULL)build(tmp->lson,cc);
        else{
            tree * tt=NULL;
            tt=(tree * )malloc(sizeof(tree));tt->lson=NULL;tt->rson=NULL;
            tt->value=cc;
            tmp->lson=tt;
        }
    }
    else if(tmp->value<cc){
        if(tmp->rson!=NULL)build(tmp->rson,cc);
        else{
            tree * tt=NULL;
            tt=(tree * )malloc(sizeof(tree));tt->lson=NULL;tt->rson=NULL;
            tt->value=cc;
            tmp->rson=tt;
        }
    }
}
void preorder(tree * tt){
    cout<<tt->value<<" ";
    if(tt->lson!=NULL)preorder(tt->lson);
    if(tt->rson!=NULL)preorder(tt->rson);
}
void midorder(tree * tt){
    if(tt->lson!=NULL)midorder(tt->lson);
    cout<<tt->value<<" ";
    if(tt->rson!=NULL)midorder(tt->rson);
}
void aftorder(tree * tt){
    if(tt->lson!=NULL)aftorder(tt->lson);
    if(tt->rson!=NULL)aftorder(tt->rson);
    cout<<tt->value<<" ";
}
int main()
{
    cout<<"请输入一串不同的正整数，以-1结束，该序列表示插入顺序"<<endl;
    int n;cin>>n;
    if(n>0){
        head=(tree * )malloc(sizeof(tree));
        head->value=n;head->lson=NULL;head->rson=NULL;cin>>n;
    }
    else{
        cout<<"no notes"<<endl;
        return 0;
    }
    while(n>=0){
        build(head,n);
        cin>>n;
    }
    cout<<"pre:"<<endl;
    preorder(head);puts("");
    cout<<"mid:"<<endl;
    midorder(head);puts("");
    cout<<"aft:"<<endl;
    aftorder(head);puts("");
    return 0;
}