Разлік вышыні бінарнага дрэва

Мне патрэбна дапамога з тэорыяй аб вылічэнні вышыні бінарнага дрэва, як правіла, у пазначэннях.

Я прачытаў наступны артыкул:

Разлік вышыні бінарнага дрэва

І адзін з пастоў даюць наступныя абазначэння:

<�Р> вышыня (вузел) = макс (вышыня (node.L), вышыня (node.R)) + 1 </р>

Давайце выкажам здагадку, што ў мяне ёсць наступнае бінарнае дрэва:

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

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

9
Гэта рэкурсіўны алгарытм. <�Код> вышыня называе сябе, пакуль яна не дойдзе да ніжняй частцы кожнай галіны дрэва.
дададзена аўтар Robert Harvey, крыніца
@ChrisChambers Дзякуй за адказ. Такім чынам, мы памнажаючы node.L па node.R Што б вышыня бягучага дрэва зададзенага, у якасці прыкладу?
дададзена аўтар Phorce, крыніца
@Phorce: Кожны дзіця з кораня дрэва, таксама дрэва з коранем у паказаным даччыным вузле. Кожны з іх дзяцей, з'яўляецца дрэвам, а таксама. <�Я> Кожны вузел у дрэве </я> само дрэва. Каб знайсці вышыню дрэва, вы проста знайсці вышыню кожнага з даччыных дрэў, вазьміце самы вялікі з гэтых лікаў, і дадаць 1 злічыць сябе.
дададзена аўтар cHao, крыніца
Я хацеў бы дадаць, што, калі ён патрапіць на дно, ён правярае, калі вышыня больш, чым існуючая якая захоўваецца вышыня, і, калі так, то абнаўляе яго.
дададзена аўтар Chris Chambers, крыніца
Я б рэкамендаваў, што вышыня дрэва усталёўваецца як ўласцівасць вашага класа дрэва кожны раз, калі вы ўстаўляеце ў яго. Гэта значыць, кожны раз, калі вы ўстаўляеце, праверыць і паглядзець, калі вы пайшлі далей ўніз па дрэве, і, калі так, то абнавіць вышыню.
дададзена аўтар Chris Chambers, крыніца
@Phorce: Мы нічога не размнажаецца. node.L ставіцца да левых даччынаму вузлу. Вышыня бягучага дрэва будзе 2
дададзена аўтар cvraman, крыніца

8 адказы

Я паспрабую растлумачыць, як працуе гэты рэкурсіўны алгарытм:

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)

Так што калі вы хочаце, каб вылічыць вышыня (10) , вы павінны пашырыць рэкурсіі ўніз, і чым замяшчаюць вынікаў у зваротным кірунку.

height(5)  = max(1, 1) + 1
height(30) = max(1, 1) + 1
height(10) = max(2, 2) + 1
height(10) = 3
20
дададзена
Гэтае пытанне дапамог шмат з маёй лабараторыі ў выкананні хатніх заданняў ... Якая мэта разліку Мах левай і правай вышыні?
дададзена аўтар Riptyde4, крыніца
@ Riptyde4 Дрэва вы бачыце вышэй, мае такую ​​ж вышыню, альбо ісці налева або направа. Але думаць пра той выпадак, калі, напрыклад. У зыходным прыкладзе прымацаваць нумар 6 пад нумарам 28. Менавіта таму мы павінны атрымаць максімум.
дададзена аўтар jasxir, крыніца
Гэты адказ з'яўляецца добрым тлумачэннем рэкурсіі, але гэта няправільна вылічае вышыню двайковага дрэва. Канец рэкурсіі (калі ўваходны вузел = NULL ) павінен вяртаць -1 не 0 . Я падаў правільны адказ ніжэй . Для даведкі, гэта паўтаральны пытанне, а другі перапаўнення стэка пытанне таксама мае правільны адказ, тут
дададзена аўтар David John Coleman II, крыніца

Вышыня дрэва даўжыня шляху ад кораня да самага глыбокага вузла ў дрэве. Вось самы кароткі Алга зрабіць так

int height(Node root){
   if(root == null )
       return 0;
   return 1+max{height(root.left), height(root.right)};
}
19
дададзена
@kimbaudi Існуе базавая ўмова, каб праверыць, калі які-небудзь з суб дзіцяці прысутнічае ці не. Я лічу, што гэта будзе працаваць для ўсіх бінарных дрэў. Тым не менш, я хацеў бы мець лічыльнік тэст, калі такія маюцца.
дададзена аўтар roger_that, крыніца
@kimbaudi: Па вызначэнні, «Вышыня вызначаецца як лік вузлоў у самім доўгім шляху ад каранёвага вузла да вузла ліста». Так што вы бачыце.
дададзена аўтар roger_that, крыніца
На жаль @roger_that. Ваш алгарытм апрацоўвае выпадак, калі або адзін з даччыных вузлоў у бінарным дрэве з'яўляецца нулявы. Аднак, разлік вышыні ня здаецца правільным. Гледзячы на ​​OP бінарнае дрэва, вышыня яго роўная 2. Але ваш алгарытм вылічае яго як 3. Я ўпэўнены, што вышыня ў каранёвым вузле 0 (не 1).
дададзена аўтар kimbaudi, крыніца
Я не згодны. Вышыня яго колькасць вузлоў ад каранёвага вузла да вузла ліста АКРАМЯ самага каранёвага вузла. Нават прыклад вікіпедыя бінарнага дрэва: en.wikipedia.org/wiki/Binary_tree ня вылічыць вышыню такім чынам.
дададзена аўтар kimbaudi, крыніца

Ці ведаюць у вызначэння вышыні вузла? Я б адказаць на яго, як далёкую адлегласць да дасяжнасці ліста (так што ўсе лісты маюць вышыню 0) ... теперь спрабую знайсці вышыню кожнага вузла знізу top..that б вашыя Алга ..

2
дададзена

C enthousiasts, не саромейцеся, каб мець чытання ў гэтым артыкуле:

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
1
дададзена
Чаму ўніз галасаваць? Жыццё так несправядліва!
дададзена аўтар Julian, крыніца

Высветліце каранёвай вузел, а затым паглядзець на самы доўгі шлях, і можа пакрыць (азначае максімальную колькасць вузлоў вы можаце пакрыць ў гэтым шляху), калі і атрымаць гэты шлях, а затым праверыць, колькі галін ці краю вы пакрылі, агульная колькасць філіялаў вы пакрылі вышыня дрэва

1
дададзена

Найбольшая колькасць вузлоў, якія можна такім чынам, пачынаючы з першага вузла (ROOT) да вузла ліста называюць вышыню дрэва. Формула для знаходжання вышыні дрэва Н = I (макс) + 1, дзе Н ўяўляе сабой вышыню, і я гэта ўзровень макс дрэва

1
дададзена
#include
#include


/* 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;
}
0
дададзена

<�Моцны> Паўторныя Пытанне

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

<�Моцны> Спасылка

Згодна Вікіпедыі , «Дрэва, якое складаецца толькі з каранёвага вузла мае вышыню 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);
}
0
дададзена