查找二叉樹的最深節點

我有一個高度方法，能夠找到二叉樹的高度，但不知道如何返回二叉樹的最深節點（如果有相同深度的多個節點）。查找二叉樹的最深節點

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子節點的ollection作爲數組

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

非常感謝。我沒有解釋得太好。我添加了一個例子。 – John

@John，你有使用l/r childs的例子（假設它們可以是nil或BinaryNode的一個實例） – robertodecurnex

Minor nitpick：我可能會重命名深度爲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

查找二叉樹的最深節點

回答

相關問題