blob: c1da45133e97acca55cbb8278c71e4d1e394f9dd (
plain)
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
|
// Fig. 15.16: tree.h
// Definition of template class Tree
#ifndef TREE_H
#define TREE_H
#include <iostream>
using std::cout;
using std::endl;
using std::ostream;
#include <iomanip>
#include <cassert>
#include <fstream>
using std::ofstream;
using std::ifstream;
using std::ios;
#include "Treenode.h"
template< class NODETYPE >
class Tree {
public:
Tree();
void insertNode( const NODETYPE & );
void preOrderTraversal() const;
void inOrderTraversal() const;
void postOrderTraversal() const;
int gettreeElementCount();
private:
TreeNode< NODETYPE > *rootPtr;
int treeElementCount;
// utility functions
void insertNodeHelper(
TreeNode< NODETYPE > **, const NODETYPE & );
void preOrderHelper( TreeNode< NODETYPE > * ) const;
void inOrderHelper( TreeNode< NODETYPE > * ) const;
void postOrderHelper( TreeNode< NODETYPE > * ) const;
};
template< class NODETYPE >
Tree< NODETYPE >::Tree() { rootPtr = 0; treeElementCount=0; }
template< class NODETYPE >
void Tree< NODETYPE >::insertNode( const NODETYPE &value )
{ insertNodeHelper( &rootPtr, value ); }
// This function receives a pointer to a pointer so the
// pointer can be modified.
template< class NODETYPE >
void Tree< NODETYPE >::insertNodeHelper(
TreeNode< NODETYPE > **ptr, const NODETYPE &value )
{
if ( *ptr == 0 ) { // tree is empty
*ptr = new TreeNode< NODETYPE >( value );
(*ptr)->frequency++;
++treeElementCount;
assert( *ptr != 0 );
}
else // tree is not empty
if ( value < ( *ptr )->data )
insertNodeHelper( &( ( *ptr )->leftPtr ), value );
else
if ( value > ( *ptr )->data )
insertNodeHelper( &( ( *ptr )->rightPtr ), value );
else
(*ptr)->frequency++;
}
template< class NODETYPE >
void Tree< NODETYPE >::preOrderTraversal() const
{ preOrderHelper( rootPtr ); }
template< class NODETYPE >
void Tree< NODETYPE >::preOrderHelper(
TreeNode< NODETYPE > *ptr ) const
{
if ( ptr != 0 ) {
cout << ptr->data << ' ';
preOrderHelper( ptr->leftPtr );
preOrderHelper( ptr->rightPtr );
}
}
template< class NODETYPE >
void Tree< NODETYPE >::inOrderTraversal() const
{ inOrderHelper( rootPtr ); }
template< class NODETYPE >
void Tree< NODETYPE >::inOrderHelper(
TreeNode< NODETYPE > *ptr ) const
{
ofstream outFile("output.txt",ios::app);
if( !outFile ) {
cerr << "Output-Datei konnte nicht geoeffnet werden." << endl;
exit( 1 );
}
if ( ptr != 0 ) {
inOrderHelper( ptr->leftPtr );
outFile << std::setw(30) << std::left << std::setfill('.') << ptr->data
<< ptr->frequency << endl;
inOrderHelper( ptr->rightPtr );
}
outFile.close();
}
template< class NODETYPE >
void Tree< NODETYPE >::postOrderTraversal() const
{ postOrderHelper( rootPtr ); }
template< class NODETYPE >
void Tree< NODETYPE >::postOrderHelper(
TreeNode< NODETYPE > *ptr ) const
{
if ( ptr != 0 ) {
postOrderHelper( ptr->leftPtr );
postOrderHelper( ptr->rightPtr );
cout << ptr->data << ' ';
}
}
template <class NODETYPE>
int Tree<NODETYPE>::gettreeElementCount()
{
return treeElementCount;
}
#endif
|
