#include "binTree.h"
#include <stdio.h>
#include <stdlib.h>
binTree emptyBinTree()
{
binTree t=malloc(sizeof(*t));
t->data=0;
t->leftChild=t->rightChild=NULL;
return t;
}
binTree newBinTree(int key)
{
binTree t=malloc(sizeof(*t));
t->data=key;
t->leftChild=t->rightChild=NULL;
return t;
}
binTree search(binTree root,int key)
{
if(!(root->data))
return NULL;
else
{
if(key==root->data)
return root;
if(key<root->data)
return search(root->leftChild,key);
return search(root->rightChild,key);
}
}
binTree modifiedSearch(binTree tree,int key)
{
binTree t=tree;
if(t->data)
{
while(t->leftChild||t->rightChild)
{
if(key==t->data)
t=NULL;
else
if(key<t->data&&t->leftChild)
t=t->leftChild;
else
if(key>t->data&&t->rightChild)
t=t->rightChild;
else
break;
}
}
return t;
}
void binTreeInsert(binTree t,int key)
{
binTree ptr=newBinTree(key);
binTree temp=modifiedSearch(t,key);
if(temp->data)
{
if(key<temp->data)
temp->leftChild=ptr;
else
temp->rightChild=ptr;
}
else
temp->data=ptr->data;
}
void binTreeDelete(binTree t,int key)
{
binTree a=emptyBinTree();
binTree b=emptyBinTree();
t=search(t,key);
if(t->leftChild==NULL&&t->rightChild==NULL)
{
t=NULL;
free(t);
}
else
{
if(t->leftChild==NULL)
{
b=t;
t=t->rightChild;
b->data=0;
}
if(t->rightChild==NULL)
{
b=t;
t=t->leftChild;
b->data=0;
}
else
{
a=t;
b=t->leftChild;
while(b->rightChild)
{
a=b;
b=b->rightChild;
}
a->data=b->data;
if(a!=t)
t->rightChild=b->leftChild;
else
t->leftChild=b->leftChild;
b->data=0;
}
}
}
void binTreeVisit(binTree t)
{
printf("%4d",t->data);
}
void binTreeInorder(binTree t,visitTy visit)
{
binTree a=t;
if(a)
{
binTreeInorder(a->leftChild,visit);
if(a->data)
visit(a);
binTreeInorder(a->rightChild,visit);
}
}
void swap(int *pm,int *pn) /*必须用指针进行交换*/
{
int temp;
temp=*pm;
*pm=*pn;
*pn=temp;
}
评论1