アルゴリズムとデータ構造 第2章 リスト構造 5月20日分

Slides:



Advertisements
Similar presentations
アルゴリズムとデータ構造 第2回 線形リスト(復習).
Advertisements

正規表現からのDFA直接構成.
プログラミング演習II 2004年11月 30日(第6回) 理学部数学科・木村巌.
プログラムのパタン演習 解説.
プログラミング言語としてのR 情報知能学科 白井 英俊.
アルゴリズムとデータ構造 第2章 リスト構造 5月17日分
実行時のメモリ構造(1) Jasminの基礎とフレーム内動作
Problem G : Entangled Tree
プログラミング言語論 第6回 型 情報工学科 篠埜 功.
情報工学概論 (アルゴリズムとデータ構造)
データ構造とアルゴリズム 第7回 木 ~ データ構造(3)~.
構造体.
プログラミング演習II 2004年12月 21日(第8回) 理学部数学科・木村巌.
データ構造とアルゴリズム 第4回 リスト ~ データ構造(1)~.
データ構造とアルゴリズム 第6回の2 木 ~ データ構造(3)~.
INSERT(x,p,L)の例 (一部) 磯 直行 2009年5月5日
データ構造と アルゴリズム 第八回 知能情報学部 新田直也.
大岩 元 慶応大学環境情報学部 二分木 データ構造とプログラミング(10) 大岩 元 慶応大学環境情報学部
データ構造と アルゴリズム 第四回 知能情報学部 新田直也.
二分探索木によるサーチ.
アルゴリズムとデータ構造 1章の復習 第2章 リスト構造 5月10日
C言語講座 第3回 ポインタ、配列.
2009/10/16 いろいろなデータ構造 第3講: 平成21年10月16日 (金) 4限 E252教室 コンピュータアルゴリズム.
アルゴリズムとデータ構造 2011年7月4日
データ構造とアルゴリズム 第4回 リスト ~ データ構造(1)~.
オブジェクト指向 プログラミング 第十三回 知能情報学部 新田直也.
アルゴリズムとデータ構造1 2006年6月16日
プログラミング 4 記憶の割り付け.
二分木のメソッド(続き).
2011/06/21 情報知能学科「アルゴリズムとデータ構造」 担当:白井英俊
第10章 これはかなり大変な事項!! ~ポインタ~
アルゴリズムとデータ構造勉強会 第6回 スレッド木
二分探索木における要素削除 データ構造とプログラミング(10)
アルゴリズムとデータ構造 第3章 ヒープ 6月10日分
計算機プログラミングI 第11回 再帰 再帰的なメソッド定義 帰納的定義 再帰的なデータ構造 計算機プログラミングI (増原) 2003年度.
第9回 優先度つき待ち行列,ヒープ,二分探索木
VBで始めるプログラミング こんにちは、世界。 /28 NARC.
データ構造と アルゴリズム 第六回 知能情報学部 新田直也.
データ構造と アルゴリズム 第五回 知能情報学部 新田直也.
Cプログラミング演習 第10回 二分探索木.
データ構造とアルゴリズム論 第9章 木構造 平成29年12月20日 森田 彦.
データ構造とアルゴリズム論 第9章 木構造 平成30年6月27日 森田 彦.
アルゴリズムとデータ構造 はじめに 第1章 アルゴリズムと計算量
第2回課題 配布した通り.氏名・学生番号を忘れないこと.
第5章 計算とプログラム 本章で説明すること ・計算の概観と記述法 ・代表的な計算モデル ・プログラムとプログラム言語.
アルゴリズムとデータ構造 2011年7月8日課題の復習
6.データ構造入門 6-1.連結リスト(Linked List) 6-2.スタック(Stack) 6-3.キュー(Queue)
15.cons と種々のデータ構造.
データ構造とアルゴリズム 第11回 リスト構造(1)
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分
情報知能学科「アルゴリズムとデータ構造」
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分の復習
情報数理Ⅱ 第11章 データ構造 平成29年1月18日.
アルゴリズムとプログラミング (Algorithms and Programming)
プログラミング 3 2 次元配列.
AVL木.
第9回 優先度つき待ち行列,ヒープ,二分探索木
アルゴリズムからプログラムへ GRAPH-SEARCH
情報工学概論 (アルゴリズムとデータ構造)
アルゴリズムとデータ構造 2013年7月8日
アルゴリズムとデータ構造1 2009年6月15日
アルゴリズムとデータ構造 第2章 リスト構造 5月24日分
ヒープソート.
データ構造とアルゴリズム論 第9章 連結リスト
アルゴリズムとデータ構造 2010年6月17日
データ構造と アルゴリズム 第四回 知能情報学部 新田直也.
TList リスト構造とは? 複数のデータを扱うために、 データの内容と、次のデータへのポインタを持つ構造体を使う。
7.木構造 7-1.データ構造としての木 7-2.2分探索木 7-3.高度な木.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
アルゴリズムとデータ構造 2012年7月9日
Presentation transcript:

アルゴリズムとデータ構造 第2章 リスト構造 5月20日分 アルゴリズムとデータ構造 第2章 リスト構造 5月20日分 情報知能学科 白井英俊

リスト構造 リスト(線形リスト)構造 リスト(線形リスト)構造の基本単位:セル(Cell) データ部とポインタを持つデータ構造 時にはセルのことを 箱と呼ぶかもしれないが御免! リスト(線形リスト)構造 データ部とポインタを持つデータ構造 ポインタが1つの場合、このデータ構造が「直線」的に並ぶので、「線形リスト」という リスト(線形リスト)構造の基本単位:セル(Cell) ポインタ データ部: データの記憶用 ポインタ部:別なセルのアドレス データ部 2

リスト構造(教科書p.16) リスト構造 ポインタを持つデータ構造 以下のような Cell (セル)クラスを考え、線形リスト構造を作る: クラス (Rubyのクラス) 概念図 Cell data データ部 next ポインタ class Cell def initialize(x,y) @data = x    @next = y end

ここには、隣のセルへのポインタ(アドレス)が入っている 線形リストの例 data next data next 青木 石川 ここには、隣のセルへのポインタ(アドレス)が入っている この印は、このセルに続くセルがないことを意味 b = Cell.new(石川, nil ) a = Cell.new(青木, b) nil は、このセルに続くセルがないことを意味 これは次のように書いてよい: a = Cell.new(青木, Cell.new(石川, nil ))

リストとセル 例えて言えば、 セルは電車の車両一両 (線形)リストは、車両(セル)が複数個連なった「列車」 他の車両を連結する「連結部」   セルは電車の車両一両 他の車両を連結する「連結部」   ポインタ データを記憶する場所 (線形)リストは、車両(セル)が複数個連なった「列車」

線形リストの特徴 data データ部 next ポインタ 後ろのセルの ポインタ リストは「セル」が「つながって」できている この「つながり」は、次によって実現:    前のセルの「ポインタ部」に「後ろのセルへのポインタ(アドレス)」が入っている このセルの後にどんなセルがあるかは分かるが、このセルの前にどんなセルがあるかは分からない Cell data データ部 next ポインタ 後ろのセルの ポインタ

クラスCellにメソッドを追加する Cellをつないだり、後続のCellにアクセスしたり、書き替えたりできるよう、Cellのクラス定義に、インスタンスメソッドを追加する アクセス(access)=(主に)値をとりだす ここではCellのメソッドが『リストに対する関数(メソッド)」を兼ねる ものとして考えていく クラス (Rubyのクラス) 概念図 Cell data データ部 next ポインタ class Cell def initialize(x,y) @data = x    @next = y end   attr_accessor :data, :next

クラスCellにメソッドを追加する(続) 「このメソッドが適用されたセル」とは、例えば、x.get(2)の場合、 xの値のセルのこと Cellに3つのインスタンスメソッドを付け加える: get(n) : このメソッドが適用されたセルから数えてn番目のセルを返す(get) insert(n, content) :このメソッドが適用されたセルから数えて n 番目のセルの前に、contentをデータ部にもつセルを挿入(insert) delete(n) :このメソッドが適用されたセルから数えてn番目のセルを削除する(delete)

1 2 クラスCellにgetメソッドを追加 “b” x “a” “b” “c” get(n) :このメソッドが適用されたセルから数えてn番目のセル(へのポインタ)を返す 例: x.get(1) => data next “b” 要するに x.next と同じ 1 2 data next data next data next x “a” “b” “c” 解説: たとえて言えば、この例においてxは3両編成の電車を指している。 先頭の車両を「0」号車、2番目の車両を「1」号車、などとする。 ここでは x.get(n) により 「n」号車(へのポインタ)を返したい。

1 2 クラスCellのgetメソッド x x “a” “b” “c” 下の例では、 x.get(0) ⇒ x.get(1) ⇒ 「“a”をdataにもつセル 」、つまりxそれ自体 (self) 「“b”をdataにもつセル 」、つまり x.next 「“c”をdataにもつセル 」、 x.next.next (後ろのセルがない) nil 1 2 data next data next data next x x “a” “b” “c”

クラスCellにgetメソッドを追加 class Cell def initialize(x,y) @data = x @next = y end # def attr_accessor :data, :next def get(n) return self if (n <= 0) if (@next != nil) return @next.get(n-1) else return nil end # if end #def end # class 既に定義済み n=0なら呼ばれたセル自身(self)を返す follower = @next  # 後ろのセル if (follower != nil) return follower.get(n-1) else return nil end # if n>0 かつ 後続のセルがある場合 再帰!次のセルから見て n-1番目のセルを返す。 @next が次のセルを与える。 今見ているセルからn番目に あるセルは、「その後ろのセル」 からみれば、n-1番目のセル

クラスCellのgetメソッドの検証 “b” “c” “a” x c b c = Cell.new(“c”, nil) ; b = Cell.new("b", c) ; x = Cell.new("a", b) # getの検証 p x.get(0) p x.get(1) p x.get(2) class Cell def get(n) return self if (n <= 0) if (@next != nil) return @next.get(n-1) else return nil end # if end #def end n = 0 =x (= self) next n = 1 =b.get(0) =b n = 2 = b.get(1) “a” “b” “c” data next = c.get(0) = c x c b

クラスCellにinsertメソッドを追加 insert(n, content) :このメソッドが適用されたセルから数えて n 番目のセルの前に、contentをデータ部にもつセルを挿入(insert)する 1 2 data next data next data next “a” “b” “c” x この時、x.insert(2,”d”)を実行すると data next “d” となるようにできればよい それには、 (1) n-1番目のセルを見つける、 (2)新しいセルを作る、(3)ポインタを正しく設定する、ことができればよい

クラスCellにinsertメソッドを追加 class Cell def initialize(x,y) @data = x @next = y end # def attr_accessor :data, :next def get(n) …. end def insert(n, cont) if (n == 1) @next = Cell.new(cont, @next) else # n > 1 と仮定 @next.insert(n - 1, cont) end # if end #def end # class 既に定義済み follower = @next  # 後ろのセル if (n == 1) return @next = Cell.new(cont, follower) else # n>1 を仮定 return follower.insert(n-1, cont) end # if ここにはちょっと問題がある 本当は値のチェックをすることが必要。 今見ているセルからn番目に あるセルは、「その後ろのセル」 からみれば、n-1番目のセル

クラスCellのinsertメソッドの検証 c = Cell.new(“c”, nil) ; b = Cell.new("b", c) ; x = Cell.new("a", b) xからみて2番目のセルの前に“d”をデータ部にもつセルを作って挿入する x.insert(2, “d”) def insert(n, cont) if (n == 1) @next = Cell.new(cont, @next) else # n > 1 と仮定 @next.insert(n - 1, cont) end # if end #def n =2 “d” next next n =1 bからみて1番目のセルの前に挿入 b.insert(1,”d”) “d” next data next data next data next data next 2 1 3 “a” 1 2 x “b” “c” b c

1 2 0番目のセルの前にinsert? “b” “c” “d” insert(n, content) :このメソッドが適用されたセルから数えて n 番目のセルの前に、contentをデータ部にもつセルを挿入(insert)する 1 2 data next data next data next “a” “b” “c” x この時、x.insert(0,”d”)を実行すると data next “d” となるようにしなければならない それには、セルの値を書き変えのではなく、 変数xの値を書き変える必要がある⇒これはインスタンスメソッドではできない!

リスト構造とポインタの話… b リスト構造は基本的なデータ構造 Rubyの配列は、リスト構造で作られている Prologの配列もリスト構造   例: [a, b] は2つのセルがつながっている  [a, b] = [a | [b] ] = [a | [b | [] ] ] 応用は広い: これから述べる木構造やネットワークも、リスト構造が基本 この話は「人工知能プログラミング」を履修している人向けのもの |はセルの間の仕切り nil に相当するのがPrologでは[ ] a b

リスト構造とポインタ(続) x “a” ポインタとは、それが指しているオブジェクトが計算機のメモリ中に置かれているアドレス(場所) Rubyでは、ポインタは、それが指しているオブジェクトと同一視される だから、x.data は ”a”を、x.next はそのポインタが指しているオブジェクトとみなせる。 x data next “a”

リスト構造とポインタ(続) 変数(インスタンス変数も含む)の使われ方は二通り:代入と参照 例: @next = Cell.new(cont, @next) 代入:変数の値の 書き換えー別なポインタで書き変わる 参照:変数の値 が取り出される 練習問題(どこがポインタの参照と代入か?) (1) x.next = x.next.next (2) y[3] = y[1]

リスト構造とポインタ(問題解答) x “b” 練習問題(どこがポインタの参照と代入か?) (1) x.next = x.next.next (2) y[3] = y[1] えっ、と思ったかもしれない。(1)は次のような状況を想定していた: 左辺でも右辺でもx は参照。ただし、左辺のx.next は代入。右辺はすべて参照 x “a” “b” data next そして(2)は次のような状況を想定していた: y = [1,2,3,4,5] 左辺でも右辺でも y は参照。ただし、 y[3] は代入、y[1]は参照

リスト構造とポインタ(補足) 変数(例えば var)の値がポインタの場合、 var . メソッド もしくは var . メソッド(引数…)  によって、ポインタが指しているオブジェクトに対しメソッドが呼び出される だから、 var = [1, 2, 3] の場合 var.size も  [1, 2, 3].size も同じ結果を返す これが、insert メソッドの定義で  @next.insert(n - 1, cont) が行っていること

クラスCellにdeleteメソッドを追加 delete(n) :このメソッドが適用されたセルから数えてn番目のセルを削除する(delete) 変数aの値が以下のような連結リストへのポインタとする: x 2 3 1 data next data next data next data next “a” “b” “d” “c” x.delete(2) を実行すると となるようにできればよい

deleteメソッドの動き 3 2 1 2 x “b” “c” “d” 先の結果を書き直すと x.delete(2)の結果は: “a” 2 1 x “a” “b” “c” 2 “d” 元のリストの3番目が2番目のセルになる。 元の2番目の要素は消えたわけではない。 が、リストの先頭からはアクセス(接近)不能=削除!

クラスCellにdeleteメソッドを追加 class Cell def initialize(x,y) @data = x   @next = y end # def attr_accessor :data, :next def get(n) …. end   def insert(n,cont) … end def delete(n) if (n == 1) @next = @next.next else # n > 1 と仮定 @next.delete(n - 1) end # if end #def end # class 既に定義済み follower = @next  # 後ろのセル if (n == 1) return @next = follower.next else # n>1 を仮定 return follower.delete(n-1) end # if ここにはちょっと問題がある 値のチェックをすることが必要。 今見ているセルからn番目に あるセルは、「その後ろのセル」 からみれば、n-1番目のセル

クラスCellのdeleteメソッドの検証 c = Cell.new(“c”, nil) ; d = Cell.new(“d”, c) b = Cell.new("b", c) ; x = Cell.new("a", b) x.delete(2) def delete(n) if (n == 1) @next = @next.next else # n > 1 と仮定 @next.delete(n - 1) end # if end #def n =2 bからみて1番目のセルを削除 n =1 b.delete(1) data next data next data next data next 1 2 x “a” “b” 1 “d” “c” 2 b d c

リスト構造の練習問題 リストがCellによって表わされているとする。 問題1. リストの最後のCellを返すメソッド last をCellに付け加えよ。 使用例: x.last data next data next data next x “a” “b” “c” 要するに、リストxの最後のCell へのポインタを返す

クラスCellのlastメソッド x “b” “c” “a” c b 考え方:  c = Cell.new(“c”, nil) ; b = Cell.new("b", c) ; x = Cell.new("a", b) によって下図のリスト構造が作られたとする。  x.last の結果は c (の値であるポインタが指しているセル)である。ポインタを順々にたどっていって(x, b, c)、それがリストの最後かどうかは  @next がnilかどうかで判断 最後でなければ、「次のセルから始まるリストの最後」を返せばよい (x.last = b.last ) data next data next data next x “a” “b” “c” c b

リスト構造の練習問題 x “b” “c” y “d” “e” リストがCellによって表わされているとする。 問題2.二つのリストをつなぎ合わせるメソッド concatをCellに付け加えよ。 使用例: x.concat(y) data next data next data next x “a” “b” “c” 要するに、リストxの最後のCell のポインタの値をnilからyの値に 変える y “d” “e”

concatメソッド x “b” “c” y “d” “e” 二つのリストをつなぎ合わせるメソッド concat 使用例: x.concat(y) やりたいのは、 ここの値をyの値(ポインタ) にすること x.last 問題1の結果から data next data next data next x “a” “b” “c” y “d” “e”

リスト構造の練習問題 リストがCellによって表わされているとする。 問題3.リストのデータ部を要素に持つ配列を返すメソッド elements をCellに付け加えよ。 使用例: x.elements ⇒ [“a”, “b”, “c”] data next data next data next x “a” “b” “c” ヒント:x.elementsは、xのセルの「後ろのセル」のelementsの結果 に、xのセルのデータ部をつけ加えたもの ただし、xの値がnilの場合は空配列 [ ] を返す

リスト構造の練習問題 リストがCellによって表わされているとする。 問題4(やや難).リストの順番が逆順になるようにポインタをつなぎかえるメソッドreverseをCellに付け加えよ。 使用例: z=x.reverese data next data next data next x “a” “b” “c” z

宿題(締め切りは5月17日) c = Cell.new(“c”, nil) ; b = Cell.new("b", c) ; x = Cell.new("a", b) Cellクラスにlast, concat, elements,reverseメソッドを加える lastメソッド: (引数なし)リストの最後のセルを返す。  例: x.last ⇒ cの値となっているセル concatメソッド: (引数は一つ)リストを接合する  例: xとyがセルのインスタンスとする。x.concat(y) ⇒ xのセルの後ろにセルy(から始まるリスト)がつながる elemetsメソッド: (引数なし)このメソッドが適用されたセルから始まるリストのデータ部を要素とする配列を返す。  例:x.elements ⇒ [“a”, ”b”, ”c”] (難)reverseメソッド: (引数なし)リストの順番を逆にする  例:x.reverse ⇒ 先頭が”c”、最後が”a”をdata部にもつリストとなる

リストの実現のための別な方法 “b” x “b” 今見てきた方法だと、1番目の要素の削除や、1番目に要素を挿入するのは、難しい それに対し、次の方法は、分かりやすい方法  ⇒ 先頭にいつもダミー(データ記憶には使わな いセル)を置く方法 今までのリスト: x “a” “b” 新方法のリスト: contents x “a” “b”

リストの実現のための別な方法(続) ダミーセルの値を書き換えることで、 次を実現するプログラムが容易に書ける  (1) xの1番目のセルとして新たな要素を挿入    x.contents = Cell.new(新たな要素,x.contents)  (2) 1番目のセルを削除     x.contents =x.contents.next

リストの実現のための別な方法(続) 先のCellクラスに加えて、新たにリスト構造を表すためのデータ構造(クラス)をNCellとする class NCell def initialize(lst) @contents = lst end attr_accessor :contents  使用例: ここでダミーセルを作っている c = Cell.new(“c”, nil) ;b = Cell.new("b", c) a = Cell.new("a", b) ; x = NCell.new(a)

練習問題 このように定義したNCellクラスに、4つのインスタンスメソッドを付け加える: [注] 必要ならCellの定義も書き変えよ get(n) :リストのn番目のセルを返す。ただし、先頭のセルを0番目、その次は1番目、等とする。 insert(n, content) :リストのn 番目のセルの前に、contentをデータ部にもつセルを挿入する。n=0の時は先頭のセルの「前に」挿入する。 delete(n) :リストのn番目のセルを削除する。n=0の時は先頭のセルを削除する。 size : 引数なし。リストを構成している(リストにつながっている)セルの個数(ただしダミーセルは無視する)を返す。

3 1 2 参考:NCellを用いたリスト構造 x “c” “b” “d” “e” w = Cell.new(“c”, nil) ; y = Cell.new("b", w) z = Cell.new("a", y) ; x = NCell.new(z) contents 3 1 x “c” “a” “b” = z = w x.get(0) x.get(1) = y x.get(2) 2 x.insert(0, “d”) “d” “e” x.insert(2, “e”) x.delete(0) x.delete(2) x.size = 3

ちょっとbreak ここまでで質問はありますか?

リストの応用(1) 二重線形リスト構造 線形リスト構造:ポインタが一つ 次のようなセルをつなぐことで実現 二重線形リスト構造:ポインタは二つ   次のようなセルをつなぐことで実現 二重線形リスト構造:ポインタは二つ data データ部 next ポインタ prec ポインタ data データ部 next ポインタ

二重線形リスト構造(続) 線形リスト構造 二重線形リスト構造 後続のセルだけ、たどることが可能 後続のセルだけではなく、その前のセルもたどることが可能

リストの応用(2) 木構造 根つき木、もしくは木構造 (1) 頂点と辺とから作られる 頂点: vertex, node, ノード、節点、…  (1) 頂点と辺とから作られる   頂点: vertex, node, ノード、節点、… 辺: edge, arc, アーク、枝、…  木はグラフの一種。 頂点は  、辺は  や      で表す (2) 根(root) という特別な頂点がただ一つある

木構造(続) 根は特別な頂点 根から、他のどの頂点へも辺をたどっていくことができる。これを『パス(道)』という。 木とグラフの違い  根から、他のどの頂点へも辺をたどっていくことができる。これを『パス(道)』という。 木とグラフの違い   頂点から別な頂点へのサイクルがない(頂点へ至る複数のパスが存在しない)

木とグラフの違い グラフ: 『根』のような特殊な頂点はない。v0 からv4へは、v1を通っても、v2を通ってもいける(複数のパスがある)。

木の用語 v0 v1 v3 v2 v4 v6 v5 v8 v7 親と子 (例: v1とv4)  2つの頂点が結ばれているとき、上の頂点を親(parent)、下の頂点を子(son)、という v1 v3 v2 v4 v6 v5  兄弟(例:v4とv5)  同じ親を持つ子頂点同士を兄 弟(brother)、という v8 v7 最も左の子を、第一子(first child)という ( 例: v1の第一子はv4、v5の第一子はv7 ) 右隣の兄弟を、次の兄弟(next brother)、という( 例: v1の次の兄弟はv2、v2の第一子はv3 ) 葉(leaf): 子を持たない頂点(例: v2, v3, v4, v7, …)

木の表現 線形リスト構造を、セル(の集まり)で表したように、木構造を次のようなデータ構造(ノードと呼ぶ)で表す class Node def initialize(u,v,w,x) @label = u @parent = v @firstChild = w @nextBrother = x end @parent @firstChild self

木の表現(続) クラスNodeを図示すると、次のようになる 頂点 親頂点 兄弟頂点 子頂点 label (ラベル) parent (親) 一個一個が以下の構造をもつ 親頂点 label (ラベル) parent (親) firstChild(第一子) nextBrother(次の兄弟) @parent @firstChild self @nextBrother 兄弟頂点 子頂点

練習:木の表現 右の木をNodeクラスを用いて表す v0 v1 v3 v2 v4 v6 v5 それには、7つのNodeインスタンスが必要…一つの頂点が一つのNodeインスタンスに対応 v1 v3 v2 v4 v6 v5 根の頂点 v0 の表現 ラベル v0 nil 親頂点 頂点 v1 第一子 nil 次の兄弟

練習:木の表現(続) v0 v1 v3 v2 v4 v6 v5 根の頂点 v0 の表現 v0 nil nil 頂点 v1 v1 頂点 v2 ラベル nil 親頂点 v1 v3 第一子 v2 nil 次の兄弟 v4 v6 v5 頂点 v1 ラベル v1 親頂点 第一子 次の兄弟 頂点 v2 頂点 v4

練習:木の表現(続) v0 v3 v1 v2 v6 v4 v5 v0 nil nil v1 v2 v4 v5 nil ラベル 親頂点 第一子 次の兄弟 ラベル v1 ラベル v2 親頂点 親頂点 第一子 第一子 次の兄弟 次の兄弟 v4 ラベル v5 ラベル 親頂点 親頂点 nil 第一子 第一子 次の兄弟 次の兄弟

練習:木の表現を完成させよう v0 v3 v1 v2 v6 v4 v5 v0 nil nil v1 v2 v3 nil v5 v6 v4 ラベル nil 親頂点 第一子 nil 次の兄弟 ラベル v1 v2 ラベル 親頂点 第一子 次の兄弟 v3 ラベル 親頂点 第一子 次の兄弟 親頂点 nil 第一子 次の兄弟 v5 ラベル 親頂点 第一子 次の兄弟 v6 ラベル 親頂点 第一子 次の兄弟 v4 ラベル nil 親頂点 nil 第一子 次の兄弟