Baum

Hallo miteinander!

Ich habe eine Frage: Wenn man zwei Argumente hat: root_ und level_ , wie "baut" man dann mit diesen Informationen einen Baum?

void
epidemic::build_tree(person* root_, unsigned int level_)
{
//...
}

CStoll

Gegenfrage: Was soll diese Funktion inhaltlich bewirken? Es gibt zu viele Möglichkeiten, Bäume zu bauen, als daß wir mit diesen Informationen etwas ausrichten können.

Der Baum soll einfach bis zum definierten level "bevölkert" werden.
(mit allen Blattknoten).

CStoll

Und wie breit soll der Baum werden?

Ein Ansatz: erzeuge genug person-Objekte als Nachfolger des übergebenen root und wende auf jeden davon rekursiv build_tree(child,level_-1); auf.

EOutOfResources

LeoK schrieb:

Der Baum soll einfach bis zum definierten level "bevölkert" werden.
(mit allen Blattknoten).

Na, wiederhol das doch mit std::pow(2, _level) Blättern. Ich würde es rekursiv lösen, da das hier gut geht. Unter der Annahme, dass es sich hier um einen binären Baum handelt. Der Threadersteller ist sehr diskret.

EDIT: CStoll war schneller.

Das Problem ist eben, dass es sich um ein quad-tree (also ein Baum mit 4 Nachfolgern) handelt. Aber die Idee mit dem rekursiven Aufruf kann dann trotzdem angewendet werden, oder?

EOutOfResources

LeoK schrieb:

Das Problem ist eben, dass es sich um ein quad-tree (also ein Baum mit 4 Nachfolgern) handelt.

Dann gehst pflanzt du eben std::pow(4, level_) Blätter an.

LeoK schrieb:

Aber die Idee mit dem rekursiven Aufruf kann dann trotzdem angewendet werden, oder?

Natürlich, Rekursion ist eine allgemeine Technik.

EOutOfResources schrieb:

std::pow(2, _level)

Warum nicht 1 << _level ?

EOutOfResources schrieb:

std::pow(4, level_)

Warum nicht 4 << level_ ?

Warum nicht _6 << level ?

Warum nicht 8_ << level ?

CStoll

hedontgetit schrieb:

EOutOfResources schrieb:

std::pow(2, _level)

Warum nicht 1 << _level ?

EOutOfResources schrieb:

std::pow(4, level_)

Warum nicht 4 << level_ ?

Warum nicht _6 << level ?

Warum nicht 8_ << level ?

Bei den Zweierpotenzen mag die Äquivalenz noch gültig sein, aber allgemeine Potenzierung funktioniert nicht so einfach per Bitshift (davon abgesehen mußt du diese Anzahl gar nicht explizit ausrechnen - jeder Knoten der vorletzten Ebene legt 4 (oder n) Blätter an, die höheren Knoten entsprechend jeweils 4 innere Knoten).

@CStoll: natürlich geht das so nicht, aber das war gar nicht meine Aussage.

Ich habe nur versucht, mich auf das niedere Niveau von EOutOfLesources herabzugeben um damit zu zeigen, wie wenig er vom Problem versteht und wie unnötig seine Berechnungen sind.

Man sollte es nämlich so machen, wie du mit deinem zweiten Post. Der ganze Rest ist zum vergessen.

EOutOfResources

hedontgetit schrieb:

wie unnötig seine Berechnungen sind.

Die waren zur Veranschaulichung. Hätte ich 2^foo geschrieben, hätte man an den XOR-Operator gedacht.

Niemand zwingt dich, nicht das dafür gedachte Hoch-Tag zu verwenden, etwas wie 2^foo (BB-Code: 2[h] foo[/ h] ) wäre unmissverständlich.
Bei noch korrekt ausgeschriebenem std::pow(2, foo) denkt man doch sofort an C-like-C++-Code.

EOutOfResources

hedontgetit schrieb:

Niemand zwingt dich, nicht das dafür gedachte Hoch-Tag zu verwenden

Stimmt. Werde ich mir für das nächste Mal merken.

hedontgetit schrieb:

C-like-C++-Code.

Wie potenzierst du denn?

Ich bin etwas verwirrt.
Also kann ich's nicht einfach so machen?

build_tree(std::pow(4, level_), level_-1);

CStoll

Schon weil du bei dem Aufruf gar nicht angeben kannst, wo die Wurzel dieses Teilbaumes liegt. Wie ich schon sagte, die Lösung liegt in der Rekursion - du legst vier neue Objekte an, hängst sie als Nachfolger in dein root-Objekt und lässt dann die build_tree()-Funktion auf jede davon los.

@EOutOfResources und hedontgetit: Habt ihr nun geklärt, wie man Potenzen schreiben sollte

Wie meinst du "hängst sie als Nachfolger in dein root-Objekt " konkret?
Also ich weiss, was du meinst. Allerdings bring ich das codemässig nicht hin.

CStoll

Du müsstest irgendwo in der person-Klasse/Struct einige Elemente haben, die die Kinder darstellen (da du uns die Definition nicht genannt hast, kann ich nur raten). Mit "einhängen" meinte ich, die neu erzeugten Objekte dort unterzubringen.

Hmm..ich kann "nur" neue Personen machen, ob die dann "children" sind, weiss man nicht...

#ifndef __PERSON__
#define __PERSON__

// Task1
#include "common.hpp"
#include "../../../shared/array.hpp"
// STL
#include <vector>

class person 
{

    public:
        /**
        * @brief construct a new person with the specified id
        * @param  id_   id of the new person
        */
        person(unsigned int id_);

        /**
        * @brief getter of the id of the person
        * @return int   return the id of the person
        */
        int
        get_id(void) const;

        /**
        * @brief retrieve the n-th children of the current node
        *        (range from 0 to 3).
        * @param    index_    index of the child to access
        * @return   person*   the actual child
        */
        person*
        get_person_at_risk(unsigned int index_);

        /**
        * @brief add a new person at the defined position.
        * @param index_           (range from 0 to 3)
        * @param new_person_      the new person to add
        */
        void
        set_person_at_risk(person* new_person_, unsigned int index_);

        /**
        * @brief checks if the node is infected or not
        * @return bool    true if the node is infected, false otherwise
        */
        bool
        is_infected(void) const;

        /**
        * @brief set the infection of the person
        * @param status_    the new infection status
        */
        void
        set_infected(bool status_);

        /**
        * @brief print the node's information
        */
        void
        print(void);

    private:
        /* Children nodes */
        array<person*, MAX_CHILDREN> _people_at_risk;

        /* ID of the person */
        const unsigned int _id;

        /* Infection status */
        bool _infected;
};

#endif  // __PERSON__

CStoll

/** 
        * @brief add a new person at the defined position. 
        * @param index_           (range from 0 to 3) 
        * @param new_person_      the new person to add 
        */ 
        void 
        set_person_at_risk(person* new_person_, unsigned int index_);

das klingt doch genau nach der Methode, die du dafür benötigst

Also meinst du das in der Art (noch nicht vollständig):

person* p1;
	p1->set_person_at_risk(p1, 0);
	person* p2;
	p2->set_person_at_risk(p2, 1);

	build_tree(p1,level_);

..ich bin mir bzgl. den Argumenten nicht sicher..

CStoll

Der Ansatz ist zu erkennen, allerdings zeigen deine Zeiger noch ins Nirvana. Du solltest auch echte Objekte erzeugen (z.B. mit new).

PS: Und ich würde eine Schleife verwenden - das erspart Schreibarbeit