Problem Description

建立并中序遍历一个排序二叉树

排序二叉树是指左子树的所有节点的值均小于它根节点的值,右子树的所有节点的值均大于它根节点的值,如下图是一棵排序二叉树

输入：

输入有一行，表示若干个要排序的数，输入0时停止

输出

二叉树的凹入表示
和二叉树的中序遍历序列

测试输入

42 168 35 101 270 125 79 259 263 165 6 246 182 62 192 296 243 28 37 0 

测试输出

        6
            28
    35
        37
42
                62
            79
        101
            125
                165
    168
                    182
                        192
                            243
                246
            259
                263
        270
            296

 6 28 35 37 42 62 79 101 125 165 168 182 192 243 246 259 263 270 296

AcCode

//
//  main.cpp
//  排序二叉树
//
//  Created by jetviper on 2017/3/26.
//  Copyright © 2017年 jetviper. All rights reserved.
//

#include <stdio.h>
struct{
    int value,parent,lchild,rchild,vsd;
}node[1000];
int k=2,tp=0,list[1000];
char stab[5] = "    ";

void insert(int x,int now){
    if(node[now].value==0){
        node[now].value=x;
        return;
    }
    
    if(x>node[now].value){
        
        if(node[now].rchild==0){
            node[now].rchild = k;
            node[k].value = x;
            node[k].parent = now;
            k++;
        }
        else {
            insert(x,node[now].rchild);
        }
        
    }
    else {
        
        if(node[now].lchild==0){
            node[now].lchild = k;
            node[k].value = x;
            
            node[k].parent = now;
            k++;
        }
        else {
            insert(x,node[now].lchild);
        }
    }
}
void mtbt(int deep,int now){
    if(node[now].value==0)return;
    
    
    if(node[now].lchild!=0&&node[node[now].lchild].vsd == 0) {
        mtbt(deep + 1, node[now].lchild);
    }
    else {
        if(node[now].vsd==0){
            node[now].vsd =1;
            for(int i=0;i<deep;i++)printf("%s",stab);
            printf("%d\n",node[now].value,now);
            list[tp++]=node[now].value;
        }
        
        if(node[now].rchild!=0&&node[node[now].rchild].vsd==0){
            mtbt(deep+1,node[now].rchild);
        }
        else {
            mtbt(deep-1,node[now].parent);
        }
    }
    
    
    
}

int main() {
    int x;
    for(int i=0;i<1000;i++){
        node[i].value=0;
        node[i].lchild=0;
        node[i].rchild=0;
        node[i].parent=0;
        node[i].vsd=0;
    }
    while(1){
        scanf("%d",&x);
        if(x==0)break;
        insert(x,1);
    }
    
    mtbt(0,1);
    printf("\n");
    for(int i=0;i<tp;i++){
        printf(" %d",list[i]);
    }
    printf("\n");
    return 0;
}