-
Notifications
You must be signed in to change notification settings - Fork 0
/
ComicTree.h
160 lines (131 loc) · 4.1 KB
/
ComicTree.h
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
// Binary tree abstract base class
// Created by Frank M. Carrano and Tim Henry.
// Modified by: Minh An Cao
//
// ComicTree.h
//
// This is the header file for the ComicTree class.
//
// Minh An Cao
//
#ifndef _COMIC_TREEin
#define _COMIC_TREE
#include "ComicNode.h"
#include "Stack.h"
#include "Queue.h"
#include "Comic.h"
template<class ItemType>
class ComicTree
{
protected:
ComicNode<ItemType>* rootPtr; // ptr to root node
int count; // number of nodes in tree
public:
// "admin" functions
ComicTree() {rootPtr = 0; count = 0;}
ComicTree(const ComicTree<ItemType> & tree){ }
virtual ~ComicTree() { }
ComicTree & operator = (const ComicTree & sourceTree);
// common functions for all binary trees
bool isEmpty() const {return count == 0;}
int size() const {return count;}
void clear() {destroyTree(rootPtr); rootPtr = 0; count = 0;}
void preOrder(void visit(ItemType &)) const {_preorder(visit, rootPtr);}
void inOrder(void visit(ItemType &)) const {_inorder(visit, rootPtr);}
void postOrder(void visit(ItemType &)) const{_postorder(visit, rootPtr);}
void breadthOrder(void visit(ItemType &)) const{_breadthorder(visit, rootPtr);}
private:
// delete all nodes from the tree
void destroyTree(ComicNode<ItemType>* nodePtr);
// copy from the tree rooted at nodePtr and returns a pointer to the copy
ComicNode<ItemType>* copyTree(const ComicNode<ItemType>* nodePtr);
// internal traverse
void _preorder(void visit(ItemType &), ComicNode<ItemType>* nodePtr) const;
void _inorder(void visit(ItemType &), ComicNode<ItemType>* nodePtr) const;
void _postorder(void visit(ItemType &), ComicNode<ItemType>* nodePtr) const;
void _iterpreorder(void visit(ItemType &), ComicNode<ItemType>* nodePtr) const;
void _iterinorder(void visit(ItemType &), ComicNode<ItemType>* nodePtr) const;
void _iterpostorder(void visit(ItemType &), ComicNode<ItemType>* nodePtr) const;
void _breadthorder(void visit(ItemType &), ComicNode<ItemType>* nodePtr) const;
};
//////////////////////////////////////////////////////////////////////////
template<class ItemType>
ComicNode<ItemType>* ComicTree<ItemType>::copyTree(const ComicNode<ItemType>* nodePtr)
{
ComicNode<ItemType>* newNodePtr = 0;
return newNodePtr;
}
template<class ItemType>
void ComicTree<ItemType>::destroyTree(ComicNode<ItemType>* nodePtr)
{
if(nodePtr != NULL)
{
destroyTree(nodePtr->getLeftPtr());
destroyTree(nodePtr->getRightPtr());
delete(nodePtr);
if(nodePtr->getLeftPtr()!=NULL)
nodePtr->setLeftPtr(NULL);
if(nodePtr->getRightPtr()!=NULL)
nodePtr->setRightPtr(NULL);
nodePtr=NULL;
}
}
template<class ItemType>
void ComicTree<ItemType>::_preorder(void visit(ItemType &), ComicNode<ItemType>* nodePtr) const
{
if (nodePtr != 0)
{
ItemType item = nodePtr->getItem();
visit(item);
_preorder(visit, nodePtr->getLeftPtr());
_preorder(visit, nodePtr->getRightPtr());
}
}
template<class ItemType>
void ComicTree<ItemType>::_inorder(void visit(ItemType &), ComicNode<ItemType>* nodePtr) const
{
if (nodePtr != 0)
{
_inorder(visit, nodePtr->getLeftPtr());
ItemType item = nodePtr->getItem();
visit(item);
_inorder(visit, nodePtr->getRightPtr());
}
}
template<class ItemType>
void ComicTree<ItemType>::_postorder(void visit(ItemType &), ComicNode<ItemType>* nodePtr) const
{
if (nodePtr != 0)
{
_postorder(visit, nodePtr->getLeftPtr());
_postorder(visit, nodePtr->getRightPtr());
ItemType item = nodePtr->getItem();
visit(item);
}
}
template<class ItemType>
void ComicTree<ItemType>::_breadthorder(void visit(ItemType &), ComicNode<ItemType>* nodePtr) const
{
Queue<ComicNode<ItemType>*> q;
if (nodePtr != 0)
{
q.enqueue(nodePtr);
}
while (!q.isEmpty())
{
ComicNode<ItemType>* temp;
q.queueFront(temp);
ItemType item = temp->getItem();
visit(item);
if (temp->getLeftPtr() != NULL)
q.enqueue(temp->getLeftPtr());
if (temp->getRightPtr() != NULL)
q.enqueue(temp->getRightPtr());
q.dequeue(temp);
}
}
template<class ItemType>
ComicTree<ItemType> & ComicTree<ItemType>::operator=(const ComicTree<ItemType> & sourceTree)
{
}
#endif