| 12345678910 二叉排序树
//////////////////////////////////////////////////////////////////////////
// File: btree_sort.h
// Author: centaurus
//////////////////////////////////////////////////////////////////////////
#ifndef __BTREE_SORT_H__
#define __BTREE_SORT_H__
#include
using namespace std;
int a[10] = {5, 6, 4, 7, 3, 9, 2, 10, 8, 1};
const int SIZE = 10;
template
class BTreeSort
{
private:
typedef struct BTreeNode
{
T value;
struct BTreeNode *lchild;
struct BTreeNode *rchild;
}BTreeNode;
typedef enum Flag
{
HEAD, LCHILD, RCHILD
}Flag;
BTreeNode *head;
int node_num;
bool Search(BTreeNode *node, T v, BTreeNode *front, BTreeNode **front_store, Flag flag, Flag *flag_store);
void PreOrderTraverse(BTreeNode *head);
public:
BTreeSort();
~BTreeSort();
void Add(int v);
void Show();
void Del(int v);
};
template
bool BTreeSort::Search(BTreeNode *node, T v, BTreeNode *front, BTreeNode **front_store, Flag flag, Flag *flag_store)
{
if(node == NULL)
{
*flag_store = flag;
*front_store = front;
return false;
}
if(node->value == v)
{
*flag_store = flag;
*front_store = front;
return true;
}
if(v > node->value)
return Search(node->rchild, v, node, front_store, RCHILD, flag_store);
else
return Search(node->lchild, v, node, front_store, LCHILD, flag_store);
}
template
BTreeSort::BTreeSort()
{
head = NULL;
node_num = 0;
for(int i = 0; i < SIZE; i++)
{
Add(a[i]);
}
}
template
void BTreeSort::Add(int v)
{
BTreeNode *fstore = NULL;
Flag f = HEAD;
if(Search(head, v, NULL, &fstore, HEAD, &f)==false)
{
if(f == HEAD)
{
head = new BTreeNode;
head->value = v;
head->lchild = head->rchild = NULL;
node_num++;
}
else
{
if(f == RCHILD)
{
fstore->rchild = new BTreeNode;
fstore->rchild->value = v;
fstore = fstore->rchild;
fstore->lchild = fstore->rchild = NULL;
}
else
{
fstore->lchild = new BTreeNode;
fstore->lchild->value = v;
fstore = fstore->lchild;
fstore->lchild = fstore->rchild = NULL;
}
node_num++;
}
}
}
template
void BTreeSort::PreOrderTraverse(BTreeNode *head)
{
if(head != NULL)
{
cout << head->value << endl;
PreOrderTraverse(head->lchild);
PreOrderTraverse(head->rchild);
}
return;
}
template
void BTreeSort::Show()
{
cout << "NodeNum:" << node_num << endl;
cout << "PreOrderShow:" << endl;
PreOrderTraverse(head);
}
template
void BTreeSort::Del(int v)
{
BTreeNode *fstore = NULL;
BTreeNode *del_node = NULL;
BTreeNode *p = NULL;
Flag f = HEAD;
if(Search(head, v, NULL, &fstore, HEAD, &f) == true)
{
if(f == LCHILD)
{
del_node = fstore->lchild;
}
else
if(f == RCHILD)
{
del_node = fstore->rchild;
}
else
{
del_node = head;
}
if(del_node->lchild == NULL && del_node->rchild != NULL)
{
if(f == LCHILD)
{
fstore->lchild = del_node->rchild;
}
else
if(f == RCHILD)
{
fstore->rchild = del_node->rchild;
}
else
{
head = del_node->rchild;
}
cout << del_node->value << endl;
delete del_node;
}
else
if(del_node->lchild != NULL && del_node->rchild == NULL)
{
if(f == LCHILD)
{
fstore->lchild = del_node->lchild;
}
else
if(f == RCHILD)
{
fstore->rchild = del_node->lchild;
}
else
{
head = del_node->lchild;
}
cout << del_node->value << endl;
delete del_node;
}
else
if(del_node->lchild != NULL && del_node->rchild != NULL)
{
p = del_node->lchild;
fstore = del_node;
cout << del_node->value << endl;
while(p->rchild != NULL)
{
fstore = p;
p = p->rchild;
}
if(p != del_node->lchild)
{
del_node->value = p->value;
fstore->rchild = p->lchild;
}
else
{
del_node->value = p->value;
del_node->lchild = p->lchild;
}
delete p;
}
else //无左右子树
{
if(f == LCHILD)
fstore->lchild = NULL;
else
if(f == RCHILD)
fstore->rchild = NULL;
else
head = NULL;
cout << del_node->value << endl;
delete del_node;
}
node_num--;
}
}
template
BTreeSort::~BTreeSort()
{
cout << "DeleteOrder:" << endl;
for(int i = 0; i < SIZE; i++)
{
Del(a[i]);
}
}
#endif
//////////////////////////////////////////////////////////////////////////
// File: btree_sort.h
// Author: centaurus
//////////////////////////////////////////////////////////////////////////
#include
using namespace std;
#include "btree_sort.h"
void main()
{
BTreeSort test;
test.Show();
} |
