プログラミング 木構造 再帰
ネットに転がっていた、木構造のソースを読む。
#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]は全く使用されず、ポインタにはゴミが入ったまま。また、意味のあるオブジェクトを指していない。
こんな変な配列の使い方は初めてみた。
それと再帰の動きがかなりためになった。