带索引的二叉搜索树

2021年1月25日发(作者：lives)
带索引的二叉搜索树

//file:indexedBSTree.h
#pragma once

#include

template
class IndexedBSTree : public BSTree
{
public:

void Create();

bool Search(const K& k,E& e)const;

bool IndexSearch(int k,E& e)const;

IndexedBSTree& Insert(const E& e);

IndexedBSTree& Delete(const K& k,E& e);

IndexedBSTree& IndexDelete(int k,E& e);

void Ascend();

void IndexOutput();
private:

static void OutputLeftSize(BinaryTreeNode *t);
};

template
void IndexedBSTree::Create()
{//
产生一个空的带索引的二叉搜索树


root = 0;
}

template
bool IndexedBSTree::Search(const K& k,E& e) const
{//
将关键值为
k
的元素返回到
e
中 ；如果操作失败返回
false
，否则返回
true

return BSTree::Search(k,e);
}

template
bool IndexedBSTree::IndexSearch(int k,E& e) const
{//
将第
k
个元素返回到
e
中


if(!root)


return false;

BinaryTreeNode *p = root;

while(p)

{


if(k < p->LeftSize)



p = p->LeftChild;


else if(k > p->LeftSize)


{



k -= p->LeftSize;



p = p->RightChild;


}


else


{



e = p->data;



return true;


}

}

return false;
}

template
IndexedBSTree& IndexedBSTree::Insert(const E& e)
{

BSTree::Insert(e);

BinaryTreeNode *t = root;

while(t)

{


if(e < t->data)


{



t->LeftSize++;



t = t->LeftChild;


}


else if(e > t->data)



t = t->RightChild;


else


{



t->LeftSize = 1;



return *this;


}

}
}

template
IndexedBSTree& IndexedBSTree::Delete(const K& k,E& e)
{//
删除关键值为
k
的元素并且将其返回到
e
中



//
将
p
指向关键值为
k
的节点













































BinaryTreeNode *p = root,//
搜索指针


*pp = 0;//p
的父节点指针

while(p && p->data != k)
{//
移动到
p
的孩子


pp = p;

if(k < p->data)

{


p = p->LeftChild;

}

else


p = p->RightChild;
}

if(!p)

throw BadInput();//
没有关键值为
k
的元素

e = p->data;//
保存欲删除的元素

BinaryTreeNode *t = root;//
搜索指针

while(t && t->data != k)
{//
移动到
p
的孩子


if(k < t->data)

{


t->LeftSize--;


t = t->LeftChild;

}

else


t = t->RightChild;
}
//
对树进行重构

//
处理
p
有两个孩子的情形

if(p->LeftChild && p->RightChild)
{//
两个孩子


//
转换成有
0
或
1
个孩子的情形


//
在
p
的左子树中寻找最大元素


BinaryTreeNode *s = p->LeftChild,*ps = p;//s
的父节点


while(s->RightChild)

{//
移动到较大的元素



ps = s;


s = s->RightChild;

}

p->LeftSize = p->LeftSize - 1;//
修改所删除元素的索引值



//
将最大元素从
s
移动到
p


p->data = s->data;


p = s;


pp = ps;

}


//p
最多有一个孩子


//
在
c
中保存孩子指针


BinaryTreeNode *c;

if(p->LeftChild)


c = p->LeftChild;

else



c= p->RightChild;


//
删除
p

if(p == root)


root = c;

else

{//p
是
pp
的左孩子还是
pp
的右孩子？



if(p == pp->LeftChild)


{



pp->LeftChild = c;


}


else



pp->RightChild = c;

}

delete p;


return *this;
}

template
IndexedBSTree& IndexedBSTree::IndexDelete(int k,E& e)
{//
删除第
k
个元素并将其返回到
e
中


BinaryTreeNode *p = root,




*pp = 0;//
指向第
k
个元素的父节点


//
寻找删除点


while(p && k != p->LeftSize)

{


pp = p;


if(k < p->LeftSize)


{



p = p->LeftChild;


}













































else if(k > p->LeftSize)

{


k -= p->LeftSize;


p = p->RightChild;

}
}

if(!p)

throw BadInput();//
没有关键值为
k
的元素

e = p->data;//
保存欲删除的元素

//
调整
LeftSize
值

BinaryTreeNode *t = root;//
搜索指针

while(p && k != t->LeftSize)
{//
移动到
t
的孩子


if(k < t->LeftSize)

{


t = t->LeftChild;

}

else if(k > p->LeftSize)

{


k -= t->LeftSize;


t = t->RightChild;

}
}
//
对树进行重构

//
处理
p
有两个孩子的情形

if(p->LeftChild && p->RightChild)
{//
两个孩子


//
转换成有
0
或
1
个孩子的情形


//
在
p
的左子树中寻找最大元素


BinaryTreeNode *s = p->LeftChild,*ps = p;//s
的父节点


while(s->RightChild)

{//
移动到较大的元素



ps = s;


s = s->RightChild;

}





p->LeftSize = p->LeftSize - 1;//
修改所删除元素的索引值

//
将最大元素从
s
移动到
p
p->data = s->data;
p = s;
pp = ps;

}


//p
最多有一个孩子


//
在
c
中保存孩子指针


BinaryTreeNode *c;

if(p->LeftChild)


c = p->LeftChild;

else



c= p->RightChild;


//
删除
p

if(p == root)


root = c;

else

{//p
是
pp
的左孩子还是
pp
的右孩子？



if(p == pp->LeftChild)


{



pp->LeftChild = c;


}


else



pp->RightChild = c;

}

delete p;


return *this;
}

template
void IndexedBSTree::Ascend()
{//
按照关键值的升序排列输出所有元素


InOutput();
}


template
void IndexedBSTree::IndexOutput()
{//
中序遍历，输出节点元素的索引值


InOrder(OutputLeftSize,root);

cout<}

template
void IndexedBSTree::OutputL eftSize(BinaryTreeNode *t)
{//
输出节点元素的索引值


cout<LeftSize<<' ';
}

//file:BSTree.h
#pragma once

#include

template
class BSTree : public BinaryTree
{
public:

bool Search(const K& k,E& e)const;

BSTree& Insert(const E& e);

BSTree& Delete(const K& k,E& e);

void Ascend() {InOutput();}

void traversalBSTree(int a[]);



void traversalBSTree0(BinaryTreeNode *t,int &pos,int a[]);

BSTree& DeleteMax(E& x);
};

template
bool BSTree::Search(const K& k,E& e) const
{//
搜索与
k
匹配的元素


//
指针
p
从树根开始进行查找


if(!root)


return false;

BinaryTreeNode *p = root;

while(p)//
检查
p->data

{


if(k < p->data)



p = p->LeftChild;


else if(k > p->data)



p = p->RightChild;


else



{



e = p->data;



return true;


}

}

return false;
}

template
BSTree& BSTree::Insert(const E& e)
{//
如果不出现重复，则插入
e

BinaryTreeNode *p = root,//
搜索指针



*pp = 0;

//
寻找插入点


while(p)

{//
检查
p->data


pp = p;


//
将
p
移向孩子节点



if(e < p->data)



p = p->LeftChild;


else if(e > p->data)



p = p->RightChild;


else



throw BadInput();//
出现重复


}


//
为
e
建立一个节点，并将该节点连接至
pp

BinaryTreeNode *r = new BinaryTreeNode (e);

if(root)

{//
树非空



if(e < pp->data)



pp->LeftChild = r;


else



pp->RightChild = r;

}

else//
插入到空树



root = r;


return *this;
}

template
BSTree& BSTree::Delete(const K& k,E& e)
{//
删除关键值为
k
的元素，并将其放入
e


//
将
p
指向关键值为
k
的节点


BinaryTreeNode *p = root,//
搜索指针



*pp = 0;//p
的父节点指针


while(p && p->data != k)

{//
移动到
p
的孩子



pp = p;


if(k < p->data)














































p = p->LeftChild;

else


p = p->RightChild;
}
if(!p)

throw BadInput();//
没有关键值为
k
的元素

e = p->data;//
保存欲删除的元素

//
对树进行重构

//
处理
p
有两个孩子的情形

if(p->LeftChild && p->RightChild)
{//
两个孩子


//
转换成有
0
或
1
个孩子的情形


//
在
p
的左子树中寻找最大元素


BinaryTreeNode *s = p->LeftChild,*ps = p;//s
的父节点


while(s->RightChild)

{//
移动到较大的元素



ps = s;


s = s->RightChild;

}




}
//
将最大元素从
s
移动到
p
p->data = s->data;
p = s;
pp = ps;
//p
最多有一个孩子

//
在
c
中保存孩子指针

BinaryTreeNode *c;
if(p->LeftChild)

c = p->LeftChild;
else


c= p->RightChild;
//
删除
p
if(p == root)

root = c;
else
{//p
是
pp
的左孩子还是
pp
的右孩子？


if(p == pp->LeftChild)


pp->LeftChild = c;

else



pp->RightChild = c;

}

delete p;


return *this;
}

template
void BSTree::traversalBSTree(int a[])
{


int pos = 0;

traversalBSTree0(root,pos,a);
}

template
void BSTree::traversalBSTree0(BinaryTreeNode *t,int &pos,int a[])
{






if (!t)










return;








traversalBSTree0(t->LeftChild, pos, a);






a[pos++] = t->data;






traversalBSTree0(t->RightChild, pos, a);
}

template
BSTree& BSTree::DeleteMax(E& x)
{



if (!root)





throw OutOfBounds();





BinaryTreeNode *p = root,





















*pp = 0;




while (p->RightChild)




{






pp = p;






p = p->RightChild;



}




x = p->data;




if (p == root)





root = p->LeftChild;



else





pp->RightChild = p->LeftChild;




delete p;




return *this;
}

//file:binaryTree.h
#ifndef _BINARYTREE_H_
#define _BINARYTREE_H_

#include
#include
#include

int _count = 0;

template
class BinaryTree
{

template

friend class IndexedBSTree;

template

friend class BSTree;

public:


BinaryTree() {root = 0;}


~BinaryTree() {}


bool IsEmpty() const {return ((root) ? false : true);}


bool Root(T& x) const;


void SetRoot(BinaryTreeNode* t) {root = t;}


BinaryTreeNode* GetRoot() {return root;}


void MakeTree(const T& element,BinaryTree& left,BinaryTree& right);


void BreakTree(T& element,BinaryTree& left,BinaryTree& right);


void PreOrder(void (*Visit)(BinaryTreeNode *u))


{PreOrder(Visit,root);}


void InOrder(void (*Visit)(BinaryTreeNode *u))


{InOrder(Visit,root);}


void PostOrder(void (*Visit)(BinaryTreeNode *u))


{PostOrder(Visit,root);}


void LevelOrder(void (*Visit)(BinaryTreeNode *u));


void PreOutput()


{PreOrder(Output,root);cout<

void InOutput()


{InOrder(Output,root);cout<

void PostOutput()


{PostOrder(Output,root);cout<

void LevelOutput()


{LevelOrder(Output);cout<

void Delete()


{PostOrder(Free,root);root = 0;}


int Height() const


{return Height(root);}


int Size();


BinaryTreeNode* search(T element) {return search(element, root);}


BinaryTreeNode* copy(BinaryTreeNode * t);



int NumLeaves()


{return CountLeaf(root);}


void Swap()


{Swap0(root);}


bool Compare(BinaryTree& X)


{return Compare1(root,);}



bool IsHBLT()


{return IsHBLT(root);}




private:


BinaryTreeNode *root;//
根节点指针




void PreOrder(void (*Visit)(BinaryTreeNode *u),BinaryTreeNode *t);


void InOrder(void (*Visit)(BinaryTreeNode *u),BinaryTreeNode *t);


void PostOrder(void (*Visit)(BinaryTreeNode *u),BinaryTreeNode *t);


static void Output(BinaryTreeNode *t);


static void Free(BinaryTreeNode *t) {delete t;}


int Height(BinaryTreeNode *t) const;


static void Add1(BinaryTreeNode *t) {_count++;}


//int Count(BinaryTreeNode *t) const;


BinaryTreeNode* search(T& element,BinaryTreeNode *t);


int CountLeaf(BinaryTreeNode *t);


void Swap0(BinaryTreeNode *t);


bool Compare1(BinaryTreeNode *p,BinaryTreeNode *t);



bool IsHBLT(BinaryTreeNode * t);
};

template