2分木、2分探索木
4.0: ベースとなるソースコードの公開について
- 本ページで示しているソースコードは，以下のURLにて取得できます
4.1: 木構造の図を作成する方法について
今回のレポートでは，2分木・2分探索木の図を描いて説明した場合には加点するので， 読みやすくかつ分かりやすいレポートの作成に励んでもらいたい． プログラム等で機械的に木の図を作成する方法を2つ紹介する．
4.1.1: Mermaidの場合
Mermaidとは，テキスト形式で各種チャートを表すことができるサービス・ツールである． Mermaid Live Editorを使うことで，ブラウザ上で簡単に試すことができる． Live Editorでは，画面左下の「Actions」項目を開くと，ブラウザ画面に表示されている図を，各種形式で画像を保存できる．
ただし，現在のMermaidは木構造をサポートしていないため， 擬似的に再現するにとどまり，ノードの位置関係が歪でバランスが悪くなる場合がある． 後述するLaTeX+Tikzを用いる方がよりバランス良く木構造を図示できるが， Mermaidの方がより手軽に十分にわかりやすい図を描画できるためここでとりあげる．
graph TD;
N1[1] --- N2[2];
N1[1] --- N3[3];
N3[3] --- N4[NULL];
N3[3] --- N5[4];
このようなMermaidのテキストをLive Editorで描画すると，次のような画像が得られる．
graph TD;はチャートの種類を示すもので，上から下にチャートを描画する指示である（TD = Top Down）．
N1からN5は図における節点を識別するための名前（ID）である．
[]の中に数字や文字列を入力すると，図にある対応する節点の中にその内容が描かれる．
また，---で節点同士をつなぐことで親子関係を表し，線を描く．
Mermaidを用いて擬似的に木構造を再現をしているため，左右の子が両方ないと描画が崩れてしまう問題がある．
この問題に対処するため，左右の子のいずれか一方がNULLの場合はダミーノードを追加して，図のバランスを保つ必要がある．
N4の節点は，N3の節点は右の子がNULLであるため，図が崩れることを防止するためのダミー節点である．
ただし，N2のように，左右の子が両方ともNULLである場合は，ダミー節点は必要ない．
次の，よくない例を示す．この図では，ラベル14のノードの子が左の子なのか，右の子なのかわからない．
graph TD;
N1[20] --- N2[10];
N2[10] --- N3[5];
N2[10] --- N4[14];
N4[14] --- N5[13];
N1[20] --- N7[26];
左右の子を明確に表すために，ラベル13のノードが左の子であるなら右にNULLラベルのノード（ダミーノード）を挿入すること．
graph TD;
N1[20] --- N2[10];
N2[10] --- N3[5];
N2[10] --- N4[14];
N4[14] --- N5[13];
N4[14] --- N6[NULL];
N1[20] --- N7[26];
4.1.2: LaTeXの場合
LaTeXでtikzというパッケージを用いると木構造の図を作成できる． そのためのサンプルを以下に示す．このサンプルをコンパイルすると2分木の基本課題 2 で示した図が出力される．
\documentclass[a4paper]{article}
\def\pgfsysdriver{pgfsys-dvipdfmx.def}
\usepackage{tikz}
\usetikzlibrary{trees}
\thispagestyle{empty}
\begin{document}
\tikzstyle{level 1}=[sibling distance=3.8cm]
\tikzstyle{level 2}=[sibling distance=1.8cm]
\tikzstyle{level 3}=[sibling distance=1cm]
\tikzstyle{edge from parent}=[draw,-]
\begin{tikzpicture}
[node distance=1cm,tnode/.style={draw,circle,thick,minimum size=2em}]
\node [tnode] (root) {A}
child { node [tnode] {C}
child {node [tnode] {D}}
child {node [tnode] {E}
child[fill=none] {edge from parent[draw=none]}
child {node [tnode] {I}}
}
}
child { node [tnode] {B}
child {node [tnode] {F}
child {node [tnode] {H}}
child {node [tnode] {G}}
}
child[fill=none] {edge from parent[draw=none]}
};
\end{tikzpicture}
\end{document}
4.2: 2分木の実装
4.2.1: 基本課題
以下は，2分木を実現するC言語プログラムであり，教科書リスト2.11 ~ 2.12 (pp.40 ~ 41) をベースに実装されている．
ソースコードは，binarytree.h，binarytree.c，main_binarytree.c に分割されている．
ヘッダーファイル binarytree.h
#ifndef INCLUDE_GUARD_BINARYTREE_H
#define INCLUDE_GUARD_BINARYTREE_H
typedef struct node {
char *label;
struct node *left;
struct node *right;
} Node;
Node *create_node(char *label, Node *left, Node *right);
void preorder(Node *n);
void inorder(Node *n);
void postorder(Node *n);
void display(Node *n);
void breadth_first_search(Node *n);
int height(Node *n);
void delete_tree(Node *n);
#endif // INCLUDE_GUARD_BINARYTREE_H
ソースファイル main_binarytree.c
#include <stdio.h>
#include <stdlib.h>
#include "binarytree.h"
int main(void) {
// Build a binary tree
Node *f = create_node("F", NULL, NULL);
Node *i = create_node("I", NULL, NULL);
Node *d = create_node("D", f, NULL);
Node *g = create_node("G", NULL, NULL);
Node *a = create_node("A", i, d);
Node *l = create_node("L", NULL, g);
Node *c = create_node("C", a, l);
preorder(c);
inorder(c);
postorder(c);
breadth_first_search(c);
display(c);
printf("height: %d\n", height(c));
delete_tree(c);
return EXIT_SUCCESS;
}
ファイル Makefile
binarytree: binarytree.o main_binarytree.o
コンパイルと実行
コマンドラインでmakeコマンドを実行すると，Cコンパイラによって実行ファイルが生成される． 実行ファイル binarytree を実行すると，図2.21 (p.38) の節点 'B' 'K' 'J' 'H' 'E' が欠けた2分木を構築し，以下のような結果が表示される．
$ make
cc -c -o binarytree.o binarytree.c
cc -c -o main_binarytree.o main_binarytree.c
cc binarytree.o main_binarytree.o -o binarytree
$ ./binarytree
PRE: C A I D F L G
IN: I A F D C L G
POST: I F D A G L C
BFS: C A L I D G F
TREE: C(A(I(null,null),D(F(null,null),null)),L(null,G(null,null)))
height: 4
$
基本課題の説明
- ラベルとして 文字列 をとる2分木を実現するプログラム
binarytreeを実装せよ． binarytree.cには，最低限以下の関数を定義すること．Node *create_node(char *label, Node *left, Node *right)labelを節点のラベル，左部分木の根をleft，右部分木の根をrightとする2分木を作成し，作成した2分木の節点のポインタを返す．
void preorder(Node *n)- 節点 n を根とする2分木を探索し，行きがけ順で節点のラベルを標準出力に表示する．
- この関数は，方式識別のための文字列
PRE:に続いて，木を行きがけ順でなぞった際の節点ラベルを順に表示する． - ラベル間は，出力例にあるように半角空白1文字で区切って表示すること
- 最後の要素の後には，改行を1文字表示すること．
void inorder(Node *n)- 節点
nを根とする2分木を探索し，通りがけ順で節点のラベルを標準出力に表示する． - この関数は，方式識別のための文字列
IN:に続いて，木を通りがけ順でなぞった際の節点ラベルを順に表示する． - ラベル間は，出力例にあるように半角空白1文字で区切って表示すること
- 最後の要素の後には，改行を1文字表示すること．
- 節点
void postorder(Node *n)- 節点
nを根とする2分木を探索し，帰りがけ順で節点のラベルを標準出力に表示する． - この関数は，方式識別のための文字列
POST:に続いて，木を帰りがけ順でなぞった際の節点ラベルを順に表示する． - ラベル間は，出力例にあるように半角空白1文字で区切って表示すること
- 最後の要素の後には，改行を1文字表示すること．
- 節点
void breadth_first_search(Node *n)- 節点
nを根とする2分木を幅優先探索し，節点のラベルを標準出力に表示する． - 課題2で実装したキューを上手く活用すること．ただし，簡単のため，キューの容量（一度に入れられる要素数）は少なくとも100あれば足りると仮定して良い．
- この関数は，方式識別のための文字列
BFS:に続いて，木幅優先探索でなぞった際の節点ラベルを順に表示する． - ラベル間は，出力例にあるように半角空白1文字で区切って表示すること
- 最後の要素の後には，改行を1文字表示すること．
- 節点
void display(Node *n)- 節点
nを根とする2分木の構造が完全に分かる形式で標準出力に表示する． - この関数は，方式識別のための文字列
TREE:に続いて，木の構造がわかるように次の書式を用いて表示する． - 表示の書式は
$X($L,$R)とする．ここで$Xは節点のラベル，$Lは左部分木を同じ書式で表す文字列，$Rは左部分木を同じ書式で表す文字列． - 例えば
C(A(I(null,null),D(F(null,null),null)),L(null,G(null,null))) - 最後の要素の後には，改行を1文字表示すること．
- 節点
int height(Node *n)- 節点
nを根とする2分木の高さを返す． - ただし，教科書の定義の高さ + 1とする．つまり
NULLの高さが0，根のみの木が高さ1とすること．
- 節点
void delete_tree(Node *n)- 節点
nを根とする2分木を削除する． - 節点
nとその子が確保したメモリをすべて開放すること．- 文字列のメモリ扱いを忘れないように注意すること
- 節点
- 次の図で示す2分木に対して，1 で実装した関数が正しく動作することを確認すること．
4.2.2: 発展課題
ヘッダーファイル binarytree_mirror.h
#ifndef INCLUDE_GUARD_BINARYTREE_MIRROR_H
#define INCLUDE_GUARD_BINARYTREE_MIRROR_H
#include <stdbool.h>
Node *create_mirror(Node *n);
bool are_mirrors(Node *n0, Node *n1);
#endif // INCLUDE_GUARD_BINARYTREE_MIRROR_H
ソースファイル binarytree_mirror.c
/* 発展課題と基本課題は分けて実装すること */
ソースファイル main_binarytree_mirror.c
#include <stdio.h>
#include <stdlib.h>
#include "binarytree_mirror.h"
int main(void) {
// Build a binary tree
Node *f = create_node("F", NULL, NULL);
Node *i = create_node("I", NULL, NULL);
Node *d = create_node("D", f, NULL);
Node *g = create_node("G", NULL, NULL);
Node *a = create_node("A", i, d);
Node *l = create_node("L", NULL, g);
Node *c = create_node("C", a, l);
Node *mirror;
mirror = create_mirror(c);
printf("are_mirrors: %d\n", are_mirrors(c, mirror));
delete_tree(c);
delete_tree(mirror);
return EXIT_SUCCESS;
}
発展課題の説明
- 2分木の鏡像を計算するプログラム
binarytree_mirrorを実装せよ． - 以下の機能を有する関数を実装し，正しく動作することを確認すること．
Node *create_mirror(Node *n)- 節点
nを根とする2分木の鏡像を作成し，作成した鏡像の根のポインタを返す． - 2分木の鏡像とは全ての非葉ノードの左右の子が入れ替わった木のことであり，下に示す Mirror は Original の鏡像である．
- 引数として与えられた
n自身やその子を変更するのではなく，新しく木を作り返すこと．
- 節点
bool are_mirrors(Node *n0, Node *n1)- 節点
n0を根とする2分木と節点n1を根とする2分木が互いに鏡像の関係になっていればtrueを，そうでなければfalseをbool型で返す． - 例えば，下に示すOriginal の根のポインタと Mirror の根のポインタを引数として渡せば，
trueが出力される．
- 節点
- その他，必要な構造体や関数は適宜 基本課題である
binarytreeから流用することmain_binarytree_mirror.c,binarytree_mirror.c,binarytree.cの3ファイルを分割コンパイルし，プログラムbinarytree_mirrorを構築すること．- すなわち，基本課題で実装した構造体や関数を
binarytree.hファイルとbinarytree.cファイルから移動するのは認めない（編集せずそのまま用いること）．
- すなわち，基本課題で実装した構造体や関数を
- これを達成するために，適宜
Makefileを編集したり，#includeを追加したりすること．
Original | Mirror
-------------------------
C | C
/ \ | / \
A L | L A
/ \ \ | / / \
I D G | G D I
/ | \
F | F
4.3: 2分探索木の実装
4.3.1: 基本課題
以下は，2分探索木を実現するC言語プログラムであり，教科書リスト 4.3 ~ 4.7 (pp.69 ~ 77) をベースに実装されている．
ソースコードは，binarysearchtree.h，binarysearchtree.c，main_binarysearchtree.c に分割されている．
ヘッダーファイル binarysearchtree.h
#ifndef INCLUDE_GUARD_BINARYSEARCHTREE_H
#define INCLUDE_GUARD_BINARYSEARCHTREE_H
#include <stdbool.h>
typedef struct node {
int value;
struct node *left;
struct node *right;
} Node;
// binarysearchtree-specific functions
int min_bst(Node *root);
bool search_bst(Node *root, int d);
void insert_bst(Node **root, int d);
void delete_bst(Node **root, int d);
// Reuse the following functions implemented for the binarytree
void inorder(Node *root);
void display(Node *root);
void delete_tree(Node *root);
#endif // INCLUDE_GUARD_BINARYSEARCHTREE_H
ソースファイル main_binarysearchtree.c
#include <stdio.h>
#include <stdlib.h>
#include "binarysearchtree.h"
int main(void) {
// Build a binary search tree
Node *root = NULL;
insert_bst(&root, 20);
insert_bst(&root, 10);
insert_bst(&root, 26);
insert_bst(&root, 14);
insert_bst(&root, 13);
insert_bst(&root, 5);
inorder(root);
display(root);
printf("search_bst 14: %d\n", search_bst(root, 14));
printf("search_bst 7: %d\n", search_bst(root, 7));
printf("min_bst: %d\n", min_bst(root));
delete_bst(&root, 10);
inorder(root);
display(root);
delete_tree(root);
return EXIT_SUCCESS;
}
ファイル Makefile
以下の行を Makefile に加える．
binarysearchtree: binarysearchtree.o main_binarysearchtree.o # added
コンパイルと実行
$ make binarysearchtree
を実行することでコンパイル出来る．
実行ファイル binarysearchtree を実行すると，以下のような結果が表示される．
$ ./binarysearchtree
IN: 5 10 13 14 20 26
TREE: 20(10(5(null,null),14(13(null,null),null)),26(null,null))
search_bst 14: 1
search_bst 7: 0
min_bst: 5
IN: 5 13 14 20 26
TREE: 20(13(5(null,null),14(null,null)),26(null,null))
$
2分探索木は，葉を除く任意の節点 n に対して，その節点のデータ n->value は，n の左の子を根とする部分木 (左部分木) 内の任意の節点 l のデータ l->value より大きく (l->value < n->value)，n の右の子を根とする部分木 (右部分木) 内の任意の節点 r のデータ r->value より小さい (n->value < r->value) という条件の下に構築されている．
この条件により，2分探索木を根から通りがけ順 (inorder) でなぞると全てのデータが整列して出力される．
この特徴は「挿入」や「削除」を正しく実装されているかのデバッグに役立つ．それらの操作後の2分探索木に対して，通りがけ順でなぞって出力されるデータが整列されたものでなければ，実装が間違っているということになるので，2分木の実装の基本課題で実装したinorder関数が利用できる (ただし，このデバッグはinorder関数が正しく実装されていることが前提である)．また，構築した2分探索木の構造を把握するために，display関数を利用できる．
基本課題の説明
- ラベルとして整数値をとる2分探索木を実現するプログラム
binarysearchtreeを実装せよ． binarysearchtree.cには，最低限以下の関数を定義すること．int min_bst(Node *root)rootを根とする2分探索木における最小値を探索し，その値を返す．2分探索木が空の場合は-1を返す．
bool search_bst(Node *root, int d)- 整数
dがrootを根とする2分探索木に存在するか検査し，存在すればtrue，存在しなければfalseをbool型で返す．
- 整数
void insert_bst(Node **root, int d)rootを根とする2分探索木に整数dを追加する．2分探索木が空の場合は，整数dの根を作成する．insert_bst関数内でNode型ポインタrootが保持する内容 (アドレス) を書き換えるため，insert_bstにはNode型ポインタのポインタ (ダブルポインタ) を第一引数にセットしている．- シングルポインタだと所謂「アドレスの値渡し」となるので，関数内でアドレスを変更しても，それは関数にコピーされた値を操作しただけなので，関数の呼び出し側には反映されない
void delete_bst(Node **root, int d)rootを根とする2分探索木から整数dを削除する．insert_bst関数と同様に，第一引数にNode型ポインタrootのポインタをセットしている．
- 以下の要件を全て満たすことを確認すること．
- 空の2分探索木に対して，値 10, 15, 18, 6, 12, 20, 9をこの順で挿入したときの作られる2分探索木を確認せよ
- 以下のすべての場合に対して探索が正しく動作することを確認せよ
- 探索するデータが根にある場合
- 葉にある場合
- 根以外の非終端節点にある場合
- データが2分探索木にない場合
- 2分探索木が空の場合，空でない場合それぞれに対して，最小値の探索が正しく動作することを確認せよ
- 削除のアルゴリズムは複雑なので，以下のようなことを考慮しながら十分にテストし，正しく動作することを確認せよ．また，各テストがどのような場合のテストであるかを明確かつ簡潔に説明すること．
- 切除される節点が子供を何個持つか
- 切除される節点が根であるか
4.3.2: 発展課題
各節点にその節点を根とする部分木の高さの情報を持たせた2分探索木プログラム bst_advanced を実装してみよう．
このようなデータ構造にしておくと，木の高さをO(1)で求められるようになり，AVL木のような平衡2分探索木の実装に役立つ．
以下に bst_advanced のソースコードを示す．ソースコードは bst_advanced.h，bst_advanced.c，main_bst_advanced.c に分割されている．
ヘッダーファイル bst_advanced.h
#ifndef INCLUDE_GUARD_BST_ADVANCED_H
#define INCLUDE_GUARD_BST_ADVANCED_H
#include <stdbool.h>
typedef struct node {
int value;
int height;
struct node *left;
struct node *right;
} Node;
// advanced bst-specific functions
Node *insert_bst(Node *root, int d);
Node *delete_bst(Node *root, int d);
// Reuse the following functions implemented for the binarytree and binarysearchtree
int min_bst(Node *root);
bool search_bst(Node *root, int d);
void inorder(Node *root);
void display(Node *root);
void display_mermaid(Node *root);
void delete_tree(Node *root);
#endif // INCLUDE_GUARD_BST_ADVANCED_H
ソースファイル main_bst_advanced.c
#include <stdio.h>
#include <stdlib.h>
#include "bst_advanced.h"
int main(void) {
// Build an advanced binary search tree
Node *root = NULL;
root = insert_bst(root, 20);
root = insert_bst(root, 10);
root = insert_bst(root, 26);
root = insert_bst(root, 14);
root = insert_bst(root, 13);
root = insert_bst(root, 5);
inorder(root);
display(root);
printf("search_bst 14: %d\n", search_bst(root, 14));
printf("search_bst 7: %d\n", search_bst(root, 7));
printf("min_bst: %d\n", min_bst(root));
root = delete_bst(root, 10);
inorder(root);
display(root);
delete_tree(root);
return EXIT_SUCCESS;
}
ファイル Makefile
以下の行を Makefile に加える．
bst_advanced: bst_advanced.o main_bst_advanced.o
コンパイルと実行
$ make bst_advanced
を実行することでコンパイル出来る．
実行ファイル bst_advanced を実行すると，以下のような結果が表示される．
$ ./bst_advanced
IN: 5 10 13 14 20 26
TREE: 20#4(10#3(5#1(null,null),14#2(13#1(null,null),null)),26#1(null,null))
search_bst 14: 1
search_bst 7: 0
min_bst: 5
IN: 5 13 14 20 26
TREE: 20#3(13#2(5#1(null,null),14#1(null,null)),26#1(null,null))
$
課題の説明
ヘッダーファイル bst_advanced.h に記述されているように，構造体 Node に height というメンバ変数を持たせ，そこに自身を根とした2分探索木の高さの情報を格納している．
高さは，2分木の基本課題1と同様に，教科書の定義の高さ + 1とするので注意すること．
その情報は，ソースファイル bst_advanced.c に実装されている get_height関数によってO(1)の時間計算量で取得でき，
子供の木の高さの情報から自身の高さの情報を再設定するreset_height関数に利用されている．
bst_advanced を完成させるためには，insert_bst関数, delete_bst関数, display関数をbst_advanced用に実装し直す必要がある (基本課題とは違って，この実装ではそれらの関数はNode型のポインタを返していることに注意) が，それ以外の関数は基本課題で実装した関数を流用できる．そのため，以下に各関数の説明を示すが，既出のものは割愛する．
ただし，構造体の構造が変更されるため，4.2.2の発展課題と違い，ソースコードをそのまま流用できないことに気をつけること．
- 各節点にその節点を根とする部分木の高さの情報を持たせた2分探索木プログラム
bst_advancedを実装せよ． - 以下の機能を有する関数を実装し，正しく動作することを確認すること．
Node *insert_bst(Node *root, int d)rootを根とする2分探索木に整数 d を追加する．2分探索木が空の場合は，整数dの根を作成する．- いずれの場合も，その木の根のポインタを返す．基本課題とは違い，この関数は再帰呼び出しを用いて実装される．
Node *delete_min_bst(Node *root)rootを根とする2分探索木における最小値を削除し，その節点が子を持つ場合は木の回復を行った後，その木の根のポインタを返す．
Node *delete_bst(Node *root, int d)rootを根とする2分探索木から整数dを削除する．insert_bst関数と同様に再帰呼び出しを用いて実装される．delete_bst関数の実装では，削除すべき節点の左右の子が両方ともNULLでないときに，min_bst関数およびdelete_min_bst関数を用いる．min_bst関数により探索した右部分木の最小値を削除対象の節点にコピーし (右部分木の最小値をもつ節点を削除対象の節点の位置に移動させ)，delete_min_bst関数により最小値をコピーされた節点の削除を行う．
void display(Node *n)- 節点
nを根とする2分木の構造が完全に分かる形式で表示する． - 表示の書式は
$X#$H($L,$R)とする．ここで$Xは節点のラベル，$Hは節点の高さ，$Lは左部分木を同じ書式で表す文字列，$Rは左部分木を同じ書式で表す文字列． - 例えば
20#4(10#3(5#1(null,null),14#2(13#1(null,null),null)),26#1(null,null))
- 節点
void display_mermaid(Node *n)- 節点
nを根とする2分木をMermaid形式で標準出力に表示する． - Mermaid形式の出力方法は本ページの4.1.1を参考にすること．
- 左右 どちらかの一方の子 が
NULLである場合は，NULLという文字列を含んだダミーノードを出力すること（これは，Mermaidで二分木をバランスよく表示するために必要である）． - 左右両方の子が
NULLである場合は，ダミーノードは出力しなくて良い．
- 左右 どちらかの一方の子 が
- 節点
- 以下の要件を全て満たすことを確認すること．
- 空の2分探索木に対して，値 10, 15, 18, 6, 12, 20, 19, 9をこの順で挿入して構築された2分探索木の各節点が正しい高さの情報を保持していることを確認せよ．
- 上記の状態から 15 を削除する．15 を削除後の2分探索木の各節点が正しい高さの情報を保持していることを確認せよ．
- 上記の状態から 19 を削除する．19 を削除後の2分探索木の各節点が正しい高さの情報を保持していることを確認せよ．
4.4: 提出物について
4.4.1: 要件確認についての注意事項
要件確認するためには，各自で適宜 main 関数の中身を書き換え，テストパターンを追加してください．
また，レポートには，
- 「プログラムの入力となるデータが何で，それがプログラムのどの部分でどのようなロジックで処理されているため，このような実行結果が得られるから，要件を満たしている」という説明文
- その実行結果
の両方を書いてください．そうでないと，レポートの読み手(採点者)は，要件を満たすことを本当に確認出来ているのか判断出来ません．
4.4.2: 自動採点の注意点
- レポートの自動採点を行うため，以下の指示に従ってプログラムを作成，提出すること．
- 課題中で，関数名，引数，戻り値等が指定されている場合，これらを変更しないこと．
- 画面出力の書式は，指定されたものを守ること．
4.4.3: 提出ファイル一覧
- report4.pdf （レポート）
- Makefile
- binarytree.c
- binarytree.h
- main_binarytree.c
- binarytree_mirror.c（発展課題）
- binarytree_mirror.h（発展課題）
- main_binarytree_mirror.c（発展課題）
- binarysearchtree.c
- binarysearchtree.h
- main_binarysearchtree.c
- bst_advanced.c（発展課題）
- bst_advanced.h（発展課題）
- main_bst_advanced.c（発展課題）
4.4.4: 提出ファイルの構成
- ディレクトリ
class4を作成して，その中に上記ファイルを配置すること． class4を ZIP で圧縮したclass4.zipファイルを manaba に提出すること．
（class4.zip）の構造）
class4/
+-report4.pdf
+-Makefile
+-binarytree.c
+-binarytree.h
+-main_binarytree.c
+-binarytree_mirror.c
+-binarytree_mirror.h
+-main_binarytree_mirror.c
+-binarysearchtree.c
+-binarysearchtree.h
+-main_binarysearchtree.c
+-bst_advanced.c
+-bst_advanced.h
+-main_bst_advanced.c
4.5: 提出締切
- 2024年11月18日（月）13:30