数据结构二叉排序树的实现 (用顺序和二叉链表作存储结构 )课程设计

node(int i):data(i),left(NULL),right(NULL){}

void inorder(node *&root) //中序遍历，符合升序输出 {

if(root!=NULL) {

inorder(root->left); cout<data<<' '; inorder(root->right); } }

void insert(node *&ptr,int item) //在查找树中插入元素 {

if(ptr==NULL) ptr=new node(item); else if(itemdata) insert(ptr->left,item); else insert(ptr->right,item); }

node *find(node *&ptr,int item) //在查找树中查找元素,找到返回所在结点指针，找不到返回空指针。 {

if(ptr==NULL)

return NULL; if(ptr->data==item) return ptr; else if(itemdata) find(ptr->left,item); else find(ptr->right,item); }

node *&findy(node *&ptr,int item) //在查找树中查找肯定存在的元素,并返回其引用 {

if(ptr->data==item) return ptr; else if(itemdata) findy(ptr->left,item); else findy(ptr->right,item); }

node* rl(){return left;} node* rr(){return right;}

void dele(node *&ptr) //删除值为item所在结点 {

if(ptr->rl()==NULL&&ptr->rr()==NULL)

ptr=NULL;

else if(ptr->rr()==NULL) ptr=ptr->rl(); else

ptr=ptr->rr(); } private: int data;

node *left; //左孩子结点 node *right; //右孩子结点 }; int main() { int t,i=0,j;

cout<<\ 10计科一班 杨 旭（1010311114）\ cout<<\二叉排序树T的输入:\ cout<<\输入数字个数(结点个数):\ cin>>t;

cout<<\输入\个数字，数字之间用空格隔开:\ cin>>j;

node *x=new node(j);

for(;i>j; x->insert(x,j); }

cout<<\中序遍历为:\

x->inorder(x); //作中序遍历 cout<<\

cout<<\二叉排序树T的元素查找和删除:\ cout<<\输入操作(当输入-1时程序结束):\ cin>>j; while(j!=-1) {

node *t=x->find(x,j); //定位结点 if(t!=NULL) {

node *&y=x->findy(x,j); x->dele(y); cout<<\中序遍历为:\ x->inorder(x); }