数据结构二叉排序树操作源代码知识分享

数据结构二叉排序树

操作源代码

精品资料

数据结构二叉排序树操作

源代码：

#include using namespace std; #define TRUE 1; #define FALSE 0; typedef int T;

const maxsize=50;

template struct Node { T key; /*.....*/ };

template struct bitree { Node data; bitree *lchild; bitree *rchild; };

template class BSTree {

public: Node *ST;

int len; //无素个数 bitree *t; //根指针

bitree *f; //根指针的双亲指针

bitree *p; //指向查找路径上最后访问的节点 BSTree();//构造函数

仅供学习与交流，如有侵权请联系网站删除 谢谢2

精品资料

~BSTree();//析构函数

void SearchBST(bitree *t,T key);//二叉排序树查找 void InsertBST(bitree *(&t),Node e);//元素插入 int DeleteBST(bitree *(&t),T key);//二叉排序树中元素删除 int Delete(bitree *(&p));//

void DeleteElem(T key);//查找表元素删除 void InDisplay(bitree *t);//中序遍历二叉排序树 void Display();//查找表显示

};

template BSTree::BSTree() {//构造函数，初始化查找表

ST=new Node[maxsize];//顺序存放查找表 len=0;

t=NULL;//查找树初始化

}

template BSTree::~BSTree() {//析构函数，销毁查找表 delete [] ST; len=0; delete t;

cout<<\成功销毁二叉排序树\\n\

}

template

void BSTree::SearchBST(bitree *t,T key) {//元素查找

if(t==NULL || key==t->data.key)

仅供学习与交流，如有侵权请联系网站删除 谢谢3

精品资料

{

if(key==t->data.key) else

cout<<\不存在\的节点\

cout<<\找到\的节点\

} else if(keydata.key) SearchBST(t->lchild,key); else SearchBST(t->rchild,key); }

template

void BSTree::InsertBST(bitree *(&t),Node e) {//元素插入

ST[len]=e; len++; p=t; while(p) { if(p->data.key==e.key) {

cout<<\二叉排序树中已经存在值为:\的节点\\n\exit(1); } f=p;

if(e.keydata.key) p=p->lchild; else p=p->rchild; p=new bitree; p->data=e;

p->lchild=p->rchild=NULL; if(t==NULL) t=p; else { if(e.keydata.key) f->lchild=p; else

仅供学习与交流，如有侵权请联系网站删除 谢谢4

精品资料

f->rchild=p; } } }

template

int BSTree::DeleteBST(bitree *(&t),T key) {// 元素删除

if(!t) {

cout<<\二叉树为空,无法删除\\n\

return FALSE; } else { if(key==t->data.key) return Delete(t); else if(keydata.key) return DeleteBST(t->lchild,key); else return DeleteBST(t->rchild,key); } }

template

int BSTree::Delete(bitree *(&p)) { bitree *q,*s; if(!p->rchild) { q=p; p=p->lchild; delete q;

cout<<\成功删除\

}

else if(!p->lchild) { q=p; p=p->rchild; delete q;

cout<<\成功删除\

仅供学习与交流，如有侵权请联系网站删除 谢谢5