[問題] 配列によるキューを用いて、二分木を幅優先(breath first)で出力するプログラムを作れ。
(すでにリストによるキューを使った同様の問題をやっており、
それを配列によるキューで作り直す問題です)
[ソース]
#include <stdio.h> #include <stdlib.h> #define MaxSize 100 typedef struct node *NodeP; typedef struct node { int data; /* 処理対象のデータ */ NodeP llink, rlink; /* 左・右部分木 */ } Node; /****** 配列によるキューの実現(ここから) *****/ /* キューを配列で実現するためのデータ型 Queue の定義 */ typedef struct queue { NodeP array[MaxSize]; int size; /* 格納済データ領域の次の要素番号 */ } Queue; /* Queue のポインタ型 QueueP の定義 */ typedef Queue *QueueP; /* キューへのポインタを格納する変数の宣言 */ static QueueP queue; /******* ここからが、間違ってるかもしれないところ ********/ void initQueue(void) /* キューの初期化 */ { queue = (QueueP)malloc(sizeof(Queue)); if(queue == NULL) { fprintf(stderr,"Can't allocate memory!\n"); exit(1); } queue->size = 0; } int isEmpty(void) /* キューが空なら1、空でなければ0を返す */ { return ((queue->size) != 0) ? 0 : 1; } void enqueue(NodeP nd) /* キューに節点を追加 */ { if (queue->size < MaxSize) { queue->array[queue->size] = nd; queue->size++; } } NodeP dequeue(void) /* キューから節点を取り出す */ { NodeP nd; if (queue->size > 0 ) queue->size--; nd = queue->array[queue->size]; return nd; } } /*** 以上が間違っているかもしれないところ ****/ /**** 配列によるキューの実現(ここまで) ****/ void breathFirst(NodeP root) /* root を根とする二分木を幅優先訪問する */ { NodeP p; initQueue(); enqueue(root); while(!isEmpty()) { p = dequeue(); printf(" %d,", p->data); if(p->llink != NULL) enqueue(p->llink); /* 左部分木が存在するならキューに左部分木の節点を追加 */ if(p->rlink != NULL) enqueue(p->rlink); /* 右部分木が存在するならキューに右部分木の節点を追加 */ } } NodeP newNode(int val) /* 値 val をもつ節点を生成する補助関数 */ { NodeP newp = (NodeP)malloc(sizeof(Node)); if(newp == NULL) { fprintf(stderr, "Can't allocate memory!\n"); exit(1); } newp->data = val; newp->llink = NULL; newp->rlink = NULL; return newp; } NodeP createTree(void) /* 以下の二分木を作る * 1 * 2 3 * 4 5 6 7 * 8 9 10 * 11 */ { NodeP root; root = newNode(1); root->llink = newNode(2); root->rlink = newNode(3); root->llink->llink = newNode(4); root->llink->rlink = newNode(5); root->rlink->llink = newNode(6); root->rlink->rlink = newNode(7); root->rlink->llink->llink = newNode(8); root->rlink->llink->rlink = newNode(9); root->rlink->rlink->rlink = newNode(10); root->rlink->llink->llink->llink = newNode(11); return root; } void freeTree(NodeP root) /* root を根とする二分木をメモリ上から開放する */ { if(root == NULL) return; /* 左部分木の開放 */ freeTree(root->llink); /* 右部分木の開放 */ freeTree(root->rlink); /* root の開放 */ freeTree(root); } int main(void) { NodeP root; root = createTree(); /* 二分木の生成 */ printf("breathFirst: "); breathFirst(root); /* 二分木を幅優先探索で表示 */ printf("\n"); freeTree(root); /* 二分木の開放 */ return 0; }このまま実行すると、
breathFirst: 1, 3, 7, 10, 6, 9, 8, 11, 2, 5, 4
となってしまいます。実際は
breathFirst: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
とならなければなりません。
ソースでも示したとおり、
(void)initQueue(void) , int isEmpty(void) ,
void enqueue(NodeP nd) , NodeP dequeue(void)
の四つの関数のどれかが間違っていると思われます。
それ以外の部分は、先にリストによるキューでの同様の問題を解いたときに
使ったものなので、間違っていません。
自分は、
void enqueue(NodeP nd) , NodeP dequeue(void)
辺りを間違っていると思うのですが、知恵を貸してくれませんか?