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