二分木のメソッド（続き）
中間順に木をなぞるメソッド class Vertex def initialize … attr_attribute :data, :left, :right def inorder # 中間順でなぞる @left.inorder if @left != nil # vの左の子をなぞる print @data # 頂点のラベルを表示 @right.inorder if @right != nil # vの右の子をなぞる end # def of inorder end # class
先行順、後行順に木をなぞるメソッド class Vertex def initialize … attr_attribute :data, :left, :right def # 中間順でなぞる @left.inorder if @left != nil # vの左の子をなぞる print @data # 頂点のラベルを表示 @right.inorder if @right != nil # vの右の子をなぞる end # def preorder postorder inorder 後行 先行 @left.preorder if @left != nil # vの左の子をなぞる @left.postorder if @left != nil # vの左の子をなぞる print @data # 頂点のラベルを表示 @right.postoder if @right != nil # vの右の子をなぞる @right.preorder if @right != nil # vの右の子をなぞる end # class
「高さ」を返すメソッド この木の高さは？ 左部分木の高さ と 右部分木の高さ の大きい方＋１ 左部分木の高さ＝ @left.height 左部分木の高さ と 右部分木の高さ の大きい方＋１ 左部分木の高さ＝ @left.height 右部分木の高さ＝ @left.height ただし子がいない時も考慮すること （例えば両方とも子がいない＝葉の場合は、高さ０！）
考えるべきケース 子ノードがない場合： これは高さ ０ 左（または右）の子ノードだけがある場合 両方の子がある場合 子ノードを根とする 子ノードがない場合： これは高さ ０ 左（または右）の子ノードだけがある場合 両方の子がある場合 子ノードを根とする 部分木の高さ＋１ 左子ノードを根とする部分木の高さ 右子ノードを根とする部分木の高さ の大きいほう＋１ （前のスライド参照）
「高さ」を返すメソッド（続） class Vertex def initialize … attr_attribute :data, :left, :right def height if (@left != nil) # 左の子あり leftHeight = @left.height elsif (@right != nil) # 左の子なし、右の子あり return 1+@right.height else # 左の子も右の子もなし return 0 # 葉 end # if --- 左の子がある場合のみ残る if (@right != nil) # 右の子あり rightHeight = @right.height else # 右の子なし return 1+leftHight end # if --- 二つの子あり if (leftHeight > rightHeight) return 1+leftHeight else return 1+rightHeight end # if end # def end # class
葉を表示するメソッド class Vertex def initialize … attr_attribute :data, :left, :right def inorder # 中間順でなぞる @left.inorder if @left != nil # vの左の子をなぞる print @data # 頂点のラベルを表示 @right.inorder if @right != nil # vの右の子をなぞる end # def of inorder このままだと「葉」以外の頂点も表示 そこで「葉」の条件を加えれば良い end # class それは、子頂点がないこと！ print @data if (@left == nil) && (@right == nil) 注意：showが返す「配列」から求めても良いが、Vertexクラスのメソッドにならない