线索二叉树，二叉搜索树的简单实现

利用前面的二叉树设计，可以很方便的实现线索二叉树，二叉搜索树，下面给出代码，很多功能还有待添加。

//thread_binary_tree.h

1 #ifndef _THREAD_BIANTY_TREE_H_
 2 #define _THREAD_BIANTY_TREE_H_
 3
 4 #include "binary_tree.h"
 5
 6 namespace binary_tree{
 7
 8 //ThreadBinaryTreeNode with elem type T
 9 template<typename T>
10 class ThreadBinaryTreeNode : public BinaryTreeNodeBase< T, ThreadBinaryTreeNode<T> > {
11 public:
12 typedef with_thread_node_tag node_category;
13 ThreadBinaryTreeNode() :m_ltag(0),m_rtag(0) {}
14 ThreadBinaryTreeNode(const T& elem, ThreadBinaryTreeNode<T> * left = NULL,
15 ThreadBinaryTreeNode<T> * right = NULL,
16 bool ltag = 0, bool rtag = 0)
17 : BinaryTreeNodeBase< T, ThreadBinaryTreeNode<T> > (elem, left, right),
18 m_ltag(ltag), m_rtag(rtag){}
19 const bool ltag() const{
20 return m_ltag;
21 }
22 const bool rtag() const{
23 return m_rtag;
24 }
25 void set_ltag(bool ltag){
26 m_ltag = ltag;
27 }
28 void set_rtag(bool rtag){
29 m_rtag = rtag;
30 }
31 private:
32 bool m_ltag;
33 bool m_rtag;
34 };
35
36 template <typename U, typename T = ThreadBinaryTreeNode >
37 class ThreadBinaryTree;
38
39 //到底要不要让穿线二叉树继承BinaryTree呢还是独立一个类
40 //如果继承，那么要继承所有接口，但是基本上都要重写内容
41 //我现在只关心一部分内容，提供一部分接口，所以可以独立
42 //写，这里还是用了继承先，注意使用的时候仅使用那些穿线二叉
43 //树改写的内容的接口，理论上一个完整的穿线二叉树应该能
44 //提供BinaryTree的所有接口的,而且这样好复用简单
45 //也可以单独一个类，以后如果需要添加其它接口，需要BinaryTree
46 //的实现的化用复合，调用处理。
47 //其实如ThreadBinaryTree只想继承BinaryTree的一部分，暗示
48 //BinaryTree的接口太多了，想要继承的是核心接口，应该提出来。
49 //剩下的可以AdvacedBinaryTree public BinaryTree
50 //或者剩下的用non memer func
51 //这里先用private 继承屏蔽掉基类的接口,恩还是可以用复用
52 //但是复用代码写起来麻烦些,哦但是那样基类的root()
53 //用户也没办法用了，还要在thread_tree中明写，权衡，呵呵
54 //暂时还是public吧， TODO
55
56 //注意对于PrintTree采用了InorderTravel(虚函数重定义)不同的基类triats手法
57 template <typename U>
58 class ThreadBinaryTree< U,ThreadBinaryTreeNode > : public BinaryTree<U, ThreadBinaryTreeNode > {
59 public:
60 typedef ThreadBinaryTreeNode T;
61 ~ThreadBinaryTree() { DeleteBinaryTree(this->root()); this->set_root(NULL); } //well 无法访问需要 this->
62 virtual void DeleteBinaryTree(T *root);
63 virtual void InOrderTravel(T *root);
64 virtual void CreateTree(U end_mark) {
65 BinaryTree<U, ThreadBinaryTreeNode >::CreateTree(end_mark);
66 //T* p = NULL;
67 //InThreadRec(this->root(), p); //no access to m_root directly, 注意InThreadRec(this->root(), NULL)不对
68 InThreadNoRec(this->root());
69 cout << "Finished inorder threading" << endl;
70 }
71 // TODO
72 // virtual void FindElem(T* root, U elem);
73 // virtual void PrintTree(); //涉及很多地方要改动
74 // virtual void PreOrderTravel();
75 // virtual void PostOrderTravel();
76 // T* InOrderNext(T *current);
77 // T* InOrderPre(T *current);
78 // T* PreOrderNext(T *current);
79 // void InsertNode(T *pointer, T *newpointer)
80 private:
81 //递归中序线索化二叉树
82 void InThreadRec(T *root, T *&pre); //这里需要引用

.wow!,这里的pre相当一个全局量，而不是随着递归变化的，相当sum
83 //非递归中序线索化二叉树 //相当容易出错！！！因为要求pre的值及时变化，但如果不是引用，下层变化了，退
84 void InThreadNoRec(T *root); //到上层，pre的值又变回到当时的值了(当前栈内)
85 //中序周游
86 };
87
88 template <typename U>
89 void ThreadBinaryTree< U,ThreadBinaryTreeNode > ::
90 DeleteBinaryTree(ThreadBinaryTreeNode *root) {
91 cout << "Dlete thread tree" << endl;
92 if (root) {
93 if (!root->ltag())
94 DeleteBinaryTree(root->left());
95 if (!root->rtag())
96 DeleteBinaryTree(root->right());
97 delete root;
98 }
99 }
100 //关于二叉中序穿线树就是对于左子树为空的存它在中序遍历的前驱，显然对于中序第一访问的节点没有前驱，这里采用不处理方式
101 //是不行的，因为遍历的时候不方便，也需要把它设置为ltag = 1;
102 //右子树为空则存它在中序遍历的后继，对于中序最后访问的节点，无后继,不特殊处理，所以最后存在两个NULL指针
103 //对于NULL指针也就无所谓去判断是线索还是左右子树了。
104 template <typename U>
105 void ThreadBinaryTree< U,ThreadBinaryTreeNode > ::
106 InThreadRec(ThreadBinaryTreeNode *root, ThreadBinaryTreeNode *&pre) {
107 cout << "Inorder rec threading" << endl;
108 if (root) {
109 InThreadRec(root->left(), pre);
110 if (!root->left()) {
111 root->set_ltag(1);
112 root->set_left(pre);
113 }
114 if (pre && !pre->right()) {
115 pre->set_rtag(1);
116 pre->set_right(root);
117 }
118 pre = root;
119 InThreadRec(root->right(), pre);
120 }
121 }
122
123 template <typename U>
124 void ThreadBinaryTree< U,ThreadBinaryTreeNode > ::
125 InThreadNoRec(ThreadBinaryTreeNode *root) {
126 cout << "Inorder threading no rec" << endl;
127 typedef ThreadBinaryTreeNode T;
128 T* p = root;
129 T* pre = NULL;
130 stack<T *> s;
131 while(!s.empty() || p) {
132 if (p){
133 s.push(p);
134 p = p->left();
135 } else {
136 p = s.top();
137 if (!p->left()) {
138 p->set_ltag(1);
139 p->set_left(pre);
140 }
141 if (pre && !pre->right()) {
142 pre->set_rtag(1);
143 pre->set_right(p);
144 }
145 pre = p;
146 s.pop();
147 p = p->right();
148 }
149 }
150 }
151
152 template <typename U>
153 void ThreadBinaryTree< U,ThreadBinaryTreeNode > ::
154 InOrderTravel(ThreadBinaryTreeNode *root) {
155 cout << "Inorder travel thread tree" << endl;
156 typedef ThreadBinaryTreeNode T;
157 T* p = root;
158 // while (p) {
159 // if (!p->ltag()) {
160 // p = p->left();
161 // } else {
162 // Visit(p);
163 // while (p->rtag()) {
164 // p = p->right();
165 // Visit(p);
166 // }
167 // p = p->right(); //上面的while 是必要的不能直接p->right 只有对于原右子为空情况p->right 才进入下一向左状态
168 // } //否则p->right 之后右p->left重复访问左子树了
169 // }
170 while (p) {
171 while(!p->ltag()) {
172 p = p->left(); //左子树走
173 }
174 Visit(p); //访问
175 while (p->rtag()) { //右子树为空，相当不停的pop 访问根节点(左子树已经访问完)
176 p = p->right(); //注意p->right 访问后继的话，证明左子树访问完，要访问右子的，没有继续后继,而不能重复再访问左子
177 Visit(p);
178 }
179 p = p->right(); //OK,进入右子树，重复开始的向左走
180 } //上面的while 是必要的不能直接p->right 只有对于原右子为空情况p->right 才进入下一向左状态
181 } //否则p->right 之后右p->left重复访问左子树了
182
183
184
185 //template <typename U, typename T = ThreadBinaryTreeNode >
186 //class ThreadBinaryTree {
187 // public:
188 // ThreadBinaryTree() { m_root = NULL;}
189 // virtual ~ ThreadBinaryTree() {DeleteBinaryTree(m_root);}
190 // private:
191 // T* m_root;
192 //}
193
194
195 } // end of namespace binary_tree
196 #endif // end of _THREAD_BIANTY_TREE_H_
197

//binary_search_tree.h

1 #ifndef _BINARY_SEARCH_TREE_H_
 2 #define _BINARY_SEARCH_TREE_H_
 3 #include "binary_tree.h"
 4 namespace binary_tree{
 5
 6 //当期二叉搜索树无重复值节点
 7 template<typename U, typename T = BinaryTreeNode >
 8 class BinarySearchTree;
 9
10 // TODO 这个命名不太好
11 // 允许有重复元素的二叉搜索树
12 template<typename U, typename T = BinaryTreeNode >
13 class BinarySearchTree2;
14
15 template<typename U>
16 class BinarySearchTree< U, BinaryTreeNode > : public BinaryTree< U, BinaryTreeNode > {
17 public:
18 typedef BinaryTreeNode T;
19 // TODO why here do not need 构造函数,while BinaryTree need
20 void InsertNode(const U elem) {
21 //InsertNodeRec(this->m_root, elem);
22 InsertNode(this->m_root, elem);
23 }
24 void DeleteNode(const U elem) {
25 DeleteNode(this->m_root, elem);
26 }
27 private:
28 void InsertNodeRec(T *&root,const U elem);
29 virtual void InsertNode(T *root, const U elem);
30 virtual void DeleteNode(T *root, const U elem);
31 //void InsertNode(T *root, T *pn);
32 };
33
34 //允许相同的元素，后进入的相同元素插入到原元素右子树的最左下
35 //well 这里有个问题，对于继承类，
36 //例如 BinarySearchTre2<float> tree; tree.InserNode(3.0);
37 //编译器似乎只会找到 InsertNode(T *root, const U elem)，认为它最匹配但不成功
38 //而不会去基类中查找,解决办法避免重名重载?
39 // TODO 这里先把虚函数名从 InsertNode改成InsertNode成功不过感觉不爽
40 // well 条款33，基类的名称被遮掩了！！所以编译器看不到基类的void InsertNode(const U elem)
41 // 这个陷阱好深，其实编译器应该对子类的虚函数不要掩盖基类名称.
42 // 另外编译器竟然还是要求virtual void DeleteNode(T *root, const U elem)
43 // 提供定义，不能用基类默认的吗,哦，用默认的你就不要再写
44 template<typename U>
45 class BinarySearchTree2<U, BinaryTreeNode > : public BinarySearchTree<U, BinaryTreeNode > {
46 public:
47 typedef BinaryTreeNode T;
48 //这样也不行，因为基类有个virtual void InsertNode(T *root, const U elem);是私有
49 //using BinarySearchTree<U, BinaryTreeNode >::InsertNode;
50 //这能用转交函数了,或者你就改名呵呵
51 void InsertNode(const U elem) {
52 BinarySearchTree<U, BinaryTreeNode >::InsertNode(elem);
53 }
54 //递归函数打印min到mx之间的元素
55 void PrintRange(T *root, U min, U max);
56 int PrintRangeRec(T *root, U min, U max);
57 private:
58 virtual void InsertNode(T *root, const U elem);
59 //virtual void DeleteNode(T *root, const U elem);
60 };
61
62 /*binary tree 实现*/
63
64 //递归写法，简单，但是注意到每次只可能走一个分支，其实递归是没有意义的
65 //可以很简单的写成非递归
66 template <typename U>
67 void BinarySearchTree< U,BinaryTreeNode >::
68 InsertNodeRec(BinaryTreeNode *&root,const U elem) {
69 typedef BinaryTreeNode T;
70 if (!root)
71 root = new T(elem);
72 else if (elem < root->elem())
73 InsertNode(root->m_left, elem);
74 else if (elem > root->elem())
75 InsertNode(root->m_right, elem);
76 else //遇到相同节点，不需要插入
77 return;
78 }
79
80 //So 不要递归思维定势
81 template <typename U>
82 void BinarySearchTree< U,BinaryTreeNode >::
83 InsertNode(BinaryTreeNode *root,const U elem) {
84 typedef BinaryTreeNode T;
85 //空树
86 if (!root) {
87 this->set_root(new T(elem));
88 return;
89 }
90
91 T* p = root;
92
93 while (1) {
94 if (elem == p->elem()) //遇到相同的节点，无需插入了
95 break;
96 if (elem < p->elem()) {
97 if (p ->left()) {
98 p = p->left();
99 } else {
100 p->set_left(new T(elem));
101 break;
102 }
103
104 } else {
105 if (p->right()) {
106 p = p->right();
107 } else {
108 p->set_right(new T(elem));
109 break;
110 }
111 }
112 }
113 }
114 template <typename U>
115 void BinarySearchTree< U,BinaryTreeNode >::
116 DeleteNode(BinaryTreeNode *root,const U elem) {
117 typedef BinaryTreeNode T;
118
119 if(this->IsEmpty())
120 return;
121
122 }
123
124
125 /*带重复元素的binary tree实现*/
126
127 template <typename U>
128 void BinarySearchTree2< U,BinaryTreeNode >::
129 InsertNode(BinaryTreeNode *root,const U elem) {
130 typedef BinaryTreeNode T;
131 //空树
132 if (!root) {
133 this->set_root(new T(elem));
134 return;
135 }
136 T* p = root;
137 while (1) {
138 if (elem < p->elem()) {
139 if (p ->left()) {
140 p = p->left();
141 } else {
142 p->set_left(new T(elem));
143 break;
144 }
145
146 } else { // elem >= p->elem()
147 if (p->right()) {
148 p = p->right();
149 } else {
150 p->set_right(new T(elem));
151 break;
152 }
153 }
154 }
155 }
156
157 template <typename U>
158 void BinarySearchTree2< U,BinaryTreeNode >::
159 PrintRange(BinaryTreeNode *root, U min, U max) {
160 assert(min <= max);
161 typedef BinaryTreeNode T;
162 if (!root)
163 return;
164 if (root->elem() == min) { //遇到了比min小或者相同的，其左子树无须访问了，相同需先访问根，小于则无需了直接右子树
165 Visit(root);
166 PrintRange(root->right(),min,max);
167 } else if (root->elem() > min) {
168 PrintRange(root->left(),min,max);
169 if (root->elem() > max) // 遇到更大的遍历结束
170 return;
171 Visit(root);
172 PrintRange(root->right(), root->elem(), max); //改成root->elem()没有太大优化
173 } else {
174 PrintRange(root->right(),min,max);
175 }
176 }
177
178 template <typename U>
179 int BinarySearchTree2< U,BinaryTreeNode >::
180 PrintRangeRec(BinaryTreeNode *root, U min, U max) {
181
182 }
183
184 } //end of namespace binary_tree
185 #endif //end of _BINARY_SEARCH_TREE_H_
186