Рассчитать высоту дерева

Question

Я пытаюсь вычислить высоту дерева. Я doint с кодом, написанным ниже.

#include<iostream.h> 

struct tree 
{ 
    int data; 
    struct tree * left; 
    struct tree * right; 
}; 

typedef struct tree tree; 

class Tree 
{ 
private: 
    int n; 
    int data; 
    int l,r; 
public: 
    tree * Root; 
    Tree(int x) 
    { 
     n=x; 
     l=0; 
     r=0; 
     Root=NULL; 
    } 
    void create(); 
    int height(tree * Height); 

}; 

void Tree::create() 
{ 
    //Creting the tree structure 
} 

int Tree::height(tree * Height) 
{ 
    if(Height->left==NULL && Height->right==NULL) 
    {return 0; 
    } 
    else 
    { 
     l=height(Height->left); 
     r=height(Height->right); 

     if (l>r) 
     {l=l+1; 
     return l; 
     } 
     else 
     { 
      r=r+1; 
      return r; 
     } 
    } 
} 

int main() 
{ 
    Tree A(10);//Initializing 10 node Tree object 
    A.create();//Creating a 10 node tree 

    cout<<"The height of tree"<<A.height(A.Root);*/ 

} 

Это дает мне результат коррекции. Но в some posts (googled page) Было предложено выполнить обход Postorder и использовать этот метод высоты для вычисления высоты. Любая конкретная причина?

Answer 1

Но ведь вы не в постобработке, а что именно вы делаете? Предполагая, что влево и вправо оба значения не равны нулю, вы сначала делаете height(left), затем height(right), а затем обрабатываете в текущем узле. Это постоперационный обход по мне.

Но я бы написал так:

int Tree::height(tree *node) { 
    if (!node) return -1; 

    return 1 + max(height(node->left), height(node->right)); 
} 

Edit: в зависимости от того, как вы определяете высоту дерева, базовый вариант (для пустого дерева) должен быть 0 или -1.

Answer 2

Высота дерева не изменяется при обходе. Он остается постоянным. Это последовательность узлов, которые изменяются в зависимости от обхода.

Answer 3

Определения от wikipedia.

Предзаказ (глубина первая):

1. Посещение корень.
2. Перемещение левого поддерева.
3. Пройдите вправо поддерева.

Симметричного (симметричный):

1. траверс левого поддерева.
2. Посетите корень.
3. Пройдите вправо поддерева.

Postorder:

1. Traverse левого поддерева.
2. Пройдите вправо поддерева.
3. Посетите корень.

«Посещение» в определениях означает «рассчитать высоту узла». Который в вашем случае равен нулю (как слева, так и справа - null) или 1 + комбинированная высота детей.

В вашей реализации порядок обхода не имеет значения, он даст те же результаты. Не могу сказать, что вам больше ничего, кроме ссылки на ваш источник, указывающий, что заказчик предпочитает.

Answer 4

код потерпит неудачу в деревьях, где по крайней мере один из узлов имеет только одного ребенка:

// code snippet (space condensed for brevity) 
int Tree::height(tree * Height) { 
    if(Height->left==NULL && Height->right==NULL) { return 0; } 
    else { 
     l=height(Height->left); 
     r=height(Height->right); 
//... 

Если дерево имеет два узла (корень и либо левую или правую ребенка) вызовом метода корень не выполнит первое условие (по крайней мере одно из поддеревьев не пустое), и оно будет вызывать рекурсивно для обоих детей. Один из них является нулевым, но все же он будет разыменовывать нулевой указатель для выполнения if.

Правильное решение - это сообщение, отправленное Hans. Во всяком случае вам нужно выбрать, каковы ваши инварианты метода: либо вы разрешаете вызовы, где аргумент равен null, и вы обрабатываете это изящно, либо вам нужно, чтобы аргумент был не нулевым и гарантировал, что вы не вызываете метод с нулевыми указателями ,

Первый случай более безопасен, если вы не контролируете все точки входа (этот метод является общедоступным, как в вашем коде), поскольку вы не можете гарантировать, что внешний код не будет пропускать нулевые указатели. Второе решение (изменение сигнатуры на ссылку и создание ее метода-члена класса tree) может быть более чистым (или нет), если вы можете контролировать все точки входа.

Answer 5

Вот ответ:

int Help :: heightTree (node *nodeptr) 
{ 
    if (!nodeptr) 
     return 0; 
    else 
    { 
     return 1 + max (heightTree (nodeptr->left), heightTree (nodeptr->right)); 
    } 
}