fork download
copy 
  1. // 2bun-ki
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5.  
  6. #define height 6
  7. #define MAX (1<<height) 
  8.  
  9. int t[MAX+1]; //配列外アクセス防止のためのダミーで＋１
  10. int sz = 0;
  11.  
  12. void swap(int *x, int *y){
  13.     int tmp = *x;
  14.     *x = *y;
  15.     *y = tmp;
  16. }
  17.  
  18. void initTree(int n){
  19.     int i;
  20.     for(i=0;i<MAX;i++){
  21.         t[i] = -1;
  22.     }
  23. }
  24.  
  25. void printA(){
  26.     int i;
  27.     for(i=1;i<MAX;i++) printf("%d ",t[i]);
  28.     printf("\n");
  29. }
  30.  
  31. int goP(int i){
  32.     if(i/2 == 0) return 0;
  33.     else return i/2;
  34. }
  35.  
  36. int goL(int i){
  37.     if(2*i >= MAX) return 0;
  38.     else return 2*i;
  39. }
  40.  
  41. int goR(int i){
  42.     if(2*i+1 >= MAX) return 0;
  43.     else return 2*i+1;
  44. }
  45.  
  46. void insBT(int x){
  47.     int k,i = 1;
  48.     for(k=0;k<height;k++){
  49.         if(t[i]==-1){
  50.             t[i] = x;
  51.             sz++;
  52.             return;
  53.         }
  54.         if(x < t[i]) i = goL(i);
  55.         else i = goR(i);
  56.     }
  57.     printf("Error : too high -> %d\n",x);
  58. }
  59.  
  60. void printT(int i){
  61.     int x = i;
  62.     while(x/2!=0){
  63.         printf("  ");
  64.         x/=2;
  65.     }
  66.     printf("%d\n",t[i]);
  67. }
  68.  
  69. void preOrder(int i){
  70.     if(t[i] == -1) return;
  71.     printT(i);
  72.     preOrder(goL(i));
  73.     preOrder(goR(i));
  74. }
  75.  
  76. void inOrder(int i){
  77.     if(t[i] == -1) return;
  78.     inOrder(goL(i));
  79.     printT(i);
  80.     inOrder(goR(i));
  81. }
  82.  
  83. void postOrder(int i){
  84.     if(t[i] == -1) return;
  85.     postOrder(goL(i));
  86.     postOrder(goR(i));
  87.     printT(i);
  88. }
  89.  
  90. int main(void){
  91.     int i,x,n;
  92.     scanf("%d",&n);
  93.     initTree(n);
  94.     for(i=0;i<n;i++){
  95.         scanf("%d",&x);
  96.         insBT(x);
  97.     }
  98.     printf("== preOrder ====\n");
  99.     preOrder(1);
  100.     printf("\n");
  101.     printf("== inOrder ====\n");
  102.     inOrder(1);
  103.     printf("\n");
  104.     printf("== postOrder ====\n");
  105.     postOrder(1);
  106.     printf("\n");
  107.     printf("%d", MAX);
  108.     return 0;
  109. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
6
13 3 5 2 21 8
stdout
copy 
== preOrder ====
13
  3
    2
    5
      8
  21

== inOrder ====
    2
  3
    5
      8
13
  21

== postOrder ====
    2
      8
    5
  3
  21
13

64
https://ideone.com/02bIee
language:
C99 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!