이진 트리의 가장 깊은 노드 찾기

이진 트리의 높이를 찾을 수 있지만 이진 트리의 가장 깊은 노드 (동일한 깊이의 경우 여러 노드)를 반환하는 방법을 알 수있는 높이 방법이 있습니다. 리프가 비어 나타내는이진 트리의 가장 깊은 노드 찾기

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 
     [email protected]+1 
     [email protected]+1 
    end 
     height=[height1,height2].max 
     height 
    end 
    end 
end

출처

2012-10-26 John

컨텍스트를 추가 할 수 있습니까? 그것은 일종의 모호한 예이며, 필요한 것이 무엇인지 분명하지 않습니다. 예상되는 출력을 가진 일부 입력으로 충분해야합니다. – robertodecurnex

이진 트리의 가장 깊은 노드를 찾고 싶습니다. – John

우리는 구현에 대해 아무것도 모릅니다. 보다 자세한 내용을 제공 할 수 있다면 더 나은 솔루션을 제공 할 수 있습니다. 나는 너에게 하나를 주려고하지만 많은 것을 가정하려고 노력할 수있다. – robertodecurnex

가정이다 :

이진 트리는 실제로 루트 노드입니다
child_nodes는 c 배열

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

리팩토링 자식 노드의 ollection :

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-26 17:51:14 robertodecurnex

고맙습니다. 나는 너무 잘 설명하지 않았습니다. 나는 예제를 추가했다. – John

@ 존, 거기에 l/r 차일드를 사용하는 예제가 있습니다 (주어진 노드가 BinaryNode의 인스턴스가 아니거나 주어진 경우) – robertodecurnex

사소한 nitpick : 아마도 노드의 깊이가'depth'의 이름으로'height'로 바뀝니다. 일반적으로 루트에서 거리입니다. – Phrogz

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-04 14:22:12

이진 트리의 가장 깊은 노드 찾기

답변

관련 문제