Как рассчитать глубину двоичного дерева поиска

Ответ 1

Что-то вроде этого:

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

И чтобы получить сумму глубин каждого ребенка:

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);
}

Теперь, надеюсь, информативное объяснение в случае, если это домашнее задание. Подсчет количества узлов довольно прост. Прежде всего, если node не является node (node == null), он возвращает 0. Если это node, он сначала подсчитывает свое "я" (1), а также число узлов в его левом поддереве плюс число узлов в его правом поддереве. Еще один способ подумать - вы посещаете каждый node через BFS и добавляете его к счету для каждого node, который вы посещаете.

Суммирование глубин аналогично, за исключением того, что вместо добавления только одного для каждого node, node добавляет глубину его самого. И он знает глубину своего "я", потому что его родитель рассказал об этом. Каждый node знает, что глубина его детей - это собственная глубина плюс одна, поэтому, когда вы получаете глубину левого и правого дочерних элементов node, вы сообщаете им, что их глубина - это текущая глубина node плюс 1.

И снова, если node не является node, он не имеет глубины. Поэтому, если вам нужна сумма глубины всех корневых node детей, вы передаете в корневой каталог node и корневую глубину node следующим образом: sumDepthOfAllChildren(root, 0)

Рекурсия весьма полезна, это совсем другой способ думать о вещах и берет практику, чтобы привыкнуть к ней

Ответ 2

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);
    }
}

Ответ 3

Для любого заданного дерева количество узлов равно 1 для корня плюс число узлов в левом поддереве плюс число узлов в правом поддереве:)

Детали, например, чтобы убедиться, что на самом деле есть левое или правое поддерево, "оставлены читателю".

Ответ 4

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

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

Ответ 5

Это решение еще проще.

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

Ответ 6

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

Ответ 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);
}

Ответ 8

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;
}

Ответ 9

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;
}

Ответ 10

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); 
}