Lab12/BinaryTreeIterator.h at master · scaneer/Lab12 · GitHub

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
115
#if !defined (BINARYTREEITERATOR_H)
#define BINARYTREEITERATOR_H

#include "QueueLinked.h"
using CSC2110::QueueLinked;
#include "TreeNode.h"

template < class T >
class BinaryTreeIterator
{

   private:
      QueueLinked<T>* q;
      TreeNode<T>* root;

      void inorder(TreeNode<T>* tNode);
      void preorder(TreeNode<T>* tNode);
      void postorder(TreeNode<T>* tNode);

   public:
      BinaryTreeIterator(TreeNode<T>* root);
      ~BinaryTreeIterator();

      bool hasNext();
      T* next();

      void setInorder();
      void setPreorder();
      void setPostorder();

};

template < class T >
BinaryTreeIterator<T>::BinaryTreeIterator(TreeNode<T>* r)
{
   q = new QueueLinked<T>();
   root = r;
}

template < class T >
BinaryTreeIterator<T>::~BinaryTreeIterator()
{
   delete q;
}

template < class T >
bool BinaryTreeIterator<T>::hasNext()
{
   return (!q->isEmpty());
}

template < class T >
T* BinaryTreeIterator<T>::next()
{
   if (hasNext())
   {
      return q->dequeue();
   }
}

template < class T >
void BinaryTreeIterator<T>::setInorder()
{
   q->dequeueAll();
   inorder(root);
}

template < class T >
void BinaryTreeIterator<T>::inorder(TreeNode<T>* tNode)
{
   if (tNode != NULL)
   {
      inorder(tNode->getLeft());
      q->enqueue(tNode->getItem());
      inorder(tNode->getRight());
   }
}

template < class T >
void BinaryTreeIterator<T>::setPreorder()
{
   q->dequeueAll();
   preorder(root);
}

template < class T >
void BinaryTreeIterator<T>::preorder(TreeNode<T>* tNode)
{
   if (tNode != NULL)
   {
      q->enqueue(tNode->getItem());
      preorder(tNode->getLeft());
      preorder(tNode->getRight());
   }
}

template < class T >
void BinaryTreeIterator<T>::setPostorder()
{
   q->dequeueAll();
   postorder(root);
}

template < class T >
void BinaryTreeIterator<T>::postorder(TreeNode<T>* tNode)
{
   if (tNode != NULL)
   {
      postorder(tNode->getLeft());
      postorder(tNode->getRight());
      q->enqueue(tNode->getItem());
   }
}

#endif