第六十一课二叉树的存储结构设计

BTree和BTreeNode之间是聚合关系，BTree需要聚合的使用BTreeNode。

BTreeNode要包含指向父节点的指针，方便工程应用。

二叉树也是容器类型，需要实现增删查。

先重构GTreeNode.h和TreeNode.h文件：

 1 #ifndef GTREENODE_H
 2 #define GTREENODE_H
 3 
 4 #include "TreeNode.h"
 5 #include "LinkList.h"
 6 
 7 namespace DTLib
 8 {
 9 
10 template < typename T >
11 class GTreeNode : public TreeNode<T>
12 {
13 public:
14     LinkList<GTreeNode<T>*> child;
15 
16     static GTreeNode<T>* NewNode()
17     {
18         GTreeNode<T>* ret = new GTreeNode<T>();
19 
20         if( ret != NULL )
21         {
22             ret->m_flag = true;
23         }
24 
25         return ret;
26     }
27 };
28 
29 }
30 
31 #endif // GTREENODE_H

 1 #ifndef TREENODE_H
 2 #define TREENODE_H
 3 
 4 #include "Object.h"
 5 
 6 namespace DTLib
 7 {
 8 
 9 template < typename T >
10 class TreeNode : public Object
11 {
12 protected:
13     bool m_flag;
14 
15     TreeNode(const TreeNode<T>&);
16     TreeNode<T>& operator = (const TreeNode<T>&);
17 
18     void* operator new(unsigned int size) throw()
19     {
20         return Object::operator new(size);
21     }
22 
23 public:
24     T value;
25     TreeNode<T>* parent;
26 
27     TreeNode()
28     {
29         m_flag = false;
30         parent = NULL;
31     }
32 
33     bool flag()
34     {
35         return m_flag;
36     }
37 
38     virtual ~TreeNode() = 0;
39 };
40 
41 template < typename T >
42 TreeNode<T>::~TreeNode()   //提供一个空的实现，否则可能编译不过
43 {
44 
45 }
46 
47 }
48 
49 #endif // TREENODE_H

对Gtree.h也做一下重构，GTree中原来有这样的代码：

18、19行是防止拷贝构造和赋值的，现在我们将这两行代码放到父类Tree.h中，如下：

变为了16、17两行，这样子类之间赋值或者拷贝构造时，也会调用到父类Tree.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 public:
16     bool insert(TreeNode<T>* node)
17     {
18         bool ret = true;
19 
20         return ret;
21     }
22 
23     bool insert(const T& value, TreeNode<T>* parent)
24     {
25         bool ret = true;
26 
27         return ret;
28     }
29 
30     SharedPointer< Tree<T> > remove(const T& value) //删除的节点的子节点我们还需要处理，因此要返回删除节点的指针，//这样有机会对里面的元素做进一步操作
31     {
32         return NULL;
33     }
34 
35     SharedPointer< Tree<T> > remove(TreeNode<T>* node)
36     {
37         return NULL;
38     }
39 
40     BTreeNode<T>* find(const T& value) const
41     {
42         return NULL;
43     }
44 
45     BTreeNode<T>* find(TreeNode<T>* node) const
46     {
47         return NULL;
48     }
49 
50     BTreeNode<T>* root() const
51     {
52         return dynamic_cast<BTreeNode<T>*>(this->m_root);
53     }
54 
55     int degree() const
56     {
57         return 0;
58     }
59 
60     int count() const
61     {
62         return 0;
63     }
64 
65     int height() const
66     {
67         return 0;
68     }
69 
70     void clear()
71     {
72         this->m_root = NULL;
73     }
74 
75     ~BTree()
76     {
77         clear();
78     }
79 };
80 
81 }
82 
83 #endif // BTREE_H

第六十一课 二叉树的存储结构设计

第六十一课二叉树的存储结构设计