Berechnen der Höhe eines Baumes

Question

Ich versuche Höhe eines Baumes zu berechnen. Ich bin doint mit dem Code unten geschrieben.

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

}

Es gibt mir corret Ergebnis. Aber in einige Beiträge (gegoogelt Seite) Es wurde vorgeschlagen, eine Nachordnungsdurchquerung und Verwendung zu tun diese Höhe Verfahren die Höhe zu berechnen. Einen bestimmten Grund?

Answer 1

Aber ist keine Nachordnungsdurchquerung genau das, was Sie tun? Unter der Annahme, links und rechts sind beide nicht leer ist, zunächst height(left) tun, dann height(right), und dann einige Verarbeitung in dem aktuellen Knoten. Das ist Nachordnungsdurchquerung nach mir.

Aber ich würde es so schreiben:

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

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

Edit:. Je nachdem, wie Sie Baumhöhe definieren, die Fallbasis (für einen leeren Baum) 0 sein soll oder -1

Answer 2

Der Code wird in den Bäumen scheitern, wenn mindestens einer der Knoten nur ein Kind hat:

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

Wenn der Baum zwei weitere Knoten (die Wurzel und entweder eine linke oder rechte Kind) auf der Root-Aufruf der Methode wird die erste Bedingung nicht erfüllen (mindestens eines der Teilbäume nicht leer ist), und es wird rekursiv rufen beide Kinder. Einer von ihnen ist null, aber immer noch wird es die Null-Pointer-Dereference die if auszuführen.

Eine richtige Lösung ist die, geschrieben von Hans hier. Auf jeden Fall müssen Sie entscheiden, was Ihre Methode Invarianten sind: Entweder Sie Anrufe ermöglichen, wo das Argument null ist und Sie damit umgehen, dass anmutig oder auch das Argument erfordern nicht-null und Garantie sein, dass Sie nicht die Methode mit Null-Zeiger nennen .

Der erste Fall ist sicherer, wenn Sie alle Eintrittspunkte nicht kontrollieren (die Methode ist öffentlich wie in Ihrem Code), da Sie nicht, dass die externe Code übergeben wird nicht Null-Zeiger garantieren können. Die zweite Lösung (die Signatur Bezug zu ändern, und es ein Element Methode der tree Klasse machen) könnte sauberer sein (oder nicht), wenn Sie alle Eintrittspunkte steuern können.

Answer 3

Die Höhe des Baumes nicht mit dem Traversal ändern. Es bleibt konstant. Es ist die Reihenfolge der Knoten, dass Veränderungen auf dem Traversal abhängig.

Answer 4

Definitionen von wikipedia .

  

Preorder (depth-first):

     

  
1. Besuchen Sie die Wurzel.
  
2. Traverse der linke Unterbaum.
  
3. Traverse der rechten Teilbaum.
  

     

Inorder (symmetrisch):

     

  
1. Traverse der linke Unterbaum.
  
2. Besuchen Sie die Wurzel.
  
3. Traverse der rechten Teilbaum.
  

     

Postorder:

     

  
1. Traverse der linke Unterbaum.
  
2. Traverse der rechten Teilbaum.
  
3. Besuchen Sie die Wurzel.
  

„Besuch“ in den Definitionen bedeutet „berechnen Höhe des Knotens“. Welche in Ihrem Fall ist entweder Null (links und rechts sind null) oder 1 + kombinierte Höhe von Kindern.

In der Implementierung, die Traversierfolgeliste keine Rolle spielt, wäre es die gleichen Ergebnisse liefern. Kippe wirklich Sie etwas mehr sagen, als dass es ohne einen Link zu Ihrer Quelle besagt, Postorder zu bevorzugen ist.

Answer 5

Hier ist die Antwort:

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