C++

Forum

 
Postorder binary search tree traversal

ashlclm (21)
This is for homework, I have done a few implementations for preorder/levelorder, but am having a difficult time.

iterator is biderectional, using a stack. I understand the process of how tree traversal works but putting it into the correct syntax with a stack is just making me run in circles. Any help or hints is greatly appreciated.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 

 template < class C >
 class PostorderBTIterator // patterns: ConstIterator, BidirectionalIterator
 {
 public: // terminology support
   typedef typename C::ValueType      ValueType;
   typedef typename C::Node           Node;
   typedef PostorderBTIterator<C>     ConstIterator;
   typedef PostorderBTIterator<C>     Iterator;

 private: // inner sanctum; keep stack implementation choice compatible w ChechRBLLT
  friend C;
 fsu::Stack < Node* > stk_; // default is deque-based - better safety & error detection
   fsu::Stack < Node* , fsu::Vector < Node* > > stk_; // faster

 public:
   // first class
   PostorderBTIterator                 () : stk_() {}
   virtual  ~PostorderBTIterator       () { stk_.Clear(); }
   PostorderBTIterator                 (const PostorderBTIterator& i) : stk_(i.stk)

   PostorderBTIterator<C>&  operator=  (const PostorderBTIterator& i) { stk_ = i.stk_; return\
 *this; }

   // information/access
   bool  Valid   () const { return !stk_.Empty(); } // Iterator can be de-references

   // various operators
   bool                     operator== (const PostorderBTIterator& i2) const { return stk_ ==\
 i2.stk_; }
   bool                     operator!= (const PostorderBTIterator& i2) const { return !(*this\
 == i2); }
   const ValueType&         operator*  () const { return stk_.Top()->value_; }
   PostorderBTIterator<C>&  operator++ ();    // prefix
   PostorderBTIterator<C>   operator++ (int); // postfix
     PostorderBTIterator<C>&  operator-- ();    // prefix
     PostorderBTIterator<C>   operator-- (int); // postfix

// developers helper
   void Dump( std::ostream& os = std::cout , char ofc = '\0' ) const;

   private:
     void Init      (Node* n); // live nodes only
     void rInit     (Node* n); // live nodes only
     void Increment (); // structural version of ++
     void Decrement (); // structural version of --
   };
Last edited on
ashlclm (21)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
 
here are implementations..
  template < class C >
   void PostorderBTIterator<C>::Dump(std::ostream& os, char ofc) const
   {
     fsu::Stack < Node* , fsu::Vector < Node* > > s(stk_);
     fsu::Stack < Node* , fsu::Vector < Node* > > stk;
     while (!s.Empty())
     {
       stk.Push(s.Top());
       s.Pop();
     }
     if (ofc == '\0')
     {
       while (!stk.Empty())
       {
         os << stk.Top()->value_;
         stk.Pop();
       }
     }
     else
     {
       while (!stk.Empty())
       {
         os << ofc << stk.Top()->value_;
         stk.Pop();
       }
     }
     os << '\n';
   }

   template < class C >
   void PostorderBTIterator<C>::Init(Node* n)
   // only intended to be used with n = root_
   {
     // implementation required

     Node * n;
       while (n->IsDead())
         Increment();
   }
   template < class C >
   void PostorderBTIterator<C>::Increment()
   {
     // implementation required
    /* what i have currently
 if (n->HasLeftChild)
     {
       ++n;
     }
     else if (n->HasRightChild)
     {
       n++;
     }
     else
     {
       while (n->IsValid())//if no children, go up to parent
       {
         prev = n;
         --n;
         if ((prev == n.lchild_) && n->HasRightChild())
         {
           n++;            //find sibling of the root
           break;
         }
       }
     }
   }

*/

 template < class C >
   void PostorderBTIterator<C>::rInit(Node* n)
   // only intended to be used with n = root_
   {
     // implementation required
   }

   template < class C >
   void PostorderBTIterator<C>::Decrement()
   {
     // implementation required
   }

   template < class C >
   PostorderBTIterator<C>&  PostorderBTIterator<C>::operator++ ()
   {
     // implementation required
   }

   template < class C >
   PostorderBTIterator<C>   PostorderBTIterator<C>::operator++ (int)
   {
     // implementation required
   }

   template < class C >
   PostorderBTIterator<C>&  PostorderBTIterator<C>::operator-- ()
   {
     // implementation required
   }

   template < class C >
   PostorderBTIterator<C>   PostorderBTIterator<C>::operator-- (int)
   {
     // implementation required
   }

 } // namespace fsu

 #endif



[code]
[/code]
Last edited on
Topic archived. No new replies allowed.