3

バイナリ ツリーの高さを見つけることができる高さメソッドがありますが、バイナリ ツリーの最も深いノード (同じ深さの場合は複数のノード) を返す方法がわかりません。

BinaryNode.new(1,BinaryNode.new(2,leaf,leaf),BinaryNode.new(3,leaf,leaf))

葉は空を表します

このツリーの高さは 2 で、最も深いノードは 2,3 (同じ深さ)

class BinaryNode 
  include Enumerable
  def initialize(element,lchild,rchild)
    @element, @lchild, @rchild = element, lchild, rchild
  end
  def deepestNode
    if self.nil?
      0
    else
      height1=@lchild.height+1
      height2=@lchild.height+1
    end
      height=[height1,height2].max
      height
    end
  end
end
4

2 に答える 2

2

仮定:

  • バイナリ ツリーは、実際にはルート ノードです。
  • child_nodes は、子ノードのコレクションを配列として返します
class BinaryNode
  attr_reader :element

  def initialize(element,lchild,rchild)
    @element, @lchild, @rchild = element, lchild, rchild
  end

  def height
    if @lchild.nil? && @rchild.nil?
      return 0
    else
     [@lchild, @rchild].collect {|n| n.nil ? 0 : n.height + 1 }.max      
    end
  end

  def deepest_nodes
    return [self] if self.height == 1

    [@lchild, @rchild].select {|n| !n.nil? && (n.height == self.height - 1)}.collect {|n| n.deepest_nodes}.flatten
  end
end

リファクタリング:

class BinaryNode
  attr_reader :element

  def initialize(element,lchild,rchild)
    @element, @lchild, @rchild = element, lchild, rchild
  end

  def child_nodes
    [@lchild, @rchild].compact
  end

  def height
    if self.child_nodes.empty?
      return 0
    else
      self.child_nodes.collect {|n| n.height + 1 }.max      
    end
  end

  def deepest_nodes
    return [self] if self.depth == 1

    self.child_nodes.select {|n| n.height == self.height - 1}.collect {|n| n.deepest_nodes}.flatten
  end
end

要素の取得:

BinaryNode.new(1,BinaryNode.new(2,leaf,leaf),BinaryNode.new(3,leaf,leaf)).deepest_nodes.collect {|n| n.element }
于 2012-10-26T17:51:14.883 に答える
0 
struct node //structure type
{
    int data;
    struct node *left,*right;
};

from main()
{
    Deepestnode= MaxDepth(root);
}

//return type// function name//
struct node*    MaxDepth (struct node* temp, int depth)
{  
    if(temp->next!=NULL && temp->right!=NULL)
    {
        MaxDepth(temp->left ,depth+1);
        MaxDepth(temp->right,depth+1);
    }
    else if(temp->left==NULL && temp->right!=NULL)
        MaxDepth(temp->right,depth+1);
    else if(temp->left!=NULL && temp->right==NULL)
        MaxDepth(temp->left,depth+1);

    else // temp->left==NULL &&temp->right==NULL   
    {
        if(max<depth)
        {
           max=depth;
           Deepestnode=temp;
        }
        return(Deepestnode);
     }
}
于 2013-02-04T14:22:12.730 に答える