2017年度「アルゴリズムとデータ構造」のページ

練習問題

2018年1月4日出題
  1. 二分木について、以下の処理を行う関数を書け。 ただし、各節点は整数(int型)のラベルを持ち、小さい順に順序づけ られているものとし、各々の処理は順序を保つものとする。 なお、データ構造のC言語での実装において、 以下の構造体定義を使用するものとし、 bintree.hに書かれているものとする。
    struct node {
    	struct node	*left, *right;
    	int	data;
    };
    struct bintree {
    	struct node	*root;
    };
    	    

    どの関数についても、関数の第一引数は、struct bintree * 型とする。 struct bintreeの実体を呼び出し側で用意し、それへのポインタを第一引数として渡すものとする。

    木の初期化は以下の関数bintree_init()で行うものとする。

    #include <stdlib.h>
    #include "bintree.h"
    
    void
    bintree_init(struct bintree *tree)
    {
    	tree->root = NULL;
    }
                
    1. 節点の個数を返す。
      size_t	bintree_count(const struct bintree *);
      		
    2. ラベルの値の総和を返す。
      int	bintree_sum(const struct bintree *);
      		
    3. ラベルの値を小さい順に一行に一つの書式で出力する。
      void	bintree_print(const struct bintree *);
      		
    4. 最小のラベルをもつ節点へのポインタを返す。木が空のときは、NULLを返す。
      struct node	*bintree_min(struct bintree *);
      		
    5. 最大のラベルをもつ節点へのポインタを返す。木が空のときは、NULLを返す。
      struct node	*bintree_max(struct bintree *);
      		
    6. 第二引数で指定された値が木の節点のラベルに存在すれば、その節点へのポインタを返す。なければ、NULLを返す。
      struct node	*bintree_find(struct bintree *, int);
      		
    7. 第二引数で指定された値が木の節点のラベルに存在すれば、NULLを返す。なければ、追加して、新たに作成された節点へのポインタを返す。
      struct node     *bintree_insert(struct bintree *, int);
      		
    8. 第二引数で指定された値が木の節点のラベルに存在すれば、その節点を削除し、1を返す。なければ、0を返す。
      int     bintree_delete(struct bintree *, int);
      		
    9. すべての節を削除して、空木にする。struct bintreeの実体は削除しない。
      void    bintree_clear(struct bintree *);
      		
  2. 二分木について、以下の処理を行う関数を書け。 ただし、各節点は整数(int型)のラベルを持ち、 小さい順に順序づけられているものとし、各々の処理は順序を保つものとする。 さらに、各節点にはその値が有効であるか無効であるかを表すフラグがあるものとする。 以下で、「値が木の節点にラベルとして存在する」は「その値をラベルに持ち有効である」を意味するものとする。 なお、データ構造のC言語での実装において、 以下の構造体定義を使用するものとし、 bintreex.hに書かれているものとする。
    struct node {
    	struct node	*left, *right;
    	int	data;
    	char	valid;		/* 0: invalid, 1: valid */
    };
    struct bintree {
    	struct node	*root;
    };
    	    

    どの関数についても、関数の第一引数は、struct bintree * 型とする。 struct bintreeの実体を呼び出し側で用意し、それへのポインタを第一引数として渡すものとする。

    木の初期化は以下の関数bintree_init()で行うものとする。

    #include <stdlib.h>
    #include "bintree.h"
    
    void
    bintree_init(struct bintree *tree)
    {
    	tree->root = NULL;
    }
                
    1. 節点の個数を返す。
      size_t	bintree_count(const struct bintree *);
      		
    2. ラベルの値の総和を返す。
      int	bintree_sum(const struct bintree *);
      		
    3. ラベルの値を小さい順に一行に一つの書式で出力する。
      void	bintree_print(const struct bintree *);
      		
    4. 最小のラベルをもつ節点へのポインタを返す。木が空のときは、NULLを返す。
      struct node	*bintree_min(struct bintree *);
      		
    5. 最大のラベルをもつ節点へのポインタを返す。木が空のときは、NULLを返す。
      struct node	*bintree_max(struct bintree *);
      		
    6. 第二引数で指定された値が木の節点のラベルに存在すれば、その節点へのポインタを返す。なければ、NULLを返す。
      struct node	*bintree_find(struct bintree *, int);
      		
    7. 第二引数で指定された値が木の節点のラベルに存在すれば、NULLを返す。なければ、追加して、新たに作成されたまたは有効にされた節点へのポインタを返す。
      struct node     *bintree_insert(struct bintree *, int);
      		
    8. 第二引数で指定された値が木の節点のラベルに存在すれば、その節点を無効にし、1を返す。なければ、0を返す。
      int     bintree_delete(struct bintree *, int);
      		
    9. すべての節を削除して、空木にする。struct bintreeの実体は削除しない。節点の削除は無効化だけではなく実際に削除すること。
      void    bintree_clear(struct bintree *);
      		

戻る