Вычисление высоты двоичного дерева

Question

Мне нужна помощь в теории расчета высоты двоичного дерева, как правило, обозначение.

Я прочитал следующую статью:

Calculating height of a binary tree

И один из постов дает следующие обозначения:

высота (узел) = макс (высота (node.L), высота (node.R)) + 1

Давайте предположим, что у меня есть следующий бинарное дерево:

 10 
/ \ 
    5 30 
/\ /\ 
4 8 28 42 

Должен ли я вычислить максимальное значение на левом узле (8) и узле max справа (42), а затем добавить 1? Я не совсем понимаю, как эта нотация работает, чтобы вычислить высоту дерева.

Answer 1

Я попытаюсь объяснить, как работает этот рекурсивный алгоритм:

height(10) = max(height(5), height(30)) + 1 

height(30) = max(height(28), height(42)) + 1 
height(42) = 1 (no children) 
height(28) = 1 (no children) 

height(5) = max(height(4), height(8)) + 1 
height(4) = 1 (no children) 
height(8) = 1 (no children) 

Так что, если вы хотите, чтобы вычислить height(10), вы должны расширить рекурсии вниз, и чем заменить результаты назад.

height(5) = max(1, 1) + 1 
height(30) = max(1, 1) + 1 
height(10) = max(2, 2) + 1 
height(10) = 3 

Answer 2

Высота дерева - это длина пути от корня до самого глубокого узла в дереве. Вот самый короткий алго сделать так

int height(Node root){ 
    if(root == null) 
     return 0; 
    return 1+max{height(root.left), height(root.right)}; 
} 

Answer 3

Вы знаете определение высоты узла? Я бы ответил на это как самое дальнее расстояние до достижимого листа (так что у всех листьев есть высота 0) ... теперь попробуйте найти высоту каждого узла снизу вверх. Это будет ваш алго ...

Answer 4

Узнать корневой узел, затем найдите самый длинный путь, который может покрыть u (означает максимальное количество узлов, которое вы можете покрыть в этом пути), , если вы получите этот путь, затем проверьте, сколько ветвей или краев вы покрыли, всего количество ветвей, которые вы накрыли, - это высота дерева

Answer 5

Наибольшее количество узлов, которое возможно в пути, начиная с первого узла (ROOT) до листового узла, называется высотой дерева. Формула для определения высоты дерева h = i (max) +1, где h - высота, I - максимальный уровень дерева

Answer 6

C энтузиастов, не стесняйтесь прочитать эту статью:

http://www.csegeek.com/csegeek/view/tutorials/algorithms/trees/tree_part3.php

Я снова aranged код C в PHP:

function getTreeHeight($node) { 
    if (!isset($node['left']) && !isset($node['right'])) { 
     return 0; 
    } 

    $leftHeight = getTreeHeight($node['left']); 
    $rightHeight = getTreeHeight($node['right']); 

    if ($leftHeight > $rightHeight) { 
     return $leftHeight + 1; 
    } else { 
     return $rightHeight + 1; 
    } 
} 

$array = array(
    'value' => 5, 
    'left' => array(
     'value' => 2, 
     'left' => array(
      'value' => 1, 
     ), 
     'right' => array(
      'value' => 4 
     ), 
    ), 
    'right' => array(
     'value' => 11, 
     'left' => array(
      'value' => 7 
     ), 
     'right' => array(
      'value' => 23, 
      'left' => array(
       'value' => 16 
      ), 
      'right' => array(
       'value' => 34 
      ), 
     ), 
    ) 
); 

echo getTreeHeight($array); //output 3 

Answer 7

#include<stdio.h> 
#include<stdlib.h> 


/* A binary tree node has data, pointer to left child 
    and a pointer to right child */ 
struct node 
{ 
    int data; 
    struct node* left; 
    struct node* right; 
}; 

/* Compute the "maxDepth" of a tree -- the number of 
    nodes along the longest path from the root node 
    down to the farthest leaf node.*/ 
int maxDepth(struct node* node) 
{ 
    if (node==NULL) 
     return 0; 
    else 
    { 
     /* compute the depth of each subtree */ 
     int lDepth = maxDepth(node->left); 
     int rDepth = maxDepth(node->right); 

     /* use the larger one */ 
     if (lDepth > rDepth) 
      return(lDepth+1); 
     else return(rDepth+1); 
    } 
} 

/* Helper function that allocates a new node with the 
    given data and NULL left and right pointers. */ 
struct node* newNode(int data) 
{ 
    struct node* node = (struct node*) 
           malloc(sizeof(struct node)); 
    node->data = data; 
    node->left = NULL; 
    node->right = NULL; 

    return(node); 
} 

int main() 
{ 
    struct node *root = newNode(1); 

    root->left = newNode(2); 
    root->right = newNode(3); 
    root->left->left = newNode(4); 
    root->left->right = newNode(5); 

    printf("Hight of tree is %d", maxDepth(root)); 

    getchar(); 
    return 0; 
} 

Answer 8

Повторные Вопрос

Несмотря на то, что я хорошо знаком с рекурсией, я немного удивлен всеми неправильными ответами относительно высоты двоичного дерева, поэтому я решил предложить правильное решение. Я сделал рытье, и на этот вопрос ответили правильно: https://stackoverflow.com/a/2597754/5567854.

Справочник

В соответствии с Wikipedia «дерево, состоящее только из корневого узла имеет высоту 0», а не 1, как состояние других ответов. Таким образом, на примере из вопроса:

 10 
/ \ 
    5 30 
/\ /\ 
4 8 28 42 

Если 10 был корневой узел, чтобы найти высоту этого дерева, то высота 2, а не 3.

Правильный код

Это решение является одним из многих возможных решений в языке C ...

size_t binary_tree_height(const binary_tree_t *tree) 
{ 
    size_t r, l, height = 0; 

    if (tree) 
    { 
     r = tree->right ? binary_tree_height(tree->right) + 1 : 0; 
     l = tree->left ? binary_tree_height(tree->left) + 1 : 0; 
     height += (r > l ? r : l); 
    } 
    return (height); 
}