二叉搜索树BSTree
2018年04月06日
⁄ 综合
⁄ 共 4786字 ⁄ 字号
小 中 大
// Binary_Search_Tree.cpp : Defines the entry point for the console application.
//二叉查找树：对于任何结点x,其左子树的关键值最大不超过key[x],右子树的关键值最小不超过key[x]
//某一结点的后继：如果关键值不同，某一结点的后继x,即大于key[x]中的最小的一个。
//
//
//
#include "stdafx.h"
#include <iostream>
#include <assert.h>
//#define CRTDBG_MAP_ALLOC//用于检查内存是否泄露
//#include <stdlib.h>
//#include <crtdbg.h>
template<class T>
class BSTree...{
struct Link...{
T key;
Link* right;
Link* left;
Link* parent;
Link(T data, Link* r, Link* l, Link* p):
key(data),right(r),left(l),parent(p)...{}
};
Link* root;
public:
BSTree(T ndata,Link* p, Link* q, Link* e):
root(new Link(ndata, p, q, e))...{}
BSTree(T a[],int size):root(new Link(a[0],NULL,NULL,NULL))
...{
for(int i = 1; i < size; i++ )
TreeInsert(a[i]);
}
void TreeInsert(T data_/**//*Link* z)*/)
...{
Link* z = new Link(data_,NULL,NULL,NULL);
Link* y = NULL;
Link* x = root;
while(x != NULL)
...{
y = x; //y作为x的父节点
if(z->key < x->key)
x = x->left;
else
x = x->right;
}
z->parent= y;//父指针只向父结点
if(y == NULL)
root = z; //空树
else if((z->key) < (y->key))//当y不为空的时候
y->left = z;//父结点指向当前插入结点
else
y->right = z;
}
void TreeDeleteNode(T inputdata)
...{
assert(TreeSearchNumber(root, inputdata)->key == inputdata);//查找看有没有值和同结点指示的一样
Link* z = TreeSearchNumber(root, inputdata);//找到此结点
Link* y = NULL;
Link* x = NULL;
if((z->left == NULL) || (z->right ==NULL))
y = z;//算法确定要删除节点y,该结点y或者是输入结点z(如果z至多只有一个子女)
else//上面语句y=z代表代表两种情况，要么是左子女，要么是右子女。下面一句代表有两个子女都存在的情况。
y = TreeSuccessor(z);//或是z的后继(如果z有两个子女)，而后继本身至多有一个子女。
if( y->left != NULL)//x被置为y的非NULL子女，或当y无子女被置为NULL。
x = y->left;
else
x = y->right;
if( x != NULL)//当y的非空子女不为空时，让子女的父指针指向y的父指针
x->parent = y->parent;
if( y->parent == NULL)//父结点为空，那么y就是根结点。
root = x;//让y的子女结点作为根结点
else
...{ if (y==(y->parent->left))//看看y是不是左结点。
y->parent->left = x;//让y的父结点的left指向x
else
y->parent->right = x;//否则，right指向x
if(y != z)
z->key = y->key;
}
delete y;
}
Link* TreeSearchNumber(Link* x, T k)
...{
if( x == NULL || k == x->key )
return x;
if( k < x->key )
return TreeSearchNumber(x->left, k);
else
return TreeSearchNumber(x->right, k);
}
Link* TreeMinIMUM(Link* x )
...{
while(x->left != NULL)
x = x->left;
return x;
}
Link* TreeMaxIMUM(Link* x)
...{
while((x->right) != NULL)
x = x->right;
return x;
}
Link* TreeSuccessor(Link* x)//存在两种情况:
...{
if (x->right != NULL)//如果结点x的右子树非空，则x的后继即右子树中的最左的结点。
return TreeMinIMUM(x->right) ;
Link* y = x->parent;//如果结点x的右子树为空，且x有一个后继y，则y是x的最低祖先结点，
while( (y != NULL) && (x == x->right))//且y的左儿子也是x的祖先票篇 p154,p155《算法导论》
...{
x = y;
y = y->parent;
}
return y;
}
void PrintTree(Link*x)
...{
if(x)
...{
std::cout<<x->key<<std::endl;
PrintTree(x->left);
PrintTree(x->right);
}
}
Link*Get(void)
...{
return root;
}
void DeleteTree(Link* x)
...{
if(x)
...{
DeleteTree(x->left);
DeleteTree(x->right);
delete x;
x = NULL;
}
}
~BSTree()
...{
DeleteTree(root);
}
};
int main(int argc, char* argv[])
...{
BSTree<int>m(15,NULL,NULL,NULL);
m.TreeInsert(3);
m.TreeInsert(5);
m.TreeInsert(12);
m.TreeInsert(10);
m.TreeInsert(13);
m.TreeInsert(6);
m.TreeInsert(7);
m.TreeInsert(16);
m.TreeInsert(20);
m.TreeInsert(18);
m.TreeInsert(23);
m.PrintTree(m.Get());
//std::cout<<m.TreeMaxIMUM(m.Get())->key<<std::endl;
//std::cout<<m.TreeMinIMUM(m.Get())->key<<std::endl;
// m.PrintTree(m.Get());
//_CrtDumpMemoryLeaks();//用于检查内存是否泄露
m.TreeDeleteNode(5);
std::cout<<"********"<<std::endl;
// std::cout<<m.TreeSearchNumber(m.Get(),678)->key<<std::endl;
// std::cout<<m.TreeSearchNumber(m.Get(),45)->key<<std::endl;
// std::cout<<m.TreeSearchNumber(m.Get(),234)->key<<std::endl;
// std::cout<<m.TreeSearchNumber(m.Get(),34)->key<<std::endl;
// std::cout<<m.TreeSearchNumber(m.Get(),100)->key<<std::endl;
m.PrintTree(m.Get());
std::cout<<"----(_________)---"<<std::endl;
int a[8] = ...{4566,89,34,23,3,1,2,90008};
BSTree<int>n(a,8);
n.PrintTree(n.Get());
return 0;
}