Binary search tree

  1 #ifndef __TREE_H
  2 #define __TREE_H
  3 #include <iostream>
  4 
  5 template<typename T> class TreeNode {
  6 private:
  7     T             _data;
  8     TreeNode<T>* _left;
  9     TreeNode<T>* _right;
 10     TreeNode<T>* _parent;
 11 public:
 12     TreeNode(T data,
 13             TreeNode<T>* parent=0,
 14             TreeNode<T>* left=0,
 15             TreeNode<T>* right=0)
 16         :_data(data),_parent(parent),_left(left),_right(right) {}
 17     void insertAtLeft(T data);
 18     void insertAtRight(T data);
 19     T& getData();
 20     TreeNode<T>*& getLeft();
 21     TreeNode<T>*& getRight();
 22     TreeNode<T>*& getParent();
 23 };
 24 
 25 template<typename T>
 26 T& TreeNode<T>::getData()
 27 {
 28     return _data;
 29 }
 30 
 31 template<typename T>
 32 TreeNode<T>*& TreeNode<T>::getLeft()
 33 {
 34     return _left;
 35 }
 36 
 37 template<typename T>
 38 TreeNode<T>*& TreeNode<T>::getRight()
 39 {
 40     return _right;
 41 }
 42 
 43 template<typename T>
 44 TreeNode<T>*& TreeNode<T>::getParent()
 45 {
 46     return _parent;
 47 }
 48 
 49 template<typename T>
 50 void TreeNode<T>::insertAtLeft(T data)
 51 {
 52     _left = new TreeNode(data,this);
 53 }
 54 
 55 template<typename T>
 56 void TreeNode<T>::insertAtRight(T data)
 57 {
 58     _right = new TreeNode(data,this);
 59 }
 60 
 61 template <typename T> class Tree{
 62 private:
 63     TreeNode<T>* _root;
 64     int          _size;
 65 protected:
 66     TreeNode<T>* findIn(TreeNode<T>* position,T element) const;
 67     /*
 68      * The last tmp argument is necessary,
 69      * it is used here to changed the parent's _left/_right field
 70      * to potint the node which is created 
 71      */
 72     TreeNode<T>* insertIn(TreeNode<T>* position,
 73             T element,TreeNode<T>* tmp);
 74     void travIn(TreeNode<T>* position);
 75     void travPrev(TreeNode<T>* position);
 76     void travPost(TreeNode<T>* position);
 77 public:
 78     Tree(T data)
 79         :_root(new TreeNode<T> (data)),_size(1) { }
 80     TreeNode<T>* find(T element) const;
 81     TreeNode<T>* findMax() const;
 82     TreeNode<T>* findMin() const;
 83     TreeNode<T>* insert(T data);
 84     void traversalIn();
 85     void traversalPrev();
 86     void traversalPost();
 87 };
 88 
 89 template<typename T>
 90 void Tree<T>::travIn(TreeNode<T>* position)
 91 {
 92     if(!position)
 93         return ;
 94     travIn(position->getLeft());
 95     std::cout << position->getData() << " ";
 96     travIn(position->getRight());
 97 }
 98 
 99 template<typename T>
100 void Tree<T>::travPrev(TreeNode<T>* position)
101 {
102     if(!position)
103         return ;
104     std::cout << position->getData() << " ";
105     travPrev(position->getLeft());
106     travPrev(position->getRight());
107 }
108 
109 template<typename T>
110 void Tree<T>::travPost(TreeNode<T>* position)
111 {
112     if(!position)
113         return ;
114     travPost(position->getLeft());
115     travPost(position->getRight());
116     std::cout << position->getData() << " ";
117 }
118 
119 template<typename T>
120 void Tree<T>::traversalPost()
121 {
122     travPost(_root);
123     std::cout << std::endl;
124 }
125 
126 template<typename T>
127 void Tree<T>::traversalPrev()
128 {
129     travPrev(_root);
130     std::cout << std::endl;
131 }
132 
133 template<typename T>
134 void Tree<T>::traversalIn()
135 {
136     travIn(_root);
137     std::cout << std::endl;
138 }
139 
140 template<typename T>
141 TreeNode<T>* Tree<T>::insertIn(TreeNode<T>* position,T data,
142         TreeNode<T>* tmp)
143 {
144     if(!position){
145         if(!tmp)
146             return new TreeNode<T>(data);
147         else
148             return (tmp->getData() >data ? tmp->getLeft():tmp->getRight())
149                 = new TreeNode<T>(data,tmp);
150     }
151     if(data < position->getData())
152         insertIn(position->getLeft(),data,position);
153     else if(position->getData() < data)
154         insertIn(position->getRight(),data,position);
155     else 
156         return position;
157 }
158 template<typename T>
159 TreeNode<T>* Tree<T>::insert(T data)
160 {
161     return insertIn(_root,data,0);
162 }
163 
164 template<typename T>
165 TreeNode<T>* Tree<T>::findIn(TreeNode<T>* position,T data)const
166 {
167     while(position && position->getData() != data)
168     {
169         if(position->getData() > data)
170             position = position->getLeft();
171         else if(position->getData() < data)
172             position = position->getRight();
173     }
174     return position;
175 }
176 
177 template<typename T>
178 TreeNode<T>* Tree<T>::find(T data) const
179 {
180     return findIn(_root,data);
181 }
182 
183 template<typename T>
184 TreeNode<T>* Tree<T>::findMax() const
185 {
186     TreeNode<T>* tmp = _root;
187     while(tmp->getRight())
188         tmp = tmp->getRight();
189     return tmp;
190 }
191 
192 template<typename T>
193 TreeNode<T>* Tree<T>::findMin() const
194 {
195     TreeNode<T>* tmp = _root;
196     while(tmp->getLeft())
197         tmp = tmp->getLeft();
198     return tmp;
199 }
200 
201 #endif
二叉搜索树