行者无疆 始于足下 - 行走，思考，在路上
bst, avl, c++, inheritance, template, two days
鉴于大二上年幼无知加上某些特殊的原因，导致我大三才开始修读高级数据结构。同一屋子大二的小朋友们上课，百般滋味，心中自知。第一次课迟到了，下课的时候随便找了两个学弟，算是组了个队，并申请做Project1(因为开始的Project)会比较简单。
实践起来也不是很难，就是让你比较下BinarySearchTree, AVL Tree和Splay Tree的插入删除效率的问题。两个学弟看样子都不愿意编码，于是乎，编码的重担就落在了我这个学长身上。可是只有我自己知道，我数据结构学的实在不咋的，C++又是个半吊子。唉，谁让咱是学长呢？
学长嘛，自然要有个学长的样子。于是乎，C++、Template、Inheritance、Polymorphism，能用上的都用上……呵呵。不过主要是想练一下手。C++ Primer虽然看了大半，却没有多少应用的机会。这也算是一个练习吧。
写着写着就知道，C++的强大是一把双刃剑，强大到你无法驾驭，尤其是应用了模板后，各种小问题，都是以前闻所未闻的。比如模板的分离编译问题，看书，查资料就花了两个小时。加上昨天下午吐血恶心的同步时序电路的逻辑实验，做的我都想哭了。所以这么看上去很简单的project，我竟然写了接近两天，倍感惭愧。
不过总算出来了。但是有个瑕疵，avl的删除功能有些小问题，可能跟Balance函数和指针的引用问题有关。gdb我用的不熟，转到强大的windows下的visual studio 2008下，调试了3个小时，找到错误所在，但是却不知道怎么改正。泪奔。
计算几何最终还是低空坠毁，唉，不提也罢，看来以后不能乱选课，选了课不能随便混混。混不好就低空坠毁。你说你没事选这么一门前沿课程干嘛，你是这块料嘛……
计算几何过后开始准备计算理论的期中考试。什么有穷自动机，正则语言，上下文无关文法，等等，计算理论基础的中文版，每个小时3页，龟速前进，发现还是太抽象，看不大懂，又找来一本计算理论导引，两本结合着看，顿觉顺畅很多，看来计算机的书还是要原汁原味的英文啊。
感觉计算理论期中还不错。周一被导师叫去公司，让我参加项目，大意是让我写一个TextArea。项目代码有四万左右，光理清这个体系，补windows编程的基础知识就花了我三四天的时间。终于搞明白了什么叫windows ce，什么叫GDI，学会了windows下svn的基本用法。可是看windows ce的书还是一头雾水，什么HINSTANCE，WINAPI WinMain()，叉叉的。基本流程我还不懂。于是去找windows经典书目的书单，看到多人推荐Charles Petzold的windows程序设计，吐血买了下来，花了150元。Microsoft的书真tn的贵。
不过书是好书。周六周日周一断续看了三天，看了四章，120页，顿时明白了很多。个人windows的技术更新太快，不想unix，二十年前的vim、emacs、grep，等，万古不变。掌握win32 API才是一切的根本。永远不要指望跟上Microsoft的脚步。
只不过到现在导师的项目还没有开工，我还夸下海口自不量力要一周写出来。这可如何是好。还有图形学作业，操作系统作业，实验的作业，呃……少壮不努力，老大做it，大二不学习，大三干苦力。要努力。恩。
BinarySearchTree.h:
#ifndef _BINARYSEARCHTREE_H_
#define _BINARYSEARCHTREE_H_
#include <iostream>
#include <stack>
using namespace std;
/// 三种遍历方式
#define PREORDERTRAVERSE 0
#define INORDERTRAVERSE 1
#define POSTORDERTRAVERSE 2
/// 求两个元素的最大值
#define max(x, y) ((x > y) ? (x) : y)
/**
* @class BinaryNode
* @brief 树的结点，为了方便BST和AVL用了同一种结构。BST中所有结点的height域为默认值
*/
template<typename Comparable>
struct BinaryNode
{
Comparable element;
BinaryNode* left;
BinaryNode* right;
int height;
BinaryNode(const Comparable &theElement, BinaryNode *lt, BinaryNode *rt, const int theHeight = 0)
: element(theElement), left(lt), right(rt), height(theHeight) {}
};
/**
* @class BinarySearchTree
* @brief 实现了常见的删除，插入功能。并作为AVL树的基类
*/
template<typename Comparable>
class BinarySearchTree
{
public:
BinarySearchTree();
~BinarySearchTree();
BinaryNode<Comparable>*& GetRoot();
void BuildBinaryTree(Comparable *x, int length);
const Comparable& FindMin() const;
const Comparable& FindMax() const;
bool Contains(const Comparable &x) const;
bool IsEmpty() const;
void TraverseTree(int type);
void MakeEmpty();
virtual void Insert(const Comparable &x);
virtual void Remove(const Comparable &x);
private:
BinaryNode<Comparable> *root;
virtual void Insert(const Comparable &x, BinaryNode<Comparable> *&t) const;
virtual void Remove(const Comparable &x, BinaryNode<Comparable> *&t) const;
BinaryNode<Comparable>* FindMin(BinaryNode<Comparable> *&t) const;
BinaryNode<Comparable>* FindMax(BinaryNode<Comparable> *&t) const;
bool Contains(const Comparable &x, BinaryNode<Comparable> *&t) const;
void MakeEmpty(BinaryNode<Comparable> *&t);
void PreOrderTraverse(BinaryNode<Comparable> *&t);
void InOrderTraverse(BinaryNode<Comparable> *&t);
void PostOrderTraverse(BinaryNode<Comparable> *&t);
};
/**
* 构造函数，默认root=NULL
*
*
* @return
*/
template<typename Comparable>
BinarySearchTree<Comparable>::BinarySearchTree() : root(NULL){}
/**
* 析构函数
*
*
* @return
*/
template<typename Comparable>
BinarySearchTree<Comparable>::~BinarySearchTree()
{
MakeEmpty();
}
/**
* 得到根节点的引用
*
*
* @return 返回根节点的引用
*/
template<typename Comparable>
BinaryNode<Comparable>*& BinarySearchTree<Comparable>::GetRoot()
{
return root;
}
/**
* 建立BST树，通过数组的方式传入元素，调用Insert(x)函数
*
* @param x
* @param length
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::BuildBinaryTree(Comparable *x, int length)
{
for (int i = 0; i < length; ++i)
{
Insert(x[i]);
}
}
/**
* @return BST中的最小值
*/
template<typename Comparable>
const Comparable& BinarySearchTree<Comparable>::FindMin() const
{
return FindMin(root)->element;
}
/**
* @return BST中的最大值
*/
template<typename Comparable>
const Comparable& BinarySearchTree<Comparable>::FindMax() const
{
return FindMax(root)->element;
}
/**
* 测试x是否在BST中，调用私有函数Contains(x, root)
*
* @param x
*
* @return
*/
template<typename Comparable>
bool BinarySearchTree<Comparable>::Contains(const Comparable &x) const
{
return Contains(x, root);
}
/**
* 测试树是否为空
*
*
* @return
*/
template<typename Comparable>
bool BinarySearchTree<Comparable>::IsEmpty() const
{
if (root == NULL)
{
return true;
}
return false;
}
/**
* 以三种方式遍历树
*
* @param type 遍历树的方式
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::TraverseTree(int type)
{
if (type == PREORDERTRAVERSE)
{
cout << "PreOrderTraverse the tree:" << endl;
PreOrderTraverse(root);
cout << endl << "PreOrderTraverse ends." << endl;
}
if (type == INORDERTRAVERSE)
{
cout << "InOrderTraverse the tree:" << endl;
InOrderTraverse(root);
cout << endl << "InOrderTraverse ends." << endl;
}
if (type == POSTORDERTRAVERSE)
{
cout << "PostOrderTraverse the tree:" << endl;
PostOrderTraverse(root);
cout << endl << "InOrderTraverse ends." << endl;
}
}
/**
* 清空BST树
*
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::MakeEmpty()
{
MakeEmpty(root);
}
/**
* 向BST中插入一个元素
*
* @param x 待插入的元素
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::Insert(const Comparable &x)
{
Insert(x, root);
}
/**
* 从BST中删除一个元素
*
* @param x 被删除的元素
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::Remove(const Comparable &x)
{
Remove(x, root);
}
/**
* 向树根为t的树中插入一个元素
*
* @param x 待插入的元素
* @param t 树根
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::Insert(const Comparable &x, BinaryNode<Comparable> *&t) const
{
if (t == NULL)
{
t = new BinaryNode<Comparable>(x, NULL, NULL, -3);
}
else if (x < t->element)
{
Insert(x, t->left);
}
else if (x > t->element)
{
Insert(x, t->right);
}
else
; //dupicate; you can do something, of course
}
/**
* 从树根为t的树中删除元素
*
* @param x 被删除的元素
* @param t 树根
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::Remove(const Comparable &x, BinaryNode<Comparable> *&t) const
{
if (t == NULL)
{
return;
}
else if (x < t->element)
{
Remove(x, t->left);
}
else if (x > t->element)
{
Remove(x, t->right);
}
else if (t->left != NULL && t->right != NULL)
{
t->element = FindMin(t->right)->element;
Remove(t->element, t->right);
}
else
{
BinaryNode<Comparable> *oldNode = t;
t = (t->left != NULL) ? t->left : t->right;
delete oldNode;
}
}
template<typename Comparable>
BinaryNode<Comparable>* BinarySearchTree<Comparable>::FindMin(BinaryNode<Comparable> *&t) const
{
if (t != NULL)
{
while(t->left != NULL)
t = t->left;
}
return t;
}
template<typename Comparable>
BinaryNode<Comparable>* BinarySearchTree<Comparable>::FindMax(BinaryNode<Comparable> *&t) const
{
if (t != NULL)
{
while(t->right != NULL)
t = t->right;
}
return t;
}
template<typename Comparable>
bool BinarySearchTree<Comparable>::Contains(const Comparable &x, BinaryNode<Comparable> *&t) const
{
if (t == NULL)
{
return false;
}
else if (x < t->element)
{
return Contains(x, t->left);
}
else if (x > t->element)
{
return Contains(x, t->right);
}
else
return true;
}
template<typename Comparable>
void BinarySearchTree<Comparable>::MakeEmpty(BinaryNode<Comparable> *&t)
{
if (t != NULL)
{
MakeEmpty(t->left);
MakeEmpty(t->right);
delete t;
}
t = NULL;
}
/**
* 前序遍历
*
* @param t
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::PreOrderTraverse(BinaryNode<Comparable> *&t)
{
if (t != NULL)
{
cout << t->element << " ";
PreOrderTraverse(t->left);
PreOrderTraverse(t->right);
}
}
/**
* 中序遍历
*
* @param t
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::InOrderTraverse(BinaryNode<Comparable> *&t)
{
if (t != NULL)
{
InOrderTraverse(t->left);
cout << t->element << " ";
InOrderTraverse(t->right);
}
}
/**
* 后序遍历
*
* @param t
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::PostOrderTraverse(BinaryNode<Comparable> *&t)
{
if (t != NULL)
{
PostOrderTraverse(t->left);
PostOrderTraverse(t->right);
cout << t->element << " ";
}
}
/**
* @class AVLTree
* @brief 由于AVLTree本身是一种改进的BST树，所以绝大多数特性继承自BST树。其中的Insert()和Remove方法和BST树中不同，因此在BST类中将此方法声明为virtual function
*/
template<typename Comparable>
class AVLTree : public BinarySearchTree<Comparable>
{
public:
AVLTree();
~AVLTree();
int GetHeight();
void Insert(const Comparable &x);
void Remove(const Comparable &x);
protected:
int GetHeight(BinaryNode<Comparable> *&t);
void Insert(const Comparable &x, BinaryNode<Comparable> *&t);
void Remove(const Comparable &x, BinaryNode<Comparable> *&t);
void SingleRotateLeftChild(BinaryNode<Comparable> *&k2);
void SingleRotateRightChild(BinaryNode<Comparable> *&k2);
void DoubleRotateLeftChild(BinaryNode<Comparable> *&k3);
void DoubleRotateRightChild(BinaryNode<Comparable> *&k3);
void Balance(BinaryNode<Comparable> *&t);
};
/**
* 构造函数，调用BST基类的构造函数
*
*
* @return
*/
template<typename Comparable>
AVLTree<Comparable>::AVLTree() : BinarySearchTree<Comparable>::BinarySearchTree()
{
// BinaryNode<Comparable>* root = BinarySearchTree<Comparable>::GetRoot();
// root = NULL;
}
/**
* 析构函数，调用基类的BST::MakeEmpty()
*
*
* @return
*/
template<typename Comparable>
AVLTree<Comparable>::~AVLTree()
{
BinarySearchTree<Comparable>::MakeEmpty();
}
/**
* 得到整棵AVL树的高度
*
*
* @return
*/
template<typename Comparable>
int AVLTree<Comparable>::GetHeight()
{
BinaryNode<Comparable>*& root = BinarySearchTree<Comparable>::GetRoot();
return GetHeight(root);
}
/**
* 向AVL中插入元素x
*
* @param x 待插入的元素
*/
template<typename Comparable>
void AVLTree<Comparable>::Insert(const Comparable &x)
{
BinaryNode<Comparable>*& root = BinarySearchTree<Comparable>::GetRoot();
Insert(x, root);
}
/**
* 从AVL中删除元素x
*
* @param x 被删除的元素
*/
template<typename Comparable>
void AVLTree<Comparable>::Remove(const Comparable &x)
{
BinaryNode<Comparable>*& root = BinarySearchTree<Comparable>::GetRoot();
Remove(x, root);
}
/**
* 得到结点t的高度
*
* @param t
*
* @return
*/
template<typename Comparable>
int AVLTree<Comparable>::GetHeight(BinaryNode<Comparable> *&t)
{
return t == NULL ? -1 : t->height;
}
template<typename Comparable>
void AVLTree<Comparable>::Insert(const Comparable &x, BinaryNode<Comparable> *&t)
{
if (t == NULL)
{
t = new BinaryNode<Comparable>(x, NULL, NULL);
}
else if (x < t->element)
{
Insert(x, t->left);
Balance(t);
// if (GetHeight(t->left) - GetHeight(t->right) == 2)
// {
// if (x < t->left->element)
// {
// SingleRotateLeftChild(t);
// }
// else
// DoubleRotateLeftChild(t);
// }
}
else if (x > t->element)
{
Insert(x, t->right);
Balance(t);
// if (GetHeight(t->right) - GetHeight(t->left) == 2)
// {
// if (t->right->element < x)
// {
// SingleRotateRightChild(t);
// }
// else
// DoubleRotateRightChild(t);
// }
}
else
;
t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
}
/**
* 有个小bug，弄了一天也没弄出来，可能问题在Balance()和指针的引用上
*
* @param x
* @param t
*/
template<typename Comparable>
void AVLTree<Comparable>::Remove(const Comparable &x, BinaryNode<Comparable> *&t)
{
static stack<BinaryNode<Comparable>*> tStack;/// 定义一个静态堆栈，存储访问结点的路径
int tSize = tStack.size();/// 得到栈的大小
if (t == NULL)
{
return;
}
else if (x < t->element)
{
tStack.push(t);
cout << "traverse through " << t->element << endl;
Remove(x, t->left);
}
else if (x > t->element)
{
tStack.push(t);
cout << "traverse through " << t->element << endl;
Remove(x, t->right);
}
else if (t->left != NULL && t->right != NULL)
{
tStack.push(t);
cout << "traverse through " << t->element << endl;
BinaryNode<Comparable>*& oldT = t->right;
while (oldT->left != NULL)
{
tStack.push(oldT);
cout << "traverse through " << oldT->element << endl;
oldT = oldT->left;
}
t->element = oldT->element;
Remove(t->element, t->right);
}
else
{
BinaryNode<Comparable>*& oldNode = t;
t = (t->left != NULL) ? t->left : t->right;
delete oldNode;
}
BinaryNode<Comparable>* tempStack;
tSize = tStack.size(); /// 更新堆栈大小
for (int i = 0; i < tSize; i++)
{
tempStack = tStack.top();/// 回溯访问结点
Balance(tempStack);/// 对每个结点做Balance处理
tStack.pop();/// 已经做过Balance处理的结点出栈
}/// 此处可以进一步优化
return ;
}
template<typename Comparable>
void AVLTree<Comparable>::SingleRotateLeftChild(BinaryNode<Comparable> *&k2)
{
BinaryNode<Comparable> *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = max(GetHeight(k2->left), GetHeight(k2->right)) + 1;
k1->height = max(GetHeight(k1->left), k2->height) + 1;
k2 = k1;
}
template<typename Comparable>
void AVLTree<Comparable>::SingleRotateRightChild(BinaryNode<Comparable> *&k1)
{
BinaryNode<Comparable> *k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1->height = max(GetHeight(k1->left), GetHeight(k1->right)) + 1;
k2->height = max(k1->height, GetHeight(k2->right)) + 1;
k1 = k2;
}
template<typename Comparable>
void AVLTree<Comparable>::DoubleRotateLeftChild(BinaryNode<Comparable> *&k3)
{
SingleRotateRightChild(k3->left);
SingleRotateLeftChild(k3);
}
template<typename Comparable>
void AVLTree<Comparable>::DoubleRotateRightChild(BinaryNode<Comparable> *&k1)
{
SingleRotateLeftChild(k1->right);
SingleRotateRightChild(k1);
}
/**
* 计算t的平衡因子，分为四种不同情况分别调用不同函数处理
*
* @param t 树根
*/
template<typename Comparable>
void AVLTree<Comparable>::Balance(BinaryNode<Comparable> *&t)
{
if (GetHeight(t->left) - GetHeight(t->right) == 2)
{
if (GetHeight(t->left->left) > GetHeight(t->left->right))
{
SingleRotateLeftChild(t);
}
else if (GetHeight(t->left->left) < GetHeight(t->left->right))
{
DoubleRotateLeftChild(t);
}
else
;
}
if (GetHeight(t->left) - GetHeight(t->right) == -2)
{
if (GetHeight(t->right->right) > GetHeight(t->right->left))
{
SingleRotateRightChild(t);
}
else if (GetHeight(t->right->right) < GetHeight(t->right->left))
{
DoubleRotateRightChild(t);
}
else
;
}
}
#endif /* _BINARYSEARCHTREE_H_ */
#define _BINARYSEARCHTREE_H_
#include <iostream>
#include <stack>
using namespace std;
/// 三种遍历方式
#define PREORDERTRAVERSE 0
#define INORDERTRAVERSE 1
#define POSTORDERTRAVERSE 2
/// 求两个元素的最大值
#define max(x, y) ((x > y) ? (x) : y)
/**
* @class BinaryNode
* @brief 树的结点，为了方便BST和AVL用了同一种结构。BST中所有结点的height域为默认值
*/
template<typename Comparable>
struct BinaryNode
{
Comparable element;
BinaryNode* left;
BinaryNode* right;
int height;
BinaryNode(const Comparable &theElement, BinaryNode *lt, BinaryNode *rt, const int theHeight = 0)
: element(theElement), left(lt), right(rt), height(theHeight) {}
};
/**
* @class BinarySearchTree
* @brief 实现了常见的删除，插入功能。并作为AVL树的基类
*/
template<typename Comparable>
class BinarySearchTree
{
public:
BinarySearchTree();
~BinarySearchTree();
BinaryNode<Comparable>*& GetRoot();
void BuildBinaryTree(Comparable *x, int length);
const Comparable& FindMin() const;
const Comparable& FindMax() const;
bool Contains(const Comparable &x) const;
bool IsEmpty() const;
void TraverseTree(int type);
void MakeEmpty();
virtual void Insert(const Comparable &x);
virtual void Remove(const Comparable &x);
private:
BinaryNode<Comparable> *root;
virtual void Insert(const Comparable &x, BinaryNode<Comparable> *&t) const;
virtual void Remove(const Comparable &x, BinaryNode<Comparable> *&t) const;
BinaryNode<Comparable>* FindMin(BinaryNode<Comparable> *&t) const;
BinaryNode<Comparable>* FindMax(BinaryNode<Comparable> *&t) const;
bool Contains(const Comparable &x, BinaryNode<Comparable> *&t) const;
void MakeEmpty(BinaryNode<Comparable> *&t);
void PreOrderTraverse(BinaryNode<Comparable> *&t);
void InOrderTraverse(BinaryNode<Comparable> *&t);
void PostOrderTraverse(BinaryNode<Comparable> *&t);
};
/**
* 构造函数，默认root=NULL
*
*
* @return
*/
template<typename Comparable>
BinarySearchTree<Comparable>::BinarySearchTree() : root(NULL){}
/**
* 析构函数
*
*
* @return
*/
template<typename Comparable>
BinarySearchTree<Comparable>::~BinarySearchTree()
{
MakeEmpty();
}
/**
* 得到根节点的引用
*
*
* @return 返回根节点的引用
*/
template<typename Comparable>
BinaryNode<Comparable>*& BinarySearchTree<Comparable>::GetRoot()
{
return root;
}
/**
* 建立BST树，通过数组的方式传入元素，调用Insert(x)函数
*
* @param x
* @param length
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::BuildBinaryTree(Comparable *x, int length)
{
for (int i = 0; i < length; ++i)
{
Insert(x[i]);
}
}
/**
* @return BST中的最小值
*/
template<typename Comparable>
const Comparable& BinarySearchTree<Comparable>::FindMin() const
{
return FindMin(root)->element;
}
/**
* @return BST中的最大值
*/
template<typename Comparable>
const Comparable& BinarySearchTree<Comparable>::FindMax() const
{
return FindMax(root)->element;
}
/**
* 测试x是否在BST中，调用私有函数Contains(x, root)
*
* @param x
*
* @return
*/
template<typename Comparable>
bool BinarySearchTree<Comparable>::Contains(const Comparable &x) const
{
return Contains(x, root);
}
/**
* 测试树是否为空
*
*
* @return
*/
template<typename Comparable>
bool BinarySearchTree<Comparable>::IsEmpty() const
{
if (root == NULL)
{
return true;
}
return false;
}
/**
* 以三种方式遍历树
*
* @param type 遍历树的方式
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::TraverseTree(int type)
{
if (type == PREORDERTRAVERSE)
{
cout << "PreOrderTraverse the tree:" << endl;
PreOrderTraverse(root);
cout << endl << "PreOrderTraverse ends." << endl;
}
if (type == INORDERTRAVERSE)
{
cout << "InOrderTraverse the tree:" << endl;
InOrderTraverse(root);
cout << endl << "InOrderTraverse ends." << endl;
}
if (type == POSTORDERTRAVERSE)
{
cout << "PostOrderTraverse the tree:" << endl;
PostOrderTraverse(root);
cout << endl << "InOrderTraverse ends." << endl;
}
}
/**
* 清空BST树
*
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::MakeEmpty()
{
MakeEmpty(root);
}
/**
* 向BST中插入一个元素
*
* @param x 待插入的元素
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::Insert(const Comparable &x)
{
Insert(x, root);
}
/**
* 从BST中删除一个元素
*
* @param x 被删除的元素
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::Remove(const Comparable &x)
{
Remove(x, root);
}
/**
* 向树根为t的树中插入一个元素
*
* @param x 待插入的元素
* @param t 树根
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::Insert(const Comparable &x, BinaryNode<Comparable> *&t) const
{
if (t == NULL)
{
t = new BinaryNode<Comparable>(x, NULL, NULL, -3);
}
else if (x < t->element)
{
Insert(x, t->left);
}
else if (x > t->element)
{
Insert(x, t->right);
}
else
; //dupicate; you can do something, of course
}
/**
* 从树根为t的树中删除元素
*
* @param x 被删除的元素
* @param t 树根
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::Remove(const Comparable &x, BinaryNode<Comparable> *&t) const
{
if (t == NULL)
{
return;
}
else if (x < t->element)
{
Remove(x, t->left);
}
else if (x > t->element)
{
Remove(x, t->right);
}
else if (t->left != NULL && t->right != NULL)
{
t->element = FindMin(t->right)->element;
Remove(t->element, t->right);
}
else
{
BinaryNode<Comparable> *oldNode = t;
t = (t->left != NULL) ? t->left : t->right;
delete oldNode;
}
}
template<typename Comparable>
BinaryNode<Comparable>* BinarySearchTree<Comparable>::FindMin(BinaryNode<Comparable> *&t) const
{
if (t != NULL)
{
while(t->left != NULL)
t = t->left;
}
return t;
}
template<typename Comparable>
BinaryNode<Comparable>* BinarySearchTree<Comparable>::FindMax(BinaryNode<Comparable> *&t) const
{
if (t != NULL)
{
while(t->right != NULL)
t = t->right;
}
return t;
}
template<typename Comparable>
bool BinarySearchTree<Comparable>::Contains(const Comparable &x, BinaryNode<Comparable> *&t) const
{
if (t == NULL)
{
return false;
}
else if (x < t->element)
{
return Contains(x, t->left);
}
else if (x > t->element)
{
return Contains(x, t->right);
}
else
return true;
}
template<typename Comparable>
void BinarySearchTree<Comparable>::MakeEmpty(BinaryNode<Comparable> *&t)
{
if (t != NULL)
{
MakeEmpty(t->left);
MakeEmpty(t->right);
delete t;
}
t = NULL;
}
/**
* 前序遍历
*
* @param t
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::PreOrderTraverse(BinaryNode<Comparable> *&t)
{
if (t != NULL)
{
cout << t->element << " ";
PreOrderTraverse(t->left);
PreOrderTraverse(t->right);
}
}
/**
* 中序遍历
*
* @param t
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::InOrderTraverse(BinaryNode<Comparable> *&t)
{
if (t != NULL)
{
InOrderTraverse(t->left);
cout << t->element << " ";
InOrderTraverse(t->right);
}
}
/**
* 后序遍历
*
* @param t
*/
template<typename Comparable>
void BinarySearchTree<Comparable>::PostOrderTraverse(BinaryNode<Comparable> *&t)
{
if (t != NULL)
{
PostOrderTraverse(t->left);
PostOrderTraverse(t->right);
cout << t->element << " ";
}
}
/**
* @class AVLTree
* @brief 由于AVLTree本身是一种改进的BST树，所以绝大多数特性继承自BST树。其中的Insert()和Remove方法和BST树中不同，因此在BST类中将此方法声明为virtual function
*/
template<typename Comparable>
class AVLTree : public BinarySearchTree<Comparable>
{
public:
AVLTree();
~AVLTree();
int GetHeight();
void Insert(const Comparable &x);
void Remove(const Comparable &x);
protected:
int GetHeight(BinaryNode<Comparable> *&t);
void Insert(const Comparable &x, BinaryNode<Comparable> *&t);
void Remove(const Comparable &x, BinaryNode<Comparable> *&t);
void SingleRotateLeftChild(BinaryNode<Comparable> *&k2);
void SingleRotateRightChild(BinaryNode<Comparable> *&k2);
void DoubleRotateLeftChild(BinaryNode<Comparable> *&k3);
void DoubleRotateRightChild(BinaryNode<Comparable> *&k3);
void Balance(BinaryNode<Comparable> *&t);
};
/**
* 构造函数，调用BST基类的构造函数
*
*
* @return
*/
template<typename Comparable>
AVLTree<Comparable>::AVLTree() : BinarySearchTree<Comparable>::BinarySearchTree()
{
// BinaryNode<Comparable>* root = BinarySearchTree<Comparable>::GetRoot();
// root = NULL;
}
/**
* 析构函数，调用基类的BST::MakeEmpty()
*
*
* @return
*/
template<typename Comparable>
AVLTree<Comparable>::~AVLTree()
{
BinarySearchTree<Comparable>::MakeEmpty();
}
/**
* 得到整棵AVL树的高度
*
*
* @return
*/
template<typename Comparable>
int AVLTree<Comparable>::GetHeight()
{
BinaryNode<Comparable>*& root = BinarySearchTree<Comparable>::GetRoot();
return GetHeight(root);
}
/**
* 向AVL中插入元素x
*
* @param x 待插入的元素
*/
template<typename Comparable>
void AVLTree<Comparable>::Insert(const Comparable &x)
{
BinaryNode<Comparable>*& root = BinarySearchTree<Comparable>::GetRoot();
Insert(x, root);
}
/**
* 从AVL中删除元素x
*
* @param x 被删除的元素
*/
template<typename Comparable>
void AVLTree<Comparable>::Remove(const Comparable &x)
{
BinaryNode<Comparable>*& root = BinarySearchTree<Comparable>::GetRoot();
Remove(x, root);
}
/**
* 得到结点t的高度
*
* @param t
*
* @return
*/
template<typename Comparable>
int AVLTree<Comparable>::GetHeight(BinaryNode<Comparable> *&t)
{
return t == NULL ? -1 : t->height;
}
template<typename Comparable>
void AVLTree<Comparable>::Insert(const Comparable &x, BinaryNode<Comparable> *&t)
{
if (t == NULL)
{
t = new BinaryNode<Comparable>(x, NULL, NULL);
}
else if (x < t->element)
{
Insert(x, t->left);
Balance(t);
// if (GetHeight(t->left) - GetHeight(t->right) == 2)
// {
// if (x < t->left->element)
// {
// SingleRotateLeftChild(t);
// }
// else
// DoubleRotateLeftChild(t);
// }
}
else if (x > t->element)
{
Insert(x, t->right);
Balance(t);
// if (GetHeight(t->right) - GetHeight(t->left) == 2)
// {
// if (t->right->element < x)
// {
// SingleRotateRightChild(t);
// }
// else
// DoubleRotateRightChild(t);
// }
}
else
;
t->height = max(GetHeight(t->left), GetHeight(t->right)) + 1;
}
/**
* 有个小bug，弄了一天也没弄出来，可能问题在Balance()和指针的引用上
*
* @param x
* @param t
*/
template<typename Comparable>
void AVLTree<Comparable>::Remove(const Comparable &x, BinaryNode<Comparable> *&t)
{
static stack<BinaryNode<Comparable>*> tStack;/// 定义一个静态堆栈，存储访问结点的路径
int tSize = tStack.size();/// 得到栈的大小
if (t == NULL)
{
return;
}
else if (x < t->element)
{
tStack.push(t);
cout << "traverse through " << t->element << endl;
Remove(x, t->left);
}
else if (x > t->element)
{
tStack.push(t);
cout << "traverse through " << t->element << endl;
Remove(x, t->right);
}
else if (t->left != NULL && t->right != NULL)
{
tStack.push(t);
cout << "traverse through " << t->element << endl;
BinaryNode<Comparable>*& oldT = t->right;
while (oldT->left != NULL)
{
tStack.push(oldT);
cout << "traverse through " << oldT->element << endl;
oldT = oldT->left;
}
t->element = oldT->element;
Remove(t->element, t->right);
}
else
{
BinaryNode<Comparable>*& oldNode = t;
t = (t->left != NULL) ? t->left : t->right;
delete oldNode;
}
BinaryNode<Comparable>* tempStack;
tSize = tStack.size(); /// 更新堆栈大小
for (int i = 0; i < tSize; i++)
{
tempStack = tStack.top();/// 回溯访问结点
Balance(tempStack);/// 对每个结点做Balance处理
tStack.pop();/// 已经做过Balance处理的结点出栈
}/// 此处可以进一步优化
return ;
}
template<typename Comparable>
void AVLTree<Comparable>::SingleRotateLeftChild(BinaryNode<Comparable> *&k2)
{
BinaryNode<Comparable> *k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = max(GetHeight(k2->left), GetHeight(k2->right)) + 1;
k1->height = max(GetHeight(k1->left), k2->height) + 1;
k2 = k1;
}
template<typename Comparable>
void AVLTree<Comparable>::SingleRotateRightChild(BinaryNode<Comparable> *&k1)
{
BinaryNode<Comparable> *k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1->height = max(GetHeight(k1->left), GetHeight(k1->right)) + 1;
k2->height = max(k1->height, GetHeight(k2->right)) + 1;
k1 = k2;
}
template<typename Comparable>
void AVLTree<Comparable>::DoubleRotateLeftChild(BinaryNode<Comparable> *&k3)
{
SingleRotateRightChild(k3->left);
SingleRotateLeftChild(k3);
}
template<typename Comparable>
void AVLTree<Comparable>::DoubleRotateRightChild(BinaryNode<Comparable> *&k1)
{
SingleRotateLeftChild(k1->right);
SingleRotateRightChild(k1);
}
/**
* 计算t的平衡因子，分为四种不同情况分别调用不同函数处理
*
* @param t 树根
*/
template<typename Comparable>
void AVLTree<Comparable>::Balance(BinaryNode<Comparable> *&t)
{
if (GetHeight(t->left) - GetHeight(t->right) == 2)
{
if (GetHeight(t->left->left) > GetHeight(t->left->right))
{
SingleRotateLeftChild(t);
}
else if (GetHeight(t->left->left) < GetHeight(t->left->right))
{
DoubleRotateLeftChild(t);
}
else
;
}
if (GetHeight(t->left) - GetHeight(t->right) == -2)
{
if (GetHeight(t->right->right) > GetHeight(t->right->left))
{
SingleRotateRightChild(t);
}
else if (GetHeight(t->right->right) < GetHeight(t->right->left))
{
DoubleRotateRightChild(t);
}
else
;
}
}
#endif /* _BINARYSEARCHTREE_H_ */
main.cpp:
#include <iostream>
#include "BinarySearchTree.h"
using namespace std;
int main(int argc, char *argv[])
{
int a[10] = {5, 9, 10, 1, 3, 6, 4, 7, 8, 2};
AVLTree<int> avl;
avl.BuildBinaryTree(a, 10);
avl.Insert(11);
avl.TraverseTree(0);
avl.Remove(9);
avl.TraverseTree(0);
avl.Remove(10);
avl.TraverseTree(0);
return 0;
}
#include "BinarySearchTree.h"
using namespace std;
int main(int argc, char *argv[])
{
int a[10] = {5, 9, 10, 1, 3, 6, 4, 7, 8, 2};
AVLTree<int> avl;
avl.BuildBinaryTree(a, 10);
avl.Insert(11);
avl.TraverseTree(0);
avl.Remove(9);
avl.TraverseTree(0);
avl.Remove(10);
avl.TraverseTree(0);
return 0;
}