Problem Description

程序输入一个字符串（只包含小写字母），请按照字符的输入顺序建立平衡二叉排序树，并分别输出二叉树的先序序列、中序序列和后序序列，最后输出该二叉树向左旋转 90 度后的结构。

例如：向左旋转 90 度后，以每层向里缩进 4 个空格的方式输出，输出结果为：

        i
    g
        f
a
        d
    c
        b

测试输入

agxnzyimk

测试输出

Preorder: xigamknzy
Inorder: agikmnxyz
Postorder: agknmiyzx
Tree:
    z
        y
x
            n
        m
            k
    i
        g
            a

AcCode

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

#include <stdio.h>
#include<string.h>
struct Tnode{
    char value;
    int lchild,rchild;
}node[50];
int k=1,root = 1;
char stab[5] = "    ";

int calheight(int now,int deep){
    if(now==0)return deep - 1;
    
    int a = calheight(node[now].lchild,deep+1);
    int b = calheight(node[now].rchild,deep+1);
    
    return a>b?a:b;
}
int Max(int a,int b){
    return a>b?a:b;
}
//SingRotateLeft
void singRotateLeft(int now){
    
    Tnode temp,temp2;
    int subtemp;
    
    subtemp = node[now].lchild;
    temp = node[node[now].lchild];
    temp2 = node[now];
    
    temp2.lchild = temp.rchild;
    temp.rchild = subtemp;
    
    node[now]=temp;
    node[subtemp] = temp2;
    
    
}
//SingRotateRight
void singRotateRight(int now){
    
    Tnode temp,temp2;
    int subtemp;
    
    subtemp = node[now].rchild;
    temp = node[node[now].rchild];
    temp2 = node[now];
    
    temp2.rchild = temp.lchild;
    temp.lchild = subtemp;
    
    node[now]=temp;
    node[subtemp] = temp2;
    
}
//doubleRotateLR
void doubleRotateLR(int now)
{
    singRotateRight(node[now].lchild);
    singRotateLeft(now);
}
//doubleRotateRL
void doubleRotateRL(int now)
{
    singRotateLeft(node[now].rchild);
    singRotateRight(now);
}




void insert(char x,int parent,int now){
    
    if(now == 0){
        node[k].value=x;
        if(parent ==0){
            k++;
            return;
        }
        if(x < node[parent].value){
            node[parent].lchild = k++;
        }
        else {
            node[parent].rchild = k++;
        }
        return;
    }
    
    if(x>node[now].value){
        
        insert(x,now,node[now].rchild);
        
        
        if(calheight(node[now].lchild,0)-calheight(node[now].rchild,0) == 2||calheight(node[now].lchild,0)-calheight(node[now].rchild,0) == -2){
            if(x > node[node[now].rchild].value){
                singRotateRight(now);
            }
            else {
                //printf("doublelr\n");
                doubleRotateRL(now);
            }
        }
        
    }
    else {
        
        
        insert(x,now,node[now].lchild);
        
        if(calheight(node[now].lchild,0)-calheight(node[now].rchild,0) == 2||calheight(node[now].lchild,0)-calheight(node[now].rchild,0) == -2){
            if(x < node[node[now].lchild].value){
                singRotateLeft(now);
            }
            else {
                //printf("doublerl\n");
                doubleRotateLR(now);
            }
            
        }
    }
}

void Preorder(int now){
    
    if(node[now].value == '0')return;
    printf("%c",node[now].value);
    Preorder(node[now].lchild);
    Preorder(node[now].rchild);
}
void Inorder(int now){
    if(node[now].value=='0')return;
    
    Inorder(node[now].lchild);
    
    printf("%c",node[now].value);
    
    Inorder(node[now].rchild);
}
void Postorder(int now){
    if(node[now].value == '0')return;
    Postorder(node[now].lchild);
    Postorder(node[now].rchild);
    printf("%c",node[now].value);
}

void printTree(int deep,int now){
    if(node[now].value == '0')return;
    
    printTree(deep+1,node[now].rchild);
    
    for(int i=0;i<deep;i++)printf("%s",stab);
    
    printf("%c\n",node[now].value);
    
    printTree(deep+1,node[now].lchild);
    
}

int main() {
    
    char str[50];
    for(int i=0;i<50;i++){
        node[i].value='0';
        node[i].lchild=0;
        node[i].rchild=0;
    }
    
    scanf("%s",str);
    
    insert(str[0],0,0);
    
    for(int i=1;i<strlen(str);i++){
        insert(str[i],0,1);
    }
    //pre
    printf("Preorder: ");
    Preorder(root);
    printf("\n");
    //In
    printf("Inorder: ");
    Inorder(root);
    printf("\n");
    //Post
    printf("Postorder: ");
    Postorder(root);
    printf("\n");
    
    //Tree
    printf("Tree:\n");
    
    printTree(0,root);
    
    return 0;
}