/********************************************************************
* 建立一颗有序,并实现以下功能:
* 1.查找关键字
* 2.插入关键字
* 3.删除节点
* 4.先序遍历二叉树
* 5.中序遍历二叉树
* 6.后序遍历二叉树
作者:程凤伟
日期:2014-10-9
* *******************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define FALSE 0
#define TRUE 1
typedef int TElemType;
//创建一个树节点的结构体类型
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild; //左右孩子以及节点指针
}BiTNode,*BiTree;
BiTree CreateBiTree();
int SearchBST(BiTree T,TElemType e,BiTree f,BiTree *p);
int InsertBST(BiTree *T,TElemType e,BiTree f,BiTree *p);
int Delete(BiTree *p);
int DeleteBST(BiTree *T,TElemType e);
void PreOrderTraverse(BiTree T);
void InOrderTraverse(BiTree T);
void PostOrderTraverse(BiTree T);
// 创建一颗空树
BiTree CreateBiTree()
{
BiTNode *T;
T=NULL;
return T;
}
//查找二叉排序树
int SearchBST(BiTree T,TElemType e,BiTree f,BiTree *p)
{
// 在根指针T所指的二叉排序树中递归查找其关键字等于e的数据元素,若查找成功
// 则指针p指向该数据元素结点,并返回TRUE,否则指针p指向查找路径上访问的最后
// 一个节点,并返回FALSE。
if(T == NULL)
{ *p = f; printf("查找不成功, ");return FALSE;} //查找不成功
else if( e == T->data)
{ *p = T; printf("查找成功\n");return TRUE;} //查找成功
else if( e < T->data)
{
// printf("查找左子树 \t");
return SearchBST(T->lchild,e,T,p); //在左子树中继续查找
}
else if( e > T->data)
{
// printf("查找右子树\n");
return SearchBST(T->rchild,e,T,p); //在右子树中继续查找
}
}
int InsertBST(BiTree *T,TElemType e,BiTree f,BiTree *p)
{
//当二叉树中不存在关键字等于e的数据时,插入e并返回TRUE,否则返回FALSE
BiTree s;
if(SearchBST(*T,e,NULL,p)==FALSE) //查找不成功
{
s=(BiTree)malloc(sizeof(BiTNode));
s->data=e;
s->lchild=s->rchild=NULL;
if(!(*p)) {*T=s; printf("插入到根节点\n");} //被插入节点*s为新的根节点
else if(e < (*p)->data) {(*p)->lchild=s; printf(" 插入到左子树\n");} //被插入节点*s为左孩子
else if(e > (*p)->data) {(*p)->rchild=s; printf(" 插入到右子数\n");} //被插入节点*s为右孩子
return TRUE;
}
else return FALSE;
}
//删除一个节点 p,并重接它的左或右子树
int Delete(BiTree *p)
{
BiTree q,s;
if(!(*p)->rchild) //右子树为空需要重接它的左子树
{
q=*p;
*p=(*p)->lchild;
free(q);
}else if(!(*p)->lchild) //左子树为空需要重接它的右子树
{
q=*p;
*p=(*p)->rchild;
free(q);
}else //左右子数均不空
{
q=*p;
s=(*p)->lchild; //转向左子树
while(s->rchild)
{
q=s;
s=s->rchild; //向右走到尽头,q指向被删除节点的前驱
}
(*p)->data=s->data;
if(q!=(*p))
q->rchild=s->lchild; //重接*q的右子树
else q->lchild=s->lchild; //重接*q的左子树
free(s);
}
return TRUE;
}
int DeleteBST(BiTree *T,TElemType e)
{
//若二叉排序树T中存在关键字等于e的数据元素时,则删除该数据元素节点
//并返回TRUE,否则返回FALSE
BiTree *p;
if(!(*T)) { return FALSE;} //树为空或者不存在关键字等于e的数据元素
else {
if(e == (*T)->data) {p=T;return Delete(p);} //找到关键字等于数据e的元素
if(e < (*T)->data) { p=&((*T)->lchild);return DeleteBST(p,e); } //若数据e小于当前节点关键字,则进入当前节点的左子树查找,删除
else { p=&((*T)->rchild);return DeleteBST(p,e);} //若数据e大于当前节点关键字,则进入当前节点的右子树查找,删除
}
}
//先序遍历二叉树
void PreOrderTraverse(BiTree T)
{
if(T)
{
printf("%d\t",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
//中序遍历
void InOrderTraverse(BiTree T)
{
if(T)
{
InOrderTraverse(T->lchild);
printf("%d\t",T->data);
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiTree T)
{
if(T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%d\t",T->data);
}
}
int main(int argc, const char *argv[])
{
BiTree T,*T0,f,*p,p0;
// BiTNode t;
TElemType e;
T=CreateBiTree();
T0=&T;
p=&p0;
f=T;
printf("输入数据,查找并插入到二叉树中,遇到0则停止输入:\n");
while(1)
{
scanf("%d",&e);
if(e==0) break;
InsertBST(T0,e,f,p);
}
T=*T0;
printf(" 先序遍历二叉树的结果为:\n");
PreOrderTraverse(T);
printf("\n");
printf(" 中序遍历二叉树的结果为:\n");
InOrderTraverse(T);
printf("\n");
printf(" 后序遍历二叉树的结果为:\n");
PostOrderTraverse(T);
printf("\n");
printf("请输入数据,在二叉树中查找并删除,遇到0则停止输入:\n");
while(1)
{
scanf("%d",&e);
if(e==0)
break;
if(DeleteBST(T0,e)==FALSE)
printf("不存在等于e的关键字,删除失败\n");
else printf("找到等于e的关键字,删除成功\n");
}
T=*T0;
printf(" 先序遍历二叉树的结果为:\n");
PreOrderTraverse(T);
printf("\n");
printf(" 中序遍历二叉树的结果为:\n");
InOrderTraverse(T);
printf("\n");
printf(" 后序遍历二叉树的结果为:\n");
PostOrderTraverse(T);
printf("\n");
return 0;
}