#include #include #include using namespace std; class Object { public: virtual string getType() = 0; }; // class Leaf { class Leaf : public Object { public: Leaf( int v ) { value = v; } string getType() { return "Leaf"; } void traverse() { cout << value << ' '; } private: int value; }; // class Interior { class Interior : public Object { public: Interior( int v ) { value = v; } string getType() { return "Interior"; } void traverse() { cout << value << ' '; for (int i=0; i < children.size(); i++) if (children[i]->getType() == "Leaf") children[i]->traverse(); else ((Interior*)children[i])->traverse(); } void add( Leaf* l ) { children.push_back( l ); } private: int value; vector children; }; void main( void ) { // 1 Interior top( 1 ); // | Interior two( 2 ); // +-- 11 Interior thr( 3 ); // | Interior fou( 4 ); // +-- 2 top.add( &Leaf( 11 ) ); // | | top.add( (Leaf*) &two ); // | +-- 21 top.add( &Leaf( 12 ) ); // | | top.add( (Leaf*) &thr ); // | +-- 22 top.add( &Leaf( 13 ) ); // | | two.add( &Leaf( 21 ) ); // | +-- 4 two.add( &Leaf( 22 ) ); // | | two.add( (Leaf*) &fou ); // | +-- 41 42 thr.add( &Leaf( 31 ) ); // +-- 12 thr.add( &Leaf( 32 ) ); // | fou.add( &Leaf( 41 ) ); // +-- 3 fou.add( &Leaf( 42 ) ); // | | top.traverse(); // | +-- 31 32 cout << '\n'; // | } // +-- 13 // 1 11 2 21 22 4 41 42 12 3 31 32 13 #if 0 #include #include #include using namespace std; class Component { public: virtual void traverse() = 0; }; // class Leaf { class Leaf : public Component { public: Leaf( int v ) { value = v; } void traverse() { cout << value << ' '; } private: int value; }; // class Interior { class Interior : public Component { public: Interior( int v ) { value = v; } void traverse() { cout << value << ' '; for (int i=0; i < children.size(); i++) children[i]->traverse(); } void add( Component* l ) { children.push_back( l ); } private: int value; vector children; }; void main( void ) { Interior top( 1 ); Interior two( 2 ); Interior thr( 3 ); Interior fou( 4 ); top.add( &Leaf( 11 ) ); top.add( &two ); top.add( &Leaf( 12 ) ); top.add( &thr ); top.add( &Leaf( 13 ) ); two.add( &Leaf( 21 ) ); two.add( &Leaf( 22 ) ); two.add( &fou ); thr.add( &Leaf( 31 ) ); thr.add( &Leaf( 32 ) ); fou.add( &Leaf( 41 ) ); fou.add( &Leaf( 42 ) ); top.traverse(); cout << '\n'; } // 1 11 2 21 22 4 41 42 12 3 31 32 13 #endif