二分木のメソッド（続き）.

Presentation on theme: "二分木のメソッド（続き）."— Presentation transcript:

1 二分木のメソッド（続き）

2 中間順に木をなぞるメソッド class Vertex def initialize …
　　attr_attribute :data, :left, :right def inorder # 中間順でなぞる != nil　　 # vの左の子をなぞる print @data # 頂点のラベルを表示 @right.inorder != nil　# vの右の子をなぞる end # def of inorder end # class

3 先行順、後行順に木をなぞるメソッド class Vertex def initialize …
　　attr_attribute :data, :left, :right def 　　　　　 # 中間順でなぞる != nil　　 # vの左の子をなぞる print @data # 頂点のラベルを表示 @right.inorder != nil　# vの右の子をなぞる end # def preorder postorder inorder 後行 先行 @left.preorder != nil　　 # vの左の子をなぞる @left.postorder != nil　　 # vの左の子をなぞる print @data # 頂点のラベルを表示 @right.postoder != nil　# vの右の子をなぞる @right.preorder != nil　 # vの右の子をなぞる end # class

4 「高さ」を返すメソッド この木の高さは？ 左部分木の高さ と 右部分木の高さ の大きい方＋１ 左部分木の高さ＝ @left.height
左部分木の高さ　と 右部分木の高さ 　　　の大きい方＋１ 左部分木の高さ＝ @left.height 右部分木の高さ＝ @left.height ただし子がいない時も考慮すること （例えば両方とも子がいない＝葉の場合は、高さ０！）

5 考えるべきケース 子ノードがない場合： これは高さ ０ 左（または右）の子ノードだけがある場合 両方の子がある場合 子ノードを根とする
子ノードがない場合：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　これは高さ　０ 左（または右）の子ノードだけがある場合 両方の子がある場合 子ノードを根とする 部分木の高さ＋１ 左子ノードを根とする部分木の高さ 右子ノードを根とする部分木の高さ 　　の大きいほう＋１　（前のスライド参照）

6 「高さ」を返すメソッド（続） class Vertex def initialize …
　　attr_attribute :data, :left, :right def height if != nil) # 左の子あり leftHeight elsif != nil) # 左の子なし、右の子あり return else # 左の子も右の子もなし return 0 # 葉 end # if --- 左の子がある場合のみ残る if != nil) # 右の子あり rightHeight else # 右の子なし return 1+leftHight end # if --- 二つの子あり if (leftHeight > rightHeight) return 1+leftHeight else return 1+rightHeight end # if end # def end # class

7 葉を表示するメソッド class Vertex def initialize …
　　attr_attribute :data, :left, :right def inorder # 中間順でなぞる != nil　　 # vの左の子をなぞる print @data # 頂点のラベルを表示 @right.inorder != nil　# vの右の子をなぞる end # def of inorder このままだと「葉」以外の頂点も表示 そこで「葉」の条件を加えれば良い end # class それは、子頂点がないこと！ if == nil) && == nil) 注意：showが返す「配列」から求めても良いが、Vertexクラスのメソッドにならない