筑波大学理工情報生命学術院システム情報工学研究群情報理工学位プログラム 2018年8月実施基礎科目問題 IV

Author

祭音Myyura

Description

二分木を用いて int 型の値の集合を格納するデータ構造を C 言語で実装する．図 1 に，二分木の各ノードの構造体 node の定義を示す．構造体node は，表 1 に示した関数で操作される．その関数の実装を図 2 に示す．ただし，関数 malloc は常に成功するものとする．このとき以下の問いに答えなさい．

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

図 1: 構造体 node の定義

表 1: 構造体 node を操作する関数

関数	説明
struct node new_node(int value, struct node left, struct node *right)	新たなノードを作成し，値 value，左の子ノードへのポインタ left，右の子ノードへのポインタ right を設定し，作成したノードのポインタを返す．
void traverse(struct node *n)	ポインタ n が示すノードを根とする二分木に含まれるノード群の値を中順にて標準出力に出力する（出力の順序は，左の部分木に格納された値の集合，根の値，右の部分木に格納された値の集合とする）．

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

struct node *new_node(int value, struct node *left, struct node *right)
{
    struct node *n = malloc(sizeof(struct node));
    n->value = value;
    n->left = left;
    n->right = right;
    return (n);
}

void traverse(struct node *n)
{
    if (n == NULL) return;
    traverse(n->left);
    printf("%d\n", n->value);
    traverse(n->right);
}

図 2: 表 1 に示した関数の実装

(1) 以下に示す関数 main() が実行されたとき，この関数が標準出力に出力する内容を答えなさい．

int main()
{
    struct node *top;
    top = new_node(5, new_node(9, NULL, NULL), new_node(7, NULL, NULL));
    traverse(top);
    return (0);
}

(2) 二分木を深さ優先で走査する方法としては，関数 traverse() で実装した中順以外に，前順と後順がある．前順で走査する関数と後順で走査する関数を以下の表に示す．これらの関数を定義しなさい．

関数	説明
void pre_order_traverse(struct node *n)	ポインタ n が示すノードを根とする二分木に含まれるノード群の値を前順にて標準出力に出力する（出力の順序は，根の値，左の部分木に格納された値の集合，右の部分木に格納された値の集合とする）．
void post_order_traverse(struct node *n)	ポインタ n が示すノードを根とする二分木に含まれるノード群の値を後順にて標準出力に出力する（出力の順序は，左の部分木に格納された値の集合，右の部分木に格納された値の集合，根の値とする）．

(3) 関数 traverse() を用いて値が昇順で出力されるような二分木となるように値を挿入する関数insert() を以下の表に示す．ただし，既に二分木に格納されている値と同じ値がこの関数に与えられることはないものとする．関数 insert() が正しく動作するように，以下の空欄 [ (a) ] ~ [ (e) ] を埋めなさい．

関数

説明

struct node *insert(struct node *top, int value)

ポインタ top が NULL のときは新しくノードを作成し，そのノードに値を格納し，そのノードへのポインタを返す．それ以外の場合，ポインタ top が示すノードに格納されている値よりも値 value が小さい場合には左の部分木に値 value を格納するために再帰的にこの関数を呼んでポインタ top を返し，大きい場合には右の部分木に値 value を格納するために再帰的にこの関数を呼んでポインタ top を返す．

struct node *insert(struct node *top, int value)
{
    if (top == NULL)
        return (new_node(value, NULL, NULL));
    if (value < [空欄 (a)])
        [空欄 (b)] = insert([空欄 (c)]);
    else
        [空欄 (d)] = insert([空欄 (e)]);
    return (top);
}

(4) 設問 (3) で作成した関数 insert() を用いて空の二分木に3つの値 5，7，9 を挿入する関数 main() を以下に示す．この関数を実行したときに，関数 insert() が呼び出される回数（関数 insert() が再帰呼び出しにより呼び出される回数も含める）を答えなさい．

int main()
{
    struct node *top = NULL;
    top = insert(top, 5);
    top = insert(top, 7);
    top = insert(top, 9);
    traverse(top);
    return (0);
}

(5) 設問 (4) で示した関数main() では，空の二分木に3つの値 5，7，9 をこの順序で挿入している．この順序を変えることで関数 insert() が呼び出される回数が変化する． 3つの値 5，7，9 を空の二分木に挿入する際に，関数 insert() が呼び出される回数が最小となる順序を1つ答えなさい．

(6) 設問 (3) で示した関数 insert() を用いて，空の二分木に関数 insert() が呼び出される回数が最小となる順序で \(N\) 個の異なる値を挿入したとする．この二分木に，さらにもう 1 個の値を挿入したときに関数 insert() が呼び出される回数を \(N\) を用いて答えなさい．

Kai

(1)

1
2
3

9
5
7

(2)

void pre_order_traverse(struct node *n) {
    if (n == NULL) return;
    printf("%d\n", n->value);
    pre_order_traverse(n->left);
    pre_order_traverse(n->right);
}

void post_order_traverse(struct node *n) {
    if (n == NULL) return;
    post_order_traverse(n->left);
    post_order_traverse(n->right);
    printf("%d\n", n->value);
}