Bir ikili arama ağacının derinliğini hesaplama

Question

İkili Arama Ağacı'nın her bir düğümünün derinliklerinin toplamını hesaplamak istiyorum.

Öğelerin tek tek derinlikleri önceden depolanmamış. Herhangi bir ağaca için

Answer 1

, düğüm sayısı kökü artı sol alt ağaç düğüm sayısına artı aslında emin orada yapmak gibi sağ alt ağaç :)

Ayrıntıları düğüm sayısı için 1 bir sol veya sağ alt ağaçtır, "okuyucuya bırakılır". Böyle

Answer 2

şey:

int countChildren(Node node) 
{ 
    if (node == null) 
     return 0; 
    return 1 + countChildren(node.getLeft()) + countChildren(node.getRight()); 
} 

Ve her çocuk derinliklerinde toplamını almak için: Bu ödev olduğu durumda bir umutla bilgilendirici açıklama için Şimdi

int sumDepthOfAllChildren(Node node, int depth) 
{ 
    if (node == null) 
     return 0; // starting to see a pattern? 
    return depth + sumDepthOfAllChildren(node.getLeft(), depth + 1) + 
        sumDepthOfAllChildren(node.getRight(), depth + 1); 
} 

. Düğüm sayısını saymak oldukça basittir. Her şeyden önce, eğer düğüm bir düğüm (node == null) değilse, 0 değerini döndürür. Eğer bir düğüm ise, ilk olarak kendi kendini (1), sol alt ağacındaki düğüm sayısını artı sağ alt ağacındaki düğümler. Bunu düşünmenin başka bir yolu da, her düğümü BFS aracılığıyla ziyaret edersiniz ve ziyaret ettiğiniz her düğüm için bir sayı eklersiniz.

Derinliklerin toplamı benzerdir, her düğüm için yalnızca bir tane eklemek yerine, düğüm kendi derinliğini ekler. Ebeveyninin söylediği gibi, kendi derinliğinin ne olduğunu bilir. Her bir düğüm, çocuğun derinliğinin kendi derinliği artı bir olduğunu bilir, bu yüzden bir düğümün sol ve sağ çocukların derinliğini elde ederseniz, onlara derinliklerinin geçerli düğümün derinliği artı 1 olduğunu söylersiniz.

Ve Yine, düğüm bir düğüm değilse, derinliği yoktur. Bu nedenle, tüm kök düğümün çocuklarının derinliklerinin toplamını istiyorsanız, kök düğümünü ve kök düğümünün derinliğini şu şekilde iletirsiniz: sumDepthOfAllChildren(root, 0)

Özyineleme oldukça yararlıdır, bu yalnızca şeyler hakkında farklı bir düşünme şeklidir ve onunla

Answer 3

public int numberOfNodes() 
{ 
    // This node. 
    int result = 1; 

    // Plus all the nodes from the left node. 
    Node left = getLeft(); 
    if (left != null) 
     result += left.numberOfNodes(); 

    // Plus all the nodes from the right node. 
    Node right = getRight(); 
    if (right != null) 
     result += right.numberOfNodes(); 

    return result; 
} 

Answer 4

public int countNodes(Node root) 
{ 
    // Setup 
    // assign to temps to avoid double call accessors. 
    Node left = root.getLeft(); 
    Node right = root.getRight(); 
    int count = 1; // count THIS node. 

    // count subtrees 
    if (left != null) count += countNodes(left); 
    if (right != null) count += countNodes(right); 

    return count; 
} 

Answer 5

public class Node { 
    private Node left; 
    private Node right; 
    public int size() { return 1+ (left==null?0:left.size())+ (right==null?0:right.size());} 
} 

Answer 6

private static int getNumberOfNodes(Node node) { 
    if (node == null) { 
     return 0; 
    } 

    return 1 + getNumberOfNodes(node.left) + getNumberOfNodes(node.right); 
} 

Answer 7

int depth(treenode *p) 
{ 
    if(p==NULL)return(0); 
    if(p->left){h1=depth(p->left);} 
    if(p=>right){h2=depth(p->right);} 
    return(max(h1,h2)+1); 
} 

Answer 8

int maxDepth(Node node) { 
    if (node == null) { 
     return (-1); // an empty tree has height −1 
    } else { 
     // compute the depth of each subtree 
     int leftDepth = maxDepth(node.left); 
     int rightDepth = maxDepth(node.right); 
     // use the larger one 
     if (leftDepth > rightDepth) 
      return (leftDepth + 1); 
     else 
      return (rightDepth + 1); 
    } 
} 

01 alışması için pratik ister

Answer 9

public int getDepthHelper(TreeNode<T> node) { 
    int treeHeightLeft; 
    int treeHeightRight; 
    //get height of left subtree 
    if(node.leftNode == null) 
     treeHeightLeft = 1; 
    else { 
     treeHeightLeft = getDepthHelper(node.leftNode) + 1; 
    } 

    //get height of right subtree 
    if(node.rightNode == null) 
     treeHeightRight = 1; 
    else { 
     treeHeightRight = getDepthHelper(node.rightNode) + 1; 
    } 
    return Math.max(treeHeightLeft, treeHeightRight); 
} 

Answer 10

Bu çözüm daha da basittir.

public int getHeight(Node root) 
{ 
    if(root!=null) 
     return 1+ Math.max(getHeight(root.leftchild),getHeight(root.rightchild)); 
    else 
     return 0; 
}