diff options
| author | Sven Eisenhauer <sven@sven-eisenhauer.net> | 2023-11-10 15:11:48 +0100 |
|---|---|---|
| committer | Sven Eisenhauer <sven@sven-eisenhauer.net> | 2023-11-10 15:11:48 +0100 |
| commit | 33613a85afc4b1481367fbe92a17ee59c240250b (patch) | |
| tree | 670b842326116b376b505ec2263878912fca97e2 /Bachelor/Prog2/person-tree/Tree.h | |
| download | Studium-master.tar.gz Studium-master.tar.bz2 | |
Diffstat (limited to 'Bachelor/Prog2/person-tree/Tree.h')
| -rw-r--r-- | Bachelor/Prog2/person-tree/Tree.h | 130 |
1 files changed, 130 insertions, 0 deletions
diff --git a/Bachelor/Prog2/person-tree/Tree.h b/Bachelor/Prog2/person-tree/Tree.h new file mode 100644 index 0000000..c1da451 --- /dev/null +++ b/Bachelor/Prog2/person-tree/Tree.h @@ -0,0 +1,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
|