配列でのキューを用いた二分木の幅優先

[tela]

こんにちは。自分ではできてると思うのですが、なぜか出力の順序がおかしくなるのでお願いします。

[問題]　配列によるキューを用いて、二分木を幅優先（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)
/* キューが空なら１、空でなければ０を返す */
{
  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)
辺りを間違っていると思うのですが、知恵を貸してくれませんか？

[tela]

すいません。
vod freeTree(NodeP root) が少し間違ってました。
正しくは↓です。

void freeTree(NodeP root)
/* root を根とする二分木をメモリ上から開放する */
{
  if(root == NULL) return;

  /* 左部分木の開放 */
  freeTree(root->llink);
  /* 右部分木の開放 */
  freeTree(root->rlink);
  /* root の開放 */
  free(root);
}

[box]

dequeue()で、{と}の数が合わないため、コンパイルエラーが出ます。

[box]

また、キューを管理するにはsizeだけでは不足です。
配列の最後にenqueueして先頭からdequeueする、という
構造ですので、「どこから」と「どこまで」の２つを
管理する必要があります。

[tela]

＞dequeue()で、{と}の数が合わないため、コンパイルエラーが出ます。
すいません。忘れていました。

NodeP dequeue(void)
/* キューから節点を取り出す */
{
  NodeP nd;

  if (queue->size > 0 ) {
    queue->size--;
    nd = queue->array[queue->size];
    return nd;
  }
}

ですね。この状態で、出力する値の順序がおかしくなってしまいます。

＞「どこから」と「どこまで」の２つを管理する必要があります。

enqueue と dequeue 、両方間違っているということでしょうか？

[tela]

暫く考えましたが、やはり分かりません。

if の条件部分は変えなければなりませんか？

[box]

> enqueue と dequeue 、両方間違っているということでしょうか？

enqueue()は、「キューの最後に格納する」ことができていると思います。

しかし、dequeue()は、「キューの先頭から取り出す」ことができていなくて、
「キューの最後から取り出す」ようになっています。
sizeとは別に、「次にどこから取り出すか」という状態を管理する必要があります。

[tela]

できました！
なるほど、そういうことでしたか。
最初のデータを格納しておいて、
残りのデータを一つ前にもっていき、
配列の要素数を一つ減らせばよかったんですね。
ありがとうございました。