Tree

Hallo miteinander

Ich wollte fragen, wie man in C++ die size wie auch die height eines tree's herauskriegt, wenn man allerdings keine Argumente in den Methoden hat. Also:

int tree::size() const

bzw.

int tree::height() const

Das hpp-file sieht so aus:

#ifndef TREE_HPP
#define TREE_HPP

#include "tree_node.hpp"

class tree
{
public:
    tree();
    ~tree();

	int size() const;
	int height() const;

private:
    tree_node* _root;

};

#endif

Liebe Grüsse,
Max

Eisflamme

Man müsste auch tree_node kennen, wie sieht das aus?

Wenn man die Höhe nicht mitspeichert und sie daher algorithmisch herausfinden muss, muss man eben alle Zweige durchgehen (rekursiv oder iterativ) und sich die größte Tiefe eben merken. Währenddessen kann man die Elemente natürlich auch mitzählen.

Angenommen, tree_node hat getLeft() und getRight(), wobei der Rückgabewert ein weiterer Knoten oder NULL ist, falls nicht gesetzt. Wie SeppJ im nächsten Posting sagt, kommt es drauf an. Meine Lösung wäre also für einen nicht-balancierten Binärbaum, der sich nichts gemerkt hat. Für andere Binärbäume könnte mein Algorithmus suboptimal sein, da seine Laufzeit O(n) ist.

class tree
{
private:
    int size_;
    int height_;
    tree_node* root_; // _ als Präfix könnte Probleme mit Compilern geben, davon ist also abzuraten!
    void recalculateSizeAndHeight(tree_node* currentNode, int oldHeight);

public:
    tree() : size_(0), height_(0) {}

    int getSize() const {return size_;}
    int getHeight() const {return height_;}

    void recalculateSizeAndHeight();
}; // Edit: Semikolon vergessen, peinlich; haut mich nicht

void recalculateSizeAndHeight()
{
    size_ = 0;
    height_ = 0;
    if(root_ != NULL)
        recalculateSizeAndHeight(root_, height_);
}

void recalculateSizeAndHeight(tree_node* currentNode, int oldHeight)
{
    ++size_;

    if(currentNode->getLeft() == NULL && currentNode->getRight() == NULL)
    {
        if(height_ < oldHeight_ + 1)
            height_ = oldHeight_ + 1;
    }
    else
    {
        if(currentNode->getLeft() != NULL)
            recalculateSizeAndHeight(currentNode->getLeft(), oldHeight + 1);
        if(currentNode->getRight() != NULL)
            recalculateSizeAndHeight(currentNode->getRight(), oldHeight + 1);
    }    
}

SeppJ

Das kommt 100% auf die Implementierung deines Baumes an. Im besten Fall hat er sich diese Dinge gemerkt (oder sie sind berechenbar, weil es ein bestimmter Baum ist, z.B. ein perfekt balancierter Baum) oder im schlimmsten Fall musst du eben durchzählen. Wie sollen wir das wissen?

gemerkt ... oder rekursiv:

#include <algorithm> // std::max

// --   tree_node.hpp
struct tree_node
{
    int value_;
    tree_node* left_;
    tree_node* right_;
};

class tree
{
public:
    // ....
    int size() const;
    int height() const;

private:
    tree_node* _root;
}; 

int tree_size( const tree_node* nd )
{
    if( nd )
        return tree_size( nd->left_ ) + tree_size( nd->right_ ) + 1;
    return 0;
}
int tree::size() const
{
    return tree_size( _root );
}

int tree_height( const tree_node* nd )
{
    if( nd )
        return std::max( tree_height( nd->left_ ), tree_height( nd->right_ ) ) + 1;
    return 0;
}
int tree::height() const
{
    return tree_height( _root );
}

Wow Leute!
Ganz grosse Klasse!
..eigentlich konnte ich den Algorithmus scho raus lesen (hatte ähnliches im Sinn), aber trotzdem noch die tree_node-Klasse:

#include "tree_node.hpp"

tree_node::tree_node(const std::string& content_) : _content(content_)
{}

tree_node::~tree_node()
{
    for(int i = 0; i < _children.size(); ++i)
    {
        delete _children.at(i);
    }
}

bool tree_node::is_internal() const
{
    /* Muss ich noch machen ;) */

}

bool tree_node::is_external() const
{
     /* Muss ich noch machen ;) */

}

void tree_node::add(tree_node* node_)
{
    _children.push_back(node_);
}

int tree_node::size() const
{
     /* Muss ich noch machen ;) */

}

int tree_node::height() const
{
     /* Muss ich noch machen ;) */

}

Trotzdem aber die Frage:
Ihr habt nun jeweils Argumente in den Methoden (-Klammern) verwendet. Die sind bei mir nicht vorgesehen. (heisst aber nicht, dass man es nicht ohne machen darf ) Trotzdem aber die Frage: Ist es ohne Argumente nicht auch möglich?

Das hpp-file zu tree_node sieht so aus:

#ifndef TREE_NODE_HPP
#define TREE_NODE_HPP

#include <string>
#include <vector>

class tree_node
{
public:
	tree_node(const std::string& content);
	~tree_node();

    void add(tree_node*);

	bool is_internal() const;
	bool is_external() const;

    int size() const;
    int height() const;

private:
	std::string _content;

    std::vector<tree_node*> _children;
};

#endif

Eisflamme

Nein, die Methoden, die der Benutzer aufruft, haben keine Argumente. Weder bei Werner noch bei mir. Wenn wir uns die Mühe machen Dir Algorithmen zu schreiben, solltest Du Dir zumindest die Mühe machen, die in aller Ruhe zu lesen und zu verstehen, findest Du nicht?

Hast Recht!
...genau das mach ich jetzt.

Ach war ich wieder voreilig.
Ihr seid super - es steht ja alles da, wonach ich suchte

Ich habe allerdings noch eine inhaltliche Frage:
Es wurde

struct tree_node //...

benutzt. Was macht das genau, bzw. wozu steht das "struct"?

Eisflamme

Werner hat einfach nur eine Definition für tree_node vorausgesetzt, weil Du Deine noch nicht geposted hattest. Da Du deine jetzt ja gezeigt hast, musste das halt entsprechend dafür umbauen.

Außerdem hast Du keinen Binärbaum, sodass Du sowieso etwas Transferleistung bringen musst.

Okey, vielen Dank!

Jeps, hab's soweit gemacht. Allerdings hab ich noch zwei Fragen:

1.) Wenn man sowas hat:
if( nd )
return //...
dann prüft man einfach, ob "nd" vorhanden und korrekt gewählt ist, oder?

2.)Wie überprüft man, ob es sich um einen external_node (Blattknoten) handelt? ..also wie sieht die Idee dazu aus?

CStoll

MaxC++ schrieb:

1.) Wenn man sowas hat:
if( nd )
return //...
dann prüft man einfach, ob "nd" vorhanden und korrekt gewählt ist, oder?

Das ist im Prinzip äquivalent zu if(nd!=NULL)... - und wenn du unbenutzte Zeiger mit NULL vorbelegst, kannst du auf diese Weise prüfen, ob er belegt ist. Mit deinem vector<> kannst du dir die Überprüfung sparen (s.u.)

2.)Wie überprüft man, ob es sich um einen external_node (Blattknoten) handelt? ..also wie sieht die Idee dazu aus?

Wie ist denn der Begriff "Blatt" definiert - ein Knoten, der keine Nachfolger hat. Bei deinem Design ist das ganz einfach festzustellen, da alle Nachfolgerknoten in deinem vector<tree_node*> _children; untergrabracht sind.

Ahh..und ich dacht' schon, was die "_children" konkret sein sollen.

Eine Schlussfrage habe ich noch: Mein Compiler hat bei der tree_height-Methode etwas gejammert. Links- und Rechtsknoten gibt es bei mir ja eigentlich nicht - wie soll ich die Methode denn ohne li- re-Knoten implementieren?

CStoll

Auch über die children-Liste - du bestimmst die Höhe jedes Unterbaums (die einzelnen Kinder können als Wurzeln eines kleineren Unterbaums betrachtet werden), nimmst davon das Maximum und addierst noch 1 (für die Wurzel selber).

Okey, also ich hab mal sowas gemacht:

int tree::height() const
{
	return std::max(_children.size()) + 1;    
}

..was aber nicht stimmen kann, da: _children ja eigentlich ein private-Argument ist und ich also nicht so direkt darauf zugreifen kann..

CStoll

Nein, so klappt da nicht, du willst schließlich die maximale Höhe der Kinder haben und nicht die Größe der Kinder-Liste. Du mußt schon in einer Schleife über diese Liste laufen:

int kind_hoehe=0;
for(int i=0;i<children.size();++i)
  kind_hoehe=std::max(kind_hoehe,children[i]->height();
return kind_hoehe+1;

(und als nächstes lernen wir dann, wie du das selbe mit den STL-Algorithmen hinbekommst :D)

Aber Frage: _children ist in tree_node.hpp private, d.h. dass man ja nicht direkt darauf zugreifen kann..
(oder?)

STL-Algo? ..etwas einfacheres?

CStoll

MaxC++ schrieb:

Aber Frage: _children ist in tree_node.hpp private, d.h. dass man ja nicht direkt darauf zugreifen kann..
(oder?)

Die offensichtlichste Lsung ist dann wohl, diesen Code dorthin zu packen, wo du darauf zugreifen kannst - idealerweise wäre das die Methode tree_node::height().

STL-Algo? ..etwas einfacheres?

Nicht unbedingt einfacher, aber mitunter eleganter. Wenn du mehr darüber wissen willst, im Magazin gibt es noch einen alten Artikel von mir über die STL.

Okey, so hats eigentlich funktioniert.
Nur: Kann ich die Methode in tree.cpp nicht mit
"tree_node::height()" aufrufen?
..ich frage so dumm, weil mein Compiler da leider anderer Meinung ist..

Gerne, da werd' ich nachher einen Blick rein werfen

CStoll

Wenn du die Methode aufrufst, mußt du ihr auch sagen, für welches Objekt du sie anwenden willst - die Antwort heißt _root-height().

Ahh shit - das hab' ich eben auch gerade raus bekommen.
..darauf hätt' ich eigentlich sofort kommen sollen..

However, jetzt funktioniert alles wie gwünscht
Vielen herzlichen Dank für die Unterstützung euch allen!