binärer baum für komplexe gleichungen
-
hallo,
mir wurde folgende aufgabe gestellt:
entwerfen sie ein programm, welches eine mathematische gleichung entgegen nimmt
und diese, mittels eines binären baumes, auswertet.folgende klasse hab ich schon zusammen gebastelt:
#ifndef _BINTREE_ #define _BINTREE_ #include <list> template<class _Ty> class bintree { public: bintree(); virtual ~bintree(); public: typedef iterator const_iterator; public: private: void insert(const _TItem &_Ti); // neues item hinzufügen void erase(_TItem *_Ti); // item entfernen private: protected: class _TItem { protected: std::list<_TItem> _Pleg; // liste mit zeiger zu den weiteren zweigen public: _TItem *_LegHigher; // zeigt eine ebene höher _Ty _Container; // enthält datenstruktur // friend class bintree; // public: _TItem(): _LegHigher(NULL){} // konstruktor }; class iterator { public: deeper(); // iteriert eine ebene tiefer in abhängigkeit von _Pleg higher(); // iteriert eine ebene höher private: protected: // _TItem _Ty; public: iterator(_TItem _T = _TI): _Ty(_T){} // konstruktor virtual ~iterator(); // destruktor }; protected: _TItem _root; // wurzel "item" }; #endifnun bleibe ich an einem gedanken hängen! nämlich "wie baue ich den baum auf?"
es gibt mehrere möglichkeiten, und ich wollte mich für die etwas kompliziertere lösung entscheiden, nämlich einen baum zu entwerfen, von dem mehrere knoten ausgehen.[root] ... / | \ / | \ / | \ ____ ____ ____ | | | | | | | | | | | | |____| |____| |____| / | \ / | \ / | \ . . . (usw)mehrere zweige bzw knoten sollen möglich sein.
nun der gleichungsparser, soll entscheiden können welchen zweig er gehen muss um einen bestimmten term sinnvoll zu platzieren.
und genau diese entscheidung gibt mir zu denken.ausserdem wie iteriere ich sinnvoll(schnell, einfach) durch den baum bzw durch einen bestimmten zweig?
das iterieren hab ich mir folgendermaßen vorgestellt.
ich erstelle mir eine iterator instanz, und entscheide zunächst welchen zweig ich hinabsteigen möchte. hab ich mich entschieden, steig ich hinab und bekomme einen zeiger auf den container der datenstruktur. nun kann ich auf die variablen der datenstruktur zugreifen und die werte dieser variablen auswerten und in abhängigkeit der werte weiter iterieren. diese methode scheint mir zu komplex für eine konkrete klasse zu sein. ausserdem sollte man aufrufe ausserhalb der klasse möglichst einfach gestalten, nach dem KISS verfahren eben :-).mfg xerxes
-
Wenn in der angabe steht du sollst einen binär baum verwenden dann würde ich einen verwenden
maximale verzeigungsgrad bei einem binären baum ist 2!mfg
-
wie spjoe schon sagte ein "binaer Baum" hat maximalen Verzweigungsgrad 2, d.h. jeder Knoten kann maximal 2 Nachfolger haben
in deinem Fall brauchst du die list<> _Pleg nicht sondern 2 Zeiger auf den linken und rechten Nachfolger wuerden genuegen
weiters wuerde ich den Zeiger _LegHigher auf "Father" oder "Parent" umbennen da dies ein gaengiger Ausdruck ist und auch in den protected Bereich geben
xerxes schrieb:
protected: class _TItem { protected: std::list<_TItem> _Pleg; // liste mit zeiger zu den weiteren zweigen public: _TItem *_LegHigher; // zeigt eine ebene höher }; tem _T = _TI): _Ty(_T){} // konstruktor virtual ~iterator(); // destruktor };
-
hi,
ok, der maximale verzweigungsgrad in meinem baum soll 2 sein.
trotzallem habe ich mich an folgenden denkansätzen festgefahren.es geht um das iterieren im baum.
die iteration durch den baum macht mir probleme und wenn ich keine gescheite lösung gefunden habe, zieht das nachteile beim hinzufügen und löschen einzelner element mit sich.nun habe ich mir folgendes überlegt.
ich nummeriere jede ebene von knoten und blättern von links nach rechts durch.
wenn nun ein insert(knotennummer/blattnummer, links oder rechts) aufrufe, kann insert den weg zu diesem knoten bzw blatt berechnen. dies tue ich in dem ich die angebene nummer in folgende formeln einsetze:
- ist der wert der nummer gerade ((nummer - 2) / 2)
- ist der wert der nummer ungerade ((nummer - 1) / 2)diese rechnung führe ich solange durch bis der wert 0 auftritt.
so bekomme ich nach und nach jede knoten bzw blatt nummer heraus.
diese errechneten werte speicher ich in umgekehrter reihenfolge in einem stack.
nun kann ich den stack abarbeiten und den weg zurückverfolgen und bekomme die adresse des knotens / blattes.
(bevor insert mit der berechnung beginnt, überprüft es zuerst ob es einen knoten bzw blatt mit diesem (nennen wir es) _NodeIndex schon gibt)diese _NodeIndex angabe scheint mir recht effizient zu sein, jedoch nicht mit der handhabung sprich mit der orientierung für den, der diese klasse benutzt.
dh. bei den ganzen zahlen die nach und nach möglich sind, herrscht bald ein chaos. dieses chaos wollte ich mit einem iterator lösen. der iterator merkt sich den _NodeIndex des zuletzt hinzugefügten elements) und stellt methoden bereit um eine knoten ebene höher zu springen etc. pp.
das scheint mir ein wenig zu komplex zu sein, da darunter nämlich die benutzerfreundlichkeit leidet.einziger vorteil:
wenn die orientierung im baum übersichtlich ist, dann kann ich im baum umherspring wie ich möchte.zur nummering des baums:
_____ |__0__| / \ / \ / \ ____ ____ |__1_| |__2_| / \ | \ / \ | \ ____ ____ | \ |__3_| |__4_| ____ ____ |__5_| |__6_| usw.könntet ihr meine methode beurteilen?
sollte ich meinen lösungs ansatz schnell wieder vergessen?gruß xerxes
-
kannst du mir mal kurz die Aufgabenstellung posten, kann mir das sonst nur schwer vorstellen
und kannst mir bitte erklaeren warum du folgendes machst
xerxes schrieb:
wenn nun ein insert(knotennummer/blattnummer, links oder rechts) aufrufe, kann insert den weg zu diesem knoten bzw blatt berechnen. dies tue ich in dem ich die angebene nummer in folgende formeln einsetze:
- ist der wert der nummer gerade ((nummer - 2) / 2)
- ist der wert der nummer ungerade ((nummer - 1) / 2)diese rechnung führe ich solange durch bis der wert 0 auftritt.
so bekomme ich nach und nach jede knoten bzw blatt nummer heraus.
-
die aufgabenstellung war:
entwerfen sie ein programm, welches eine mathematische gleichung entgegen nimmt
und diese, mittels eines binären baumes, auswertet.leo aka qsch schrieb:
kannst du mir mal kurz die Aufgabenstellung posten, kann mir das sonst nur schwer vorstellen
und kannst mir bitte erklaeren warum du folgendes machst
xerxes schrieb:
wenn nun ein insert(knotennummer/blattnummer, links oder rechts) aufrufe, kann insert den weg zu diesem knoten bzw blatt berechnen. dies tue ich in dem ich die angebene nummer in folgende formeln einsetze:
- ist der wert der nummer gerade ((nummer - 2) / 2)
- ist der wert der nummer ungerade ((nummer - 1) / 2)diese rechnung führe ich solange durch bis der wert 0 auftritt.
so bekomme ich nach und nach jede knoten bzw blatt nummer heraus.die mache ich um den weg weg zu diesem element zu errechnen.
folgende klasse die ich gerade erstelle kann dir deine frage eventuell beantworten:#ifndef _BINTREE_ #define _BINTREE #include <cstddef> #include <functional> #include <iterator> #include <memory> #include <stdexcept> #include <xutility> #include <vector> #include <stack> template<class _Ty, class _A = allocator<_Ty> > class bintree { protected: struct _Item; friend struct _Item; typedef _POINTER_X(_Item, _A) _Itemptr; struct _Item{ _Itemptr _Left, _Right, _Parent; unsigned int _ItemIndex; bool _IfNode; _Ty _Value; _Item() : _ItemIndex(0), _IfNode(false) {} }; struct _Acc; friend struct _Acc; struct _Acc { typedef _REFERENCE_X(_Itemptr, _A) _Itempref; typedef _A::reference _Vref; static _Itempref _Left(_Itemptr _P) {return ((_Itempref)(*_P)._Left); } static _Itempref _Right(_Itemptr _P) {return ((_Nodepref)(*_P)._Right); } static _Itempref _Parent(_Itemptr _P) {return ((_Nodepref)(*_P)._Parent); } static _Vref _Value(_Itemptr _P) {return ((_Vref)(*_P)._Value); } static _Vref _Index(_Itemptr _P) {return ((_Vref)(*_P)._ItemIndex); } static _Vref _IfNode(_Itemptr _P) {return ((_Vref)(*_P)._IfNode); } }; typedef unsigned int _UInt; typedef /*stack<_UInt>*/list<_UInt> _Way; typedef NULL _Nil; public: class const_iterator; friend class const_iterator; class const_iterator { public: const_iterator() {} /* const_iterator(unsigned int _I) : _ItemIndex(_I) { } */ protected: //stack<_UInt> _WayStack; _UInt _ItemIndex; }; bool push(const _Ty &_X, const_iterator _I, _UInt _Way) { if((_Itemptr _Ptr = calculate_way(/*wert*/)) == _NULL()) return false; if(_Way == left()) return insert_left(_X, _Ptr); else if(_Way == right()) return insert_right(_X, _Ptr); } bool insert_left(const _Ty &_Xr, _Itemptr _Ptr) { _Itemptr _Tmp = _ByItem(); _Acc::_Left(_Ptr) = _Tmp; _Acc::_Parent(_Tmp) = _Ptr; _Acc::_IfNode(_Ptr) = true; _Acc::_Index(_Tmp) = _IndexGen(); return true; } bool insert_right(const _Ty &_Xr, _Itemptr _Ptr) { _Itemptr _Tmp = _ByItem(); _Acc::_Right(_Ptr) = _Tmp; _Acc::_Parent(_Tmp) = _Ptr; _Acc::_IfNode(_Ptr) = true; _Acc::_Index(_Tmp) = _IndexGen(); return true; } _UInt left(void) { return 1; } _UInt right(void) { return 2; } _Nil _NULL() { return _Nil; } protected: _Itemptr _ByItem(void) { _Itemptr _Tmp = allocator._Charalloc( 1 * sizeof (_Item)); return _Tmp; } void _FreeItem(_Itemptr _S) { allocator.deallocate(_S, 1); } _UInt _IndexGen(_UInt _IP) { if(!(_IP % 2)) return ((/*2 * _IP*/ _IP << 2) + 1); else return ((/*2 * _IP*/ _IP << 2) + 2); } _Itemptr calculate_way(/*wert*/) { if(!_IsValid(/*wert*/)) return _NULL(); _Way *_L = _PtoP(/*wert*/); return _WalkDown(_L); } _Itemptr _WalkDown(const _Way &_W) { _W::const_iterator _I; _Itemptr _Lo = _Head(); for(_I = _W.rbegin(); _I != _W.rend(); ++_I) { if(!(*_I % 2)) { _Lo = _Acc::_Right(_Lo); } else { _Lo = _Acc::_Left(_Lo); } } return _Lo; } _Itemptr _Head() { return _Head; } _A allocator; _Itemptr _Head; _Item _Root; }; #endif((2 * nummer) + 1) und ((2 * nummer) + 2) ergeben sich folgendermaßen:
ist man an einem knoten, enthält dieser einen index bzw die knotennummer.
zusätzlich enthält der knoten 2 variablen, normalerweise left und right.
um das nummerierungsschema beizubehalten_____ |__0__| / \ / \ / \ ____ ____ |__1_| |__2_| / \ | \ / \ | \ ____ ____ | \ |__3_| |__4_| ____ ____ |__5_| |__6_| usw.muss der index des neuen elements errechnet werden.
zb.: wir sind bei knoten eins. nun fügen wir ein element auf die rechte seite ein. nach dem nummerierungsschema muss der wert der variable index des neuen elements 4 sein. ((2 * 1) + 2) = 4
würden links von knoten 1 ein element hinzufügen, muss der wert der index variable des neuen elements 3 sein. ((2 * 1) + 1) = 3- ((nummer - 2) / 2)
diese formeln, machen genau das gegenteil der obigen 2 formeln
- ((nummer - 1) / 2)dh. hat man einen knoten index, so kann man den index des vaterknotens errechnen
gruß xerxes
-
#ifndef _BINTREE_ #define _BINTREE #include <cstddef> #include <functional> #include <iterator> #include <memory> #include <stdexcept> #include <xutility> #include <vector> #include <stack> #include <list> template<class _Ty, class _A = allocator<_Ty> > class bintree { protected: struct _Item; friend struct _Item; typedef _POINTER_X(_Item, _A) _Itemptr; struct _Item{ _Itemptr _Left, _Right, _Parent; unsigned int _ItemIndex; bool _IfNode; _Ty _Value; _Item() : _ItemIndex(0), _IfNode(false) _Left(this), _Right(this) {} }; struct _Acc; friend struct _Acc; struct _Acc { typedef _REFERENCE_X(_Itemptr, _A) _Itempref; typedef _A::reference _Vref; static _Itempref _Left(_Itemptr _P) {return ((_Itempref)(*_P)._Left); } static _Itempref _Right(_Itemptr _P) {return ((_Nodepref)(*_P)._Right); } static _Itempref _Parent(_Itemptr _P) {return ((_Nodepref)(*_P)._Parent); } static _Vref _Value(_Itemptr _P) {return ((_Vref)(*_P)._Value); } static _Vref _Index(_Itemptr _P) {return ((_Vref)(*_P)._ItemIndex); } static _Vref _IfNode(_Itemptr _P) {return ((_Vref)(*_P)._IfNode); } }; typedef unsigned int _UInt; typedef std::list<_UInt> _Way; // typedef NULL _Nil; public: typedef _UInt _Point; class const_iterator; friend class const_iterator; class const_iterator { public: const_iterator() : _Ptr(Head()) {} /* const_iterator(unsigned int _I) : _ItemIndex(_I) { } */ _Acc::_Vref operator*() const {return (_Acc::_Value(_Ptr)); } /* _Acc::_Vref _GoToParent() { _Ptr = _Acc::_Parent(_Ptr); return (_Acc::_Value(_Ptr)); } _Acc::_Vref _LeftDown() { _Ptr = _Acc::_Left(_Ptr); return (_Acc::_Value(_Ptr)); } _Acc::_Vref _RightDown() { _Ptr = _Acc::_Right(_Ptr); return (_Acc::_Value(_Ptr)); }*/ void _GoToParent() { _Ptr = _Acc::_Parent(_Ptr); return (_Acc::_Value(_Ptr)); } void _LeftDown() { _Ptr = _Acc::_Left(_Ptr); return (_Acc::_Value(_Ptr)); } void _RightDown() { _Ptr = _Acc::_Right(_Ptr); return (_Acc::_Value(_Ptr)); } bool _GoToSpecificP(_Point _P) { if((_Itemptr _Tmp = calculate_way(_P)) == _NULL()) return false; _Ptr = _Tmp; } protected: //stack<_UInt> _WayStack; //_UInt _ItemIndex; _Itemptr _Ptr; }; bool push(const _Ty &_X, _Point _P, _UInt _Way) { if((_Itemptr _Ptr = calculate_way(_P)) == _NULL()) return false; _Use(_P); if(_Way == left()) return insert_left(_X, _Ptr); else if(_Way == right()) return insert_right(_X, _Ptr); } bool insert_left(const _Ty &_Xr, _Itemptr _Ptr) { _Itemptr _Tmp = _ByItem(); _Acc::_Left(_Ptr) = _Tmp; _Acc::_Parent(_Tmp) = _Ptr; _Acc::_IfNode(_Ptr) = true; _Acc::_Index(_Tmp) = _IndexGen(); allocator.construct(&_Acc::_Value(_Tmp), _Xr); return true; } bool insert_right(const _Ty &_Xr, _Itemptr _Ptr) { _Itemptr _Tmp = _ByItem(); _Acc::_Right(_Ptr) = _Tmp; _Acc::_Parent(_Tmp) = _Ptr; _Acc::_IfNode(_Ptr) = true; _Acc::_Index(_Tmp) = _IndexGen(); allocator.construct(&_Acc::_Value(_Tmp), _Xr); return true; } _UInt left(void) { return 1; } _UInt right(void) { return 2; } NULL _NULL() { return NULL; } protected: _Itemptr _ByItem(void) { _Itemptr _Tmp = allocator._Charalloc( 1 * sizeof (_Item)); return _Tmp; } void _FreeItem(_Itemptr _S) { allocator.deallocate(_S, 1); } _UInt _IndexGen(_UInt _IP) { if(!(_IP % 2)) return ((/*2 * _IP*/ _IP << 2) + 1); else return ((/*2 * _IP*/ _IP << 2) + 2); } _Itemptr calculate_way(_Point _P) { if(!_IsValid(_P)) return _NULL(); _Way _L; _PtoP(_P, _L); return _WalkDown(_L); } _Itemptr _WalkDown(const _Way &_W) { _W::const_iterator _I; _Itemptr _Lo = Head(); for(_I = _W.rbegin(); _I != _W.rend(); ++_I) { if(!(*_I % 2)) _Lo = _Acc::_Right(_Lo); else _Lo = _Acc::_Left(_Lo); } return _Lo; } void _PtoP(_Point _P, const _Way &_W) { while(_P) { if((_P % 2)) _P = ((_P - 1) / 2); else _P = ((_P - 2) / 2); _W.push_back(_P); } } bool _IsValid(_Point _P) { _Way _L; _Way::const_iterator _I; for(_I = _L.begin(); _I != _L.end(); ++_I) { if(*_I == _P) return false; } return true; } void _Use(_Point _P) { _InUse.push_back(_P); } void _OutUse(_Point _P) { _Way _L; _Way::const_iterator _I; for(_I = _L.begin(); _I != _L.end(); ++_I) { if(*_I == _P) _I.erase(_I); } } _Itemptr Head() { return _Head; } _Way _InUse; _A allocator; _Itemptr _Head; _Item _Root; }; #endifhi, der compiler spuckt folgende fehlermeldungen aus mit denen ich nichts anfangen kann.
--------------------Konfiguration: bintree - Win32 Debug-------------------- Kompilierung läuft... main.cpp c:\dokumente und einstellungen\administrator\desktop\fa111\binäre bäume\complex calculator\bintree\bintree.h(127) : error C2059: Syntaxfehler : 'constant' c:\dokumente und einstellungen\administrator\desktop\fa111\binäre bäume\complex calculator\bintree\bintree.h(190) : Siehe Verweis auf Instantiierung der kompilierten Klassenvorlage 'bintree<_Ty,_A>' c:\dokumente und einstellungen\administrator\desktop\fa111\binäre bäume\complex calculator\bintree\bintree.h(128) : error C2334: Unerwartete(s) Token vor '{'; sichtbarer Funktionsrumpf wird übersprungen c:\dokumente und einstellungen\administrator\desktop\fa111\binäre bäume\complex calculator\bintree\bintree.h(190) : Siehe Verweis auf Instantiierung der kompilierten Klassenvorlage 'bintree<_Ty,_A>' c:\dokumente und einstellungen\administrator\desktop\fa111\binäre bäume\complex calculator\bintree\bintree.h(14) : error C2065: 'allocator' : nichtdeklarierter Bezeichner c:\dokumente und einstellungen\administrator\desktop\fa111\binäre bäume\complex calculator\bintree\bintree.h(14) : error C2275: "_Ty" : Ungültige Verwendung dieses Typs als Ausdruck C:\Dokumente und Einstellungen\Administrator\Desktop\fa111\binäre bäume\complex calculator\bintree\main.cpp(11) : Siehe Deklaration von '_Ty' c:\dokumente und einstellungen\administrator\desktop\fa111\binäre bäume\complex calculator\bintree\bintree.h(14) : error C2974: 'bintree' : Ungueltiges Vorlagenargument für '_A', Typ erwartet c:\dokumente und einstellungen\administrator\desktop\fa111\binäre bäume\complex calculator\bintree\bintree.h(190) : Siehe Deklaration von 'bintree' C:\Dokumente und Einstellungen\Administrator\Desktop\fa111\binäre bäume\complex calculator\bintree\main.cpp(11) : error C2143: Syntaxfehler : Fehlendes ';' vor '>' C:\Dokumente und Einstellungen\Administrator\Desktop\fa111\binäre bäume\complex calculator\bintree\main.cpp(11) : error C2143: Syntaxfehler : Fehlendes ';' vor '>' Fehler beim Ausführen von cl.exe. bintree.exe - 7 Fehler, 0 Warnung(en)ich benutze mvs 6