003
17.04.2004, 00:10 Uhr
(un)wissender
Niveauwart
|
Ein rudimentärer C++-Ansatz.
Wer Fehler findet, darf sie melden .
Schöner wäre es noch, BinaryNode nur intern im Tree zu verwenden und std::pair alles Schlüssel-Wertepaar zu nehmen.
| C++: |
#include <iostream>
template <typename K, typename T>
class BinaryNode
{
public:
BinaryNode(const K &key)
: key_(key), value_(), leftChild_(0), rightChild_(0) {}
BinaryNode(const K &key, const T &value)
: key_(key), value_(value), leftChild_(0), rightChild_(0) {}
void setLeftChild(BinaryNode<K,T> * leftChild)
{ leftChild_ = leftChild;}
void setRightChild(BinaryNode<K,T> * rightChild)
{ rightChild_ = rightChild;}
const BinaryNode<K,T> * getLeftChild() const
{ return leftChild_;}
const BinaryNode<K,T> * getRightChild() const
{ return rightChild_;}
void setValue(const T& value)
{ value_ = value; }
const T& getValue() const
{ return value_; }
void setKey(const K &key)
{ key_ = key; }
const T& getKey() const
{ return key_; }
bool operator< (const BinaryNode<K,T> &otherNode) const
{ return key_ < otherNode.key_; }
bool operator> (const BinaryNode<K,T> &otherNode) const
{ return key_ > otherNode.key_; }
private:
K key_;
T value_;
BinaryNode<K,T> *leftChild_;
BinaryNode<K,T> *rightChild_;
};
template<typename T, typename K>
std::ostream & operator<<(std::ostream &out, const BinaryNode<K,T> &node)
{ return out << node.getValue(); }
template<typename K, typename T>
class BinaryTree
{
public:
BinaryTree();
BinaryTree(const BinaryTree<K,T> &node);
BinaryTree<K,T> & operator=(const BinaryTree<K,T> &node);
~BinaryTree();
void insert(const K& key, const T& value);
void insert(const BinaryNode<K,T> &node);
void erase(const K& key);
void erase(const BinaryNode<K,T> &node);
const BinaryNode<K,T> * find(const K& key) const;
BinaryNode<K,T> * find(const K& key);
//Ascii-art :)
void printTree() const;
private:
//Baum ausbalancieren, kann sehr aufwendig sein!
void makeBalancedTree();
//z.B rekuriv Baum durchsuchen: preorder, postorder...
BinaryNode<K,T> * internalFind(const K& key) const;
BinaryNode<K,T> *root;
};
|
--
Wer früher stirbt ist länger tot.
Dieser Post wurde am 17.04.2004 um 00:17 Uhr von (un)wissender editiert. |
