第六十三课二叉树中的结点插入操作

如果新节点指定的目标父节点已经有左孩子和右孩子了，这时插入就会失败，这就是和通用树不同的地方。

插入新结点时，需要指定插入位置。例如，左孩子或者右孩子位置。

不带位置参数的插入函数可以插入到任何位置。

BTreeNode实现了自己的工厂模式，如下所示：

 1 #ifndef BTREENODE_H
 2 #define BTREENODE_H
 3 
 4 #include "TreeNode.h"
 5 
 6 namespace DTLib
 7 {
 8 
 9 enum BTNodePos
10 {
11     ANY,
12     LEFT,
13     RIGHT
14 };
15 
16 template < typename T >
17 class BTreeNode : public TreeNode<T>
18 {
19 public:
20     BTreeNode<T>* left;
21     BTreeNode<T>* right;
22 
23     BTreeNode()
24     {
25         left = NULL;
26         right = NULL;
27     }
28 
29     static BTreeNode<T>* NewNode()
30     {
31         BTreeNode<T>* ret = new BTreeNode<T>();
32 
33         if( ret != NULL )
34         {
35             ret->m_flag = true;
36         }
37 
38         return ret;
39     }
40 };
41 
42 }
43 
44 #endif // BTREENODE_H

BTree.h添加插入函数：

  1 #ifndef BTREE_H
  2 #define BTREE_H
  3 
  4 #include "Tree.h"
  5 #include "BTreeNode.h"
  6 #include "Exception.h"
  7 #include "LinkQueue.h"
  8 
  9 namespace DTLib
 10 {
 11 
 12 template < typename T >
 13 class BTree : public Tree<T>
 14 {
 15 protected:
 16     //定义递归功能函数
 17     virtual BTreeNode<T>* find(BTreeNode<T>* node, const T& value) const
 18     {
 19         BTreeNode<T>* ret = NULL;
 20 
 21         if( node != NULL )
 22         {
 23             if( node->value == value )
 24             {
 25                 ret = node;
 26             }
 27             else
 28             {
 29                 if( ret == NULL )
 30                 {
 31                     ret = find(node->left, value);
 32                 }
 33 
 34                 if( ret == NULL )
 35                 {
 36                     ret = find(node->right, value);
 37                 }
 38             }
 39         }
 40 
 41         return ret;
 42     }
 43 
 44     virtual BTreeNode<T>* find(BTreeNode<T>* node, BTreeNode<T>* obj) const
 45     {
 46         BTreeNode<T>* ret = NULL;
 47 
 48         if( node == obj )
 49         {
 50             ret = node;
 51         }
 52         else
 53         {
 54             if( node != NULL )
 55             {
 56                 if( ret == NULL )
 57                 {
 58                     ret = find(node->left, obj);
 59                 }
 60 
 61                 if( ret == NULL )
 62                 {
 63                     ret = find(node->right, obj);
 64                 }
 65             }
 66         }
 67 
 68         return ret;
 69     }
 70 
 71     virtual bool insert(BTreeNode<T>* n, BTreeNode<T>* np, BTNodePos pos)
 72     {
 73         bool ret = true;
 74 
 75         if( pos == ANY )
 76         {
 77             if( np->left == NULL )
 78             {
 79                 np->left = n;
 80             }
 81             else if( np->right == NULL )
 82             {
 83                 np->right = n;
 84             }
 85             else
 86             {
 87                 ret = false;
 88             }
 89         }
 90         else if( pos == LEFT )
 91         {
 92             if( np->left == NULL )
 93             {
 94                 np->left = n;
 95             }
 96             else
 97             {
 98                 ret = false;
 99             }
100         }
101         else if( pos == RIGHT )
102         {
103             if( np->right == NULL )
104             {
105                 np->right = n;
106             }
107             else
108             {
109                 ret = false;
110             }
111         }
112         else
113         {
114             ret = false;
115         }
116 
117         return ret;
118     }
119 public:
120     bool insert(TreeNode<T>* node)
121     {
122         return insert(node, ANY);
123     }
124 
125     virtual bool insert(TreeNode<T>* node, BTNodePos pos)
126     {
127         bool ret = true;
128 
129         if( node != NULL )
130         {
131             if( this->m_root == NULL )  //空树
132             {
133                 node->parent = NULL;
134                 this->m_root = node;
135             }
136             else
137             {
138                 BTreeNode<T>* np = find(node->parent);
139 
140                 if( np != NULL )
141                 {
142                     ret = insert(dynamic_cast<BTreeNode<T>*>(node), np, pos);
143                 }
144                 else
145                 {
146                     THROW_EXCEPTION(InvalidParameterException, "invalid parent tree node...");
147                 }
148             }
149         }
150         else
151         {
152             THROW_EXCEPTION(InvalidParameterException, "parameter node can not be null...");
153         }
154 
155         return ret;
156     }
157 
158     bool insert(const T& value, TreeNode<T>* parent)
159     {
160         return insert(value, parent, ANY);
161     }
162 
163     virtual bool insert(const T& value, TreeNode<T>* parent, BTNodePos pos)
164     {
165         bool ret = true;
166         BTreeNode<T>* node = BTreeNode<T>::NewNode();
167 
168         if( node == NULL )
169         {
170             THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create node...");
171         }
172         else
173         {
174             node->value = value;
175             node->parent = parent;
176 
177             ret = insert(node, pos);
178 
179             if( !ret )
180             {
181                 delete node;
182             }
183         }
184 
185         return ret;
186     }
187 
188     SharedPointer< Tree<T> > remove(const T& value) //删除的节点的子节点我们还需要处理，因此要返回删除节点的指针，//这样有机会对里面的元素做进一步操作
189     {
190         return NULL;
191     }
192 
193     SharedPointer< Tree<T> > remove(TreeNode<T>* node)
194     {
195         return NULL;
196     }
197 
198     BTreeNode<T>* find(const T& value) const
199     {
200         return find(root(), value);
201     }
202 
203     BTreeNode<T>* find(TreeNode<T>* node) const
204     {
205         return find(root(), dynamic_cast<BTreeNode<T>*>(node));
206     }
207 
208     BTreeNode<T>* root() const
209     {
210         return dynamic_cast<BTreeNode<T>*>(this->m_root);
211     }
212 
213     int degree() const
214     {
215         return 0;
216     }
217 
218     int count() const
219     {
220         return 0;
221     }
222 
223     int height() const
224     {
225         return 0;
226     }
227 
228     void clear()
229     {
230         this->m_root = NULL;
231     }
232 
233     ~BTree()
234     {
235         clear();
236     }
237 };
238 
239 }
240 
241 #endif // BTREE_H

测试程序如下：

 1 #include <iostream>
 2 #include "GTree.h"
 3 #include "GTreeNode.h"
 4 #include "BTree.h"
 5 #include "BTreeNode.h"
 6 
 7 
 8 using namespace std;
 9 using namespace DTLib;
10 
11 
12 int main()
13 {
14     BTree<int> bt;
15     BTreeNode<int>* n = NULL;
16 
17     bt.insert(1, NULL);
18 
19     n = bt.find(1);
20     bt.insert(2, n);
21     bt.insert(3, n);
22 
23     n = bt.find(2);
24     bt.insert(4, n);
25     bt.insert(5, n);
26 
27     n = bt.find(4);
28     bt.insert(8, n);
29     bt.insert(9, n);
30 
31     n = bt.find(5);
32     bt.insert(10, n);
33 
34     n = bt.find(3);
35     bt.insert(6, n);
36     bt.insert(7, n);
37 
38     n = bt.find(6);
39     bt.insert(11, n, LEFT);
40 
41     int a[] = {8, 9, 10, 11, 7};
42 
43     for(int i = 0; i < 5; i++)
44     {
45         TreeNode<int>* node = bt.find(a[i]);
46 
47         while( node )
48         {
49             cout << node->value << " ";
50             node = node->parent;
51         }
52 
53         cout << endl;
54     }
55 
56     return 0;
57 }

结果如下：

小结：

第六十三课 二叉树中的结点插入操作

第六十三课二叉树中的结点插入操作