%=====================================================================
% 秋田高専 2E 情報工学概論 テキスト
%　　テーマ　ツリー構造(2分木)
%    本テキストの内容
%        ・
%        ・
%        ・
%        ・
%　　　 　・
%
% last updated 2005.12.19
%    created by  Masashi Yamamoto
%     e-mail yamamoto@akita-nct.jp
%=====================================================================
\documentclass[10pt,a4paper]{jarticle}
\usepackage{graphicx,amsmath,amssymb,ascmac,float}
\usepackage{html, listings, jlisting}
\usepackage{url}
\oddsidemargin 0mm  %左の余白 25.4mm-0mm　奇数ページ
\evensidemargin 0mm %左の余白 25.4mm-0mm　偶数ページ
\textwidth 160mm
\newcommand{\command}[1]{「\texttt{#1}」}
\newcommand{\cl}[1]{\texttt{#1}}
\newcommand{\tw}[1]{\texttt{#1}}
%
\newcounter{toi_num}
\newcommand{\toi}{\textbf{\texttt [問\arabic{toi_num}]}
   \addtocounter{toi_num}{1}}
%
\newcommand{\qbox}[2]{
{\fboxsep=0pt \fboxrule=0.4pt\fbox{\hspace{#1}#2\hspace{#1}}}
}
%
\renewcommand{\lstlistingname}{リスト}
\lstset{language=C,%
        basicstyle=\footnotesize,%
        commentstyle=\textit,%
        classoffset=1,%
        keywordstyle=\bfseries,%
	frame=tRBl,framesep=5pt,%
	showstringspaces=false,%
        numbers=left,stepnumber=1,numberstyle=\footnotesize%
	}%
%
\begin{htmlonly}
\usepackage{verbatimfiles}
 \providecommand{\lstinputlisting}[2][]{\verbatimlisting{#2}}
\end{htmlonly}
%
\begin{document}
\title{ツリー構造(その1)}
\author{山本昌志\thanks{独立行政法人　秋田工業高等専門学校　電気情報工学科}}
\date{2006年1月16日}
\maketitle
%
%
%=====================================================================
\section{本日の学習内容}
%=====================================================================
%---------------------------------------------------------------------
\subsection{前回の復習}
%---------------------------------------------------------------------
前回の講義では，再帰呼び出しというアルゴリズムを学習した．リスト1は階乗の計算を
再帰呼び出しで行っている．このプログラムは，階乗の漸化式
\begin{align}
 &n!=n\times(n-1)!& &0!=1&
\end{align}
をそのままプログラミングした形になっている．
%----------- 階乗を計算するプログラム --------------------
\lstinputlisting
[caption=再帰呼び出しを使った階乗を計算するプログラム,label=prog:kaijyo]
{program/kaijyo.c}
%
%
%---------------------------------------------------------------------
\subsection{本日の学習内容}
%---------------------------------------------------------------------
本日はデータ構造のツリー構造の学習を行う．本日のゴールは，以下の通りである．
\begin{itemize}
 \item リストとツリー構造の違いが分かる．
 \item リストを実現する方法が理解できる．これは復習であるが，これが分からないと
 ツリー構造のプログラムはできない．
 \item 2分探索木のデータの追加と削除，探索の方法が理解できる．
\end{itemize}

実際のツリー構造のプログラムは，来週の講義とする．
%
%=====================================================================
\section{ツリー構造とは}
%=====================================================================
%---------------------------------------------------------------------
\subsection{ツリー構造とは}
%---------------------------------------------------------------------
同じような複数のデータを表す場合，配列やリスト，スタック，キューのようなデータ構
造を学習してきた．これらのデータ構造で教科書のFig.6-1のような，階層をもつデータ
の集まりを表すことは，困難である．このように階層構造をもつデータを処理するときに
威力を発揮するのがツリー構造である．ツリーとは，tree(木)のことである．

ツリー構造の例として，教科書では生き物やWindosのファイルシステムのツリー構造が書
かれている．諸君が学習で使っているUNIXのファイルシステムは，図
\ref{fig:Unix_file_system}のようになっている．
\begin{quote}
 \begin{itemize}
  \item[\textbf{[練習1]}]ツリー構造をしたデータは，他に何があるか?
 \end{itemize}
\end{quote}
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio,scale=0.8]
  {figure/UNIX_file.eps}
  \caption{UNIXのファイル構造}
  \label{fig:Unix_file_system}
 \end{center}
\end{figure}
%
%---------------------------------------------------------------------
\subsection{ツリー構造を実現する方法}
%---------------------------------------------------------------------
教科書\cite{text_algorithm_data}に書いてあるように，ツリー構造のデータ構造はリス
トを少し変えるだけで実現できる．そこで，まずはリストのおさらいをしてから，ツリー
構造を実現する方法を示す．
%--------------------------
\subsubsection{単方向リスト}
%--------------------------
リストは，図\ref{fig:list}のようなデータ構造である．一つの要素(element)はデータ
とつながりを表すポインターからなり，構造体で表すことができる．リストは，各々の要
素のつながりしか分からないので，最初の要素を示すポインターが必要である．このよう
なリストを使う場合，次のような宣言を行えば良い．
%
\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
/* --- 単方向リストを表す構造体 ---*/
typedef struct tag_list_element{
  struct tag_list_element *next;
  int data;
}list_element;

list_element *top;      /* 先頭を示すポインター */
 \end{verbatim}
\end{quote}
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio,scale=0.8]
  {figure/list.eps}
  \caption{単方向リスト}
  \label{fig:list}
 \end{center}
\end{figure}
%

配列に比べ，リストはデータの追加と削除が容易である．データの追加と削除の方法は，
教科書~\cite{text_algorithm_data}のFig.6-3(p.163)に示してあるとおりである．
\begin{quote}
 \begin{itemize}
  \item[\textbf{[練習1]}]配列のデータの追加と削除の方法を述べよ．
 \end{itemize}
\end{quote}

リストを使って，実際にデータの追加と削除を行うプログラムをリスト\ref{prog:list}
に示す．このプログラムの動作は以下の通りである．
\begin{itemize}
 \item 入力した整数は，リストの形で記憶される．
 \item エレメント作成の後，直ちに，データが昇順に並ぶように，接続のポインター(\tw{next})を設定する．
 \item 負の整数で，データ入力が終了する．
 \item 入力されたデータを昇順に表示する．
 \item データを削除する．
 \item 残っているデータを昇順に表示する．
\end{itemize}
%----------- リストを使ったプログラム --------------------
\lstinputlisting
[caption=リストを使ったプログラム例,label=prog:list]
{program/list_euc.c}
%
%---------------------
\subsection{ツリー構造}
%---------------------
ツリー構造は，図\ref{fig:tree}のように表すことができる．一つのノードは，リスト同
様，構造体で表すことができる．構造体は，データと子を示すポインターを持つことにな
る．リストでは先頭の要素を表すポインターが必要であったが，ツリー構造ではルートを
示すポインターが必要である．構造体の宣言は，以下のようにすればよいだろう．
%
\begin{quote}
 \setlength{\baselineskip}{12pt}
 \begin{verbatim}
/* --- ツリーのノードを表す構造体 ---*/
typedef struct tag_tree_node{
  struct tag_tree_node *ko_1, *ko_2, *ko_3;
  int data;
}tree_node;

tree_node *root;      /* ルートを示すポインター */
 \end{verbatim}
\end{quote}
%

このツリーを実現させるための構造体には，ひとつ問題がある．子の数が3と決められて
いる．また，多くのデータでは子の数が不定であることが多い．そのため，必要なポイン
ターの数が分からない．この解決方法については，次週の講義で説明する．ここでは，リ
ストとほとんど同じ構造体で，ツリー構造が実現できることを理解して欲しい．

%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio,scale=0.8]
  {figure/tree.eps}
  \caption{ツリー構造}
  \label{fig:tree}
 \end{center}
\end{figure}
%
%---------------------------------------------------------------------
\subsection{ツリー構造の各部の名称}
%---------------------------------------------------------------------
ツリー構造にはいろいろ名称があり，それを表\ref{table:tree_name}と図
\ref{fig:tree_peace_name}に示す．なぜ，図\ref{fig:tree}のようなデータ構造をツリー
構造と呼ぶか?．それは，この図を反対にしてみるのである．すると，根が一番下にきて，
枝や葉が上にあることが分かるであろう．まさに，木である．

\begin{table}[hbta]
 \caption{ツリー構造の名称}
 \label{table:tree_name}
 \begin{center}
  \begin{tabular}{ll}
   \hline
   \multicolumn{1}{c}{構成要素} & \multicolumn{1}{c}{内容}\\
   \hline\hline
   ルート(root:根) & 最上位のノード \\
   ノード(node:節) & 枝が分かれるところ \\
   リーフ(leaf:葉) & 子がないノード \\
   ブランチ(branch:枝) & 親と子を結ぶ線 \\
   親(parent) & 上のノード \\
   子(child) & 下のノード \\
   兄弟(brother) & 同じ親を持つノード \\
   \hline 
  \end{tabular}
 \end{center}
\end{table}
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio,scale=0.8]
  {figure/tree_structure.eps}
  \caption{ツリー構造．図中の親子関係はノード\tw{E}を基準にしている．}
  \label{fig:tree_peace_name}
 \end{center}
\end{figure}
%
%---------------------------------------------------------------------
\subsection{ツリー構造の要素の追加と削除}
%---------------------------------------------------------------------
教科書~\cite{text_algorithm_data}のp.166-167の通り．
%
%
%=====================================================================
\section{2分木(binary tree)}
%=====================================================================
ツリー構造のうち，子の数が最大2となるものを2分木と言う．そして，ある規準に従って
その2分木が作られている場合，2分探索木(binary search tree)と呼ばれる．ここでは，
その2分探索木のデータの追加と削除，探索方法を示す．

残りは，教科書~\cite{text_algorithm_data}に沿って説明する．
%=====================================================================
\section{練習問題}
%=====================================================================
\setcounter{toi_num}{1}
\begin{quote}
 \begin{itemize}
  \item[\toi]図の中で2分木になっているものはどれか?
   \begin{center}
   \begin{figure}[H]
    \begin{tabular}{cc}
     %------------------------------
     \begin{minipage}[b]{0.25\hsize}
      \begin{center}
       \includegraphics[keepaspectratio, scale=0.8]{figure/B_Q1.eps}\\
       (ア)
      \end{center}
     \end{minipage} &
     %------------------------------
     \begin{minipage}[b]{0.25\hsize}
      \begin{center}
       \includegraphics[keepaspectratio, scale=0.8]{figure/B_Q2.eps}\\
       (イ)
      \end{center}
     \end{minipage}
     %------------------------------
     \begin{minipage}[b]{0.25\hsize}
      \begin{center}
       \includegraphics[keepaspectratio, scale=0.8]{figure/B_Q3.eps}\\
       (ウ)
      \end{center}
     \end{minipage}
     %------------------------------
     \begin{minipage}[b]{0.25\hsize}
      \begin{center}
       \includegraphics[keepaspectratio, scale=0.8]{figure/B_Q4.eps}\\
       (エ)
      \end{center}
     \end{minipage}
    \end{tabular}
   \end{figure}
   \end{center}
%
  \item[\toi]最初はデータが無く，以下の並びでデータが追加される．2分木を作成せよ．
	     \begin{itemize}
	      \item[(ア)]\tw{45,64,28,90,63,24,98,23,42,95}
	      \item[(イ)]\tw{69,26,36,45,89,65,11,12,14,23,44}
	      \item[(ウ)]\tw{15,18,16,23,44,55,63,72,84,95,10}
	      \item[(エ)]\tw{85,76,71,65,61,53,45,41,33}
	      \item[(オ)]\tw{57,23,75,15,32,77,86,11,31,55,70,95}
	     \end{itemize}
  \item[\toi]図の2分木にデータを追加する．以下の問いに答えよ．
	     \begin{itemize}
	      \item[(ア)]\tw{18}を追加する．
	      \item[(イ)]\tw{53,68}と順に追加する．
	      \item[(ウ)]\tw{70,73,67,75,77,66}と順に追加する．
	      \item[(エ)]\tw{66,77,75,67,73,70}と順に追加する．
	     \end{itemize}
   \begin{figure}[H]
    \begin{center}
     \includegraphics[keepaspectratio, scale=0.8]{figure/Q_add_data.eps}\\
     データを追加する2分木
    \end{center}
   \end{figure}
  \item[\toi]図の2分木にデータを削除する．以下の問いに答えよ．
	     \begin{itemize}
	      \item[(ア)]\tw{72}を削除する．
	      \item[(イ)]\tw{46}を削除する．
	      \item[(ウ)]\tw{28}を削除する．
	      \item[(エ)]\tw{52,46,54}と順に削除する．
	     \end{itemize}
   \begin{figure}[H]
    \begin{center}
     \includegraphics[keepaspectratio, scale=0.8]{figure/Q_del_data.eps}\\
     データを削除する2分木
    \end{center}
   \end{figure}
 \end{itemize}
\end{quote}
%---------------------------------------------------------------------
\subsection{レポート提出要領}
%---------------------------------------------------------------------
提出方法は，次の通りとする．
% 
\begin{quote}
 \begin{tabular}{ll}
  期限 & 1月23日(月) AM 10:40 \\
  用紙 & A4 \\
  提出場所 & 山本研究室の入口のポスト \\
  表紙 & 表紙を1枚つけて，以下の項目を分かりやすく記述すること．\\
       & \qquad 授業科目名「情報工学」\\
       & \qquad 課題名「課題　ツリー構造(2分木)」\\
       & \qquad 2E\quad 学籍番号\quad 氏名\\
       & \qquad 提出日\\
  内容 & 2ページ以降に問いに対する答えを分かりやすく記述すること．
 \end{tabular}
\end{quote}
%
%=====================================================================
%  参考文献
%=====================================================================
\bibliographystyle{jplain}
\bibliography{reference}
%=====================================================================
\end{document}