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

Question

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

#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);*/

}

Это дает мне правильный результат.Но в несколько сообщений(страница в Google). Было предложено выполнить обход 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));
}

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

Answer 2

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

// 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);
//...

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

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

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

Answer 3

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

Answer 4

Определения из Википедия.

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

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

Непорядковый (симметричный):

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

Постзаказ:

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

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

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

Answer 5

Вот ответ:

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