システムプログラミング序論　演習　

演習 5: 複雑なデータ構造とポインタ(2)

問題：二分探索木を用いたデータの探索


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

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

struct node *insert_data(int x, struct node *p);
int search_tree(int x, struct node *p);
void print_tree(struct node *p);

int main(int argc, char *argv[])
{
  FILE *fp;
  int i, x;
  struct node *root;

  if (argc != 2) {
    printf("missing file argument\n");
    return 1;
  }

  fp = fopen(argv[1], "r");
  if (fp == NULL) {
    printf("can't open %s\n", argv[1]);
    return 1;
  }

  root = NULL;

  for (i = 0; i < 20; i++) {
    fscanf(fp, "%d", &x);
    root = insert_data(x, root);
  }

  print_tree(root);

  while (1) {
    scanf("%d", &x);
    if (x <= 0)
      break;
    if (search_tree(x, root) == 1)
      printf("%d: Found\n", x);
    else
      printf("%d: Not found\n", x);
  }

  fclose(fp);

  return 0;
}

struct node *insert_data(int x, struct node *p)
{
  if (p == NULL) {
    p = (struct node *) malloc(sizeof(struct node));
    if (p == NULL) {
      printf("Out of memory\n");
      exit(1);
    }
    p->data = x;
    p->left = NULL;
    p->right = NULL;

    return p;
  }

  if (x == p->data)
    return p;

  if (x < p->data)
    p->left = insert_data(x, p->left);
  else
    p->right = insert_data(x, p->right);

  return p;
}

void print_tree(struct node *p)
{
  if (p == NULL)
    return;

  print_tree(p->left);
  printf("%d\n", p->data);
  print_tree(p->right);
}

課題 1

関数int search_tree(int x, struct node *p)を作成し，プログラムを完成さ せなさい． プログラムの実行ファイル名はex6-1とする．
入力に使うファイルは こちらから、ダウンロードすること．こ のファイルを使って，./ex6-1 ./sys-prog-ex5-data.txt を実行し，適当な整数 を入力し，入力された数字が木構造に含まれているかどうかを確認しなさい．

課題 2

このプログラムを元に，木構造に含まれている全ての整数の和を計算し，表示 するプログラムを作成しなさい． プログラムの実行ファイル名はex6-2とする．
入力に使うファイルは こちらから、ダウンロードすること．こ のファイルを使って，./ex6-2 ./sys-prog-ex5-data.txt を実行し，木構造に含 まれている整数の和が出力されるかどうかを確認しなさい．