プログラミング 木構造 再帰

ネットに転がっていた、木構造のソースを読む。

#include <stdio.h>
#include <stdlib.h>

#define N (15)


struct node
{ 	int data;
	struct node* left;   
	struct node* right;  
};

int init_data[N+1] = {0,4,7,9,13,8,10,22,6,0,0,15,2,29,0,0};

void preorder(struct node* p);                    
void inorder(struct node* p);                    
void arrtorder(struct node* p);                   
void print_tree(int depth, struct node* p);

int main(void)
{
	int i, n_left, n_right;
	struct node *root, *arr[N+1];

	root = arr[1] = malloc( sizeof(struct node) ); 
	arr[1]->data = init_data[1];
	arr[1]->left = arr[1]->right = NULL;

	for(i=1; i<N/2; ++i) {
		n_left = i * 2; 
		n_right = n_left + 1; 

		if( init_data[n_left] != 0 ) {
		       	arr[n_left] = arr[i]->left = malloc( sizeof(struct node) ); 
			arr[n_left]->data = init_data[n_left]; 
			arr[n_left]->left = arr[n_left]->right = NULL; 
		} else {
		       	arr[n_left] = NULL; 
		} 
		
		if( init_data[n_right] != 0 ) {
		       	arr[n_right] = arr[i]->right = malloc( sizeof(struct node) ); 
			arr[n_right]->data = init_data[n_right]; 
			arr[n_right]->left = arr[n_right]->right = NULL; 
		} else {
		       	arr[n_right] = NULL; 
		} 
	} 
	
	print_tree(0,root);
	printf("\npreorder");
       	preorder( root );
       	printf("\ninorder");
       	inorder( root );
       	printf( "\narrtorder" );
       	arrtorder( root );
       	printf( "\n" );
}
void preorder(struct node* p) 
{
       	if( p == NULL ){ return; }
       	printf( "%2d ", p->data );
       	preorder( p->left );
       	preorder( p->right );
}
void inorder(struct node* p)
{
       	if( p == NULL ){ return; }
       	inorder( p->left );
       	printf( "%2d ", p->data );
       	inorder( p->right );
}
void arrtorder(struct node* p)
{
	if( p == NULL ){ return; }
       	arrtorder( p->left );
       	arrtorder( p->right );
       	printf( "%2d ", p->data );
}
void print_tree(int depth, struct node* p)
{
	int i = 0;
	if(p == NULL){ return; }
	for(i = 0;i < depth; i++){
		printf(" ");
	}
	printf("%d\n",p->data);
	print_tree(depth+1, p->left);
	print_tree(depth+1, p->right);
}

$./a.out

4
 7
  13
   6
  8
   15
 9
  10
   2
   29
  22

preorder 4  7 13  6  8 15  9 10  2 29 22 
inorder 6 13  7  8 15  4  2 10 29  9 22 
arrtorder 6 13 15  8  7  2 29 10 22  9  4 

木構造+ヒープのなれの果て?
なのか...
ヒープだと、データの挿入に制限があるけれど、コレはタダコピーするだけ。
再帰を使って木構造をそのまま出力する方法を考えたけれど、今の自分の力では無理っぽいので、お茶を濁す。
ちなみにこんなの↓

　　　　　　　　    4
　　　　7　　　　　　　　      9
　　13　　　8　　　　     10　　　   22
　6    x　x　　15　     2　　　29  x     x
x    x       x    x   x   x  x    x

あと、
arr[0]は全く使用されず、ポインタにはゴミが入ったまま。また、意味のあるオブジェクトを指していない。
こんな変な配列の使い方は初めてみた。
それと再帰の動きがかなりためになった。