数据结构课程设计（C版语言）二叉排序树算法

内容：编写算法建立一颗二叉排序树，输出该二叉树的先序和中序遍历序列；能够删除
二叉树的任意节点，并输出删除后的二叉排序树的先序中序遍历序列。
要求：能够按照要求建立不同的二叉排序树，数据可自定。
一定要用C语言编
直接编译通过再追加50分！！！

举报该问题

推荐答案 2011-01-17

下面的程序包含了树二叉树的所有操作
在二叉树的应用中有二叉排序树。
都是C语言，只不过用了C++的cin(输入)和cout（输出）,因为这两个不需要格式控制符。
//建一个工程：包含头文件：bittree.h Cpp文件：bittree.cpp main函数:main.cpp
编译运行就可以了。

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//头文件 bittree.h
#ifndef _DEF
#define _DEF
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
#define TURE 1
#define OK 1
#define FALSE 0
#define ERROR 0
#define INFEASIBLE -1//不可实行的
#define OVERFLOW -2
typedef int stadus;
typedef char Telemtype;
//typedef int Telemtype2;//为了二叉排序树的创建
typedef char ElemType;
#define STACK_SIZE 100;
#define STACKINCREMENT 10;

//二叉树
typedef struct bitnode{
Telemtype data;
struct bitnode *lchild,*rchild;
}BitNode,*BitTree;
extern stadus CreateBitTree(BitTree &T);
extern stadus PreOrderTraverse(BitTree T);
extern stadus InOrderTraverse(BitTree T);
extern stadus PostOrderTraverse(BitTree T);

typedef BitNode selemtypechar;
typedef BitTree selemtypechar2;

// 栈
typedef struct SqStack{
selemtypechar2 *base;
selemtypechar2 *top;
int stacksize;
}sqstack;
extern stadus initstackC(sqstack &S);
extern stadus gettopC(sqstack S,selemtypechar2 &e);
extern stadus pushC(sqstack &S,selemtypechar2 e);
extern stadus popC(sqstack &S,selemtypechar2 &e);
extern stadus destroyC(sqstack &S);//销毁
extern stadus clearC(sqstack &S);//置空
extern stadus stackempty(sqstack S);

//栈实现二叉树的输出
extern stadus PreOrderTraverse2(BitTree T);
extern stadus InOrderTraverse2(BitTree T);
extern stadus PostOrderTraverse2(BitTree T);
//二叉树的应用
extern stadus Depth(BitTree T);
extern stadus Single(BitTree T);
extern stadus Double(BitTree T);
extern stadus CountLeaf(BitTree T);
extern void Change_Left_Right(BitTree T);
//二叉层次遍历用到队列
typedef BitTree Qelemtype;
typedef struct QNode{
Qelemtype data;
struct QNode *next;
}qnode,*QueuePtr;
typedef struct {
QueuePtr front;
QueuePtr rear;
}LinkQueue;
extern stadus InitQueue(LinkQueue &Q);
extern stadus DestroyQueue(LinkQueue &Q);
extern stadus EnterQueue(LinkQueue &Q,Qelemtype e);
extern stadus DeQueue(LinkQueue &Q,Qelemtype &e);
//二叉层次遍历
extern stadus LevelOrder(BitTree T);
//二叉排序树
extern void insert(BitTree &T,ElemType x);
extern void CreateBiTree2(BitTree &root);

#endif
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//cpp文件 bittree.cpp
#include "bittree.h"
#include <stdlib.h>

stadus initstackC (sqstack &s)
{
s.base=(selemtypechar2 *)malloc(100*sizeof(selemtypechar));//用STACKINCREMENT会报错？？？
if (!s.base) exit(OVERFLOW);
s.top=s.base;
s.stacksize=100;
return OK;
}
stadus gettopC(sqstack s,selemtypechar2 &e)
{
if(s.base==s.top) return ERROR;
e=*(s.top-1);
return OK;
}
stadus pushC(sqstack &s,selemtypechar2 e)
{
if ((s.top-s.base)>=s.stacksize)
{
s.base=(selemtypechar2 *)realloc(s.base,((s.stacksize+10)*(sizeof(selemtypechar))));
if(!s.base) exit(OVERFLOW);
s.top=s.base+s.stacksize;
s.stacksize+=10;
}
*(s.top++)=e;
//s.top++;
return OK;
}
stadus popC(sqstack &s,selemtypechar2 &e)
{
if(s.top==s.base) return ERROR;
--s.top;
e=*(s.top);
return OK;
}
stadus destroyC(sqstack &s)
{
free(s.base); s.base=NULL;s.top=NULL;
return OK;
}
stadus clearC(sqstack &s)
{
s.top=s.base;
return OK;
}
stadus stackempty(sqstack s)
{
if(s.top!=s.base) return ERROR;
else
return OK;
}

//二叉树
stadus CreateBitTree(BitTree &T)//创建
{
Telemtype ch;
cin>>ch;
if(ch=='#') T=NULL;
else{
T=(BitTree)malloc(sizeof(BitNode));
if (!T) exit (OVERFLOW);
T->data=ch;
CreateBitTree(T->lchild);
CreateBitTree(T->rchild);
}
return OK;
}
stadus PreOrderTraverse(BitTree T)//先序访问
{
if(!T) return ERROR;
else if (T)
{
cout<<T->data<<" ";
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
return OK;
}
stadus InOrderTraverse(BitTree T)//中序
{
if(!T) return ERROR;
else if (T)
{
InOrderTraverse(T->lchild);
cout<<T->data<<" ";
InOrderTraverse(T->rchild);
}
return OK;
}
stadus PostOrderTraverse(BitTree T)//后序
{
if(!T) return ERROR;
else if (T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data<<" ";
}
return OK;
}

//栈实现二叉树的访问
stadus PreOrderTraverse2(BitTree T)//先序
{
sqstack s;
BitTree p;
initstackC(s);
p=T;
//pushC(s,p);
while (p||!stackempty(s))
{
//popC(s,p);
if (p)
{
pushC(s,p);
if(!p->data)return ERROR;
cout<<p->data<<" ";
//p1=p;
p=p->lchild;
if (p==NULL)
{
popC(s,p);
p=p->rchild;
}
else
pushC(s,p);

}
else {
popC(s,p);
popC(s,p);
p=p->rchild;
if (p==NULL)
{
popC(s,p);
if (p==NULL)
{
return OK;
}
else
{
p=p->rchild;
}
}
else{
pushC(s,p);
if(!p->data)return ERROR;
cout<<p->data<<" ";
p=p->lchild;//左空不压栈
if (p==NULL)
{
popC(s,p);
p=p->rchild;
}
else
pushC(s,p);
}
}
}
destroyC(s);
return OK;
}
stadus InOrderTraverse2(BitTree T)//中序
{
sqstack s;
BitTree p;
initstackC(s);
p=T;
while (p||!stackempty(s))
{
if (p)
{
pushC(s,p);
p=p->lchild;
}
else {
popC(s,p);
if(!p->data)return ERROR;
cout<<p->data<<" ";
p=p->rchild;
}
}
destroyC(s);
return OK;
}

stadus PostOrderTraverse2(BitTree T)//后序
{
sqstack s;
BitTree p;
initstackC(s);
p=T;
while (p||!stackempty(s))
{
if (p)
{
pushC(s,p);
p=p->lchild;
if (p==NULL)
{
popC(s,p);
//p=p->rchild;
if (p->rchild==NULL)
{
if(!p->data)return ERROR;
cout<<p->data<<" ";
//p=p->rchild;
popC(s,p);
if (p==NULL)
{
return OK;
}
else
{
//pushC(s,p);//???右结点重复压栈？？？
//p1=p;
p=p->rchild;
//p->rchild=NULL;
}
}
else
{
p=p->rchild;
}
}
else
continue ;
}
else
{
//popC(s,p);
if(!p->data)return ERROR;
cout<<p->data<<" ";
popC(s,p);
if (p==NULL)
{
return OK;
}
else
{
//pushC(s,p);
//p1=p;
p=p->rchild;
//p->rchild=NULL;
}
}
}
destroyC(s);
return OK;
}
//二叉树的应用

//二叉树的深度
stadus Depth(BitTree T)
{
int depthval,depthLeft,depthRight;
if (!T) depthval=0;
else{
depthLeft=Depth(T->lchild);
depthRight=Depth(T->rchild);
depthval=1+(depthLeft>depthRight?depthLeft:depthRight);
}
return depthval;
}
//二叉树的单分支结点数
stadus Single(BitTree T)
{
if (T==NULL) return 0; //空树
else if (T->lchild==NULL && T->rchild==NULL) return 0; //叶子结点
else{
if (!T->lchild && T->rchild) return Single(T->rchild)+1;//只有左单分支
if (T->lchild && !T->rchild) return Single(T->lchild)+1;//只有右单分支
if(T->lchild && T->rchild) return Single(T->lchild)+Single(T->rchild);//双分支结点
}
}
//二叉树的多分支结点数
stadus Double(BitTree T)
{

if (T==NULL) return 0; //空树
else if (T->lchild==NULL && T->rchild==NULL) return 0; //叶子结点
else{
if (!T->lchild && T->rchild) return Double(T->rchild);//只有左单分支
if (T->lchild && !T->rchild) return Double(T->lchild);//只有右单分支
if(T->lchild && T->rchild) return Double(T->lchild)+Double(T->rchild)+1;//双分支结点
}
}
//叶子结点
stadus CountLeaf(BitTree T)
{
int num,num1,num2;
if(T==NULL) num=0;
else if(T->lchild==NULL&&T->rchild==NULL)
num=1;
else
{
num1=CountLeaf(T->lchild);
num2=CountLeaf(T->rchild);
num=num1+num2;
}
return num;
}
//交换左右子树
void Change_Left_Right(BitTree T)
{
BitTree Temp;
if (T)
{
Change_Left_Right(T->lchild);
Change_Left_Right(T->rchild);
Temp=T->lchild;
T->lchild=T->rchild;
T->rchild=Temp;
}
}
//二叉层次遍历用到队列
stadus InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=(QueuePtr)malloc(100*sizeof(qnode));
if(!Q.front) exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
stadus DestroyQueue(LinkQueue &Q)
{
while (Q.front)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}

stadus EnterQueue(LinkQueue &Q,Qelemtype e)
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(qnode));
if(!p) return ERROR;
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
stadus DeQueue(LinkQueue &Q,Qelemtype &e)
{ QueuePtr p;
if(Q.front==Q.rear) return ERROR;
p=Q.front->next;e=p->data;
Q.front->next=p->next;
if(Q.rear==p)Q.rear=Q.front;
free(p);
return OK;
}
//二叉层次遍历
stadus LevelOrder(BitTree T)
{
LinkQueue Q;
BitTree B;
InitQueue(Q);
if (T!=NULL)
{
EnterQueue(Q,T);
while (!(Q.front==Q.rear))
{
DeQueue(Q,B);
cout<<B->data<<" ";
if(B->lchild!=NULL) EnterQueue(Q,B->lchild);
if(B->rchild!=NULL) EnterQueue(Q,B->rchild);
}
}
return OK;
}
//二叉排序树
void insert(BitTree &T,ElemType x)
{
if (T==NULL)
{
T=(BitTree)malloc(sizeof(BitNode));
T->data=x;
T->lchild=T->rchild=NULL;
}
else
{
if(x<T->data)insert(T->lchild,x);
if(x>=T->data)insert(T->rchild,x);
}
}
void CreateBiTree2(BitTree &root)
{
ElemType x;
root=NULL;
cout<<"二叉排序树的创建<以'#'结束!!!>"<<endl;
cout<<"<请输入字母，没写整型!!!>"<<endl;
cin>>x;
while (x!='#')
{
insert(root,x);
cin>>x;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//主函数 main.cpp
#include "bittree.h"
void main()
{
system("cls");
system("color f0");
BitTree T;
Create:
cout<<'\t'<<'\t'<<"先序创建二叉树<以'#'表示左右孩子为空!!!>："<<endl;
CreateBitTree(T);
BitTree T1(T);
select:
cout<<'\t'<<'\t'<<"----------------MAIN-MENU----------------"<<endl;
cout<<'\t'<<'\t'<<"&1、先序输出 2、中序输出 3、后序输出 &"<<endl;
cout<<'\t'<<'\t'<<"&4、栈实现输出 5、重新创建二叉树 0、退出&"<<endl;
cout<<'\t'<<'\t'<<"------------6、二叉树的应用-------------"<<endl;
char sel;
getchar();
cin>>sel;
switch (sel)//总
{
case '0':
break;
case '1':cout<<endl<<"---------------------------------"<<endl;
PreOrderTraverse(T);
cout<<endl<<"---------------------------------"<<endl;
goto select;
case '2':cout<<endl<<"---------------------------------"<<endl;
InOrderTraverse(T);
cout<<endl<<"---------------------------------"<<endl;
goto select;
case '3':cout<<endl<<"---------------------------------"<<endl;
PostOrderTraverse(T);
cout<<endl<<"---------------------------------"<<endl;
goto select;
case '4':
stackcout:
cout<<endl<<'\t'<<" -------------------SUB-MENU1---------------------"<<endl;
cout<<'\t'<<" &1、先序输出 2、中序输出 3、后序输出 4、返回 &"<<endl;
cout<<'\t'<<" ------------------------------------------------"<<endl;
cin>>sel;
switch (sel)//栈关于树的输出
{
case '1':cout<<endl<<"---------------------------------"<<endl;
PreOrderTraverse2(T1);//p->lchild==null,时 T 的值被修改！！！！！！！！
cout<<endl<<"---------------------------------"<<endl;
goto stackcout;
case '2':cout<<endl<<"---------------------------------"<<endl;
InOrderTraverse2(T);
cout<<endl<<"---------------------------------"<<endl;
goto stackcout;
case '3':cout<<endl<<"---------------------------------"<<endl;
PostOrderTraverse(T1);//栈实现未写完
cout<<endl<<"---------------------------------"<<endl;
goto stackcout;
case '4':goto select;
default:cout<<"选择错误!!!"<<endl;
goto stackcout;
}
case '5':
goto Create;
case '6':
{
SUB_MENU2:
cout<<'\t'<<'\t'<<"-------------------------SUB-MENU2---------------------"<<endl;
cout<<'\t'<<'\t'<<"&1、二叉树的深度 2、二叉树的单分支结点数 &"<<endl;
cout<<'\t'<<'\t'<<"&3、二叉树的多分支结点数 4、二叉树的叶子结点数 &"<<endl;
cout<<'\t'<<'\t'<<"&5、二叉层次遍历 6、二叉排序树 7、交换左右子树 &"<<endl;
cout<<'\t'<<'\t'<<"&------------------8、输出 0、返回--------------------&"<<endl;
cin>>sel;
switch (sel)//二叉树的应用
{
case '0':
goto select;
case '1':
{
int deepth=0;
deepth=Depth(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"树的深度为："<<deepth<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '2':
{
int cou_sig;
cou_sig=Single(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"此树的单分支结点为数："<<cou_sig<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '3':
{
int cou_dou;
cou_dou=Double(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"此树的双分支结点数为："<<cou_dou<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '4':
{
int cou_leaf;
cou_leaf=CountLeaf(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"此树的叶子结点数为："<<cou_leaf<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '5':
{
cout<<"二叉层次遍历的结果为："<<endl;
cout<<endl<<"---------------------------------"<<endl;
LevelOrder(T);
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '6':
{
BitTree T3;
CreateBiTree2(T3);
SUB3:
cout<<'\t'<<"-------------------------SUB-MENU2-------------------"<<endl;
cout<<'\t'<<" &1、先序输出 2、中序输出 3、后序输出 0、返回 &"<<endl;
cout<<'\t'<<"-----------------------------------------------------"<<endl;
cin>>sel;
switch (sel)//二叉树的层次遍历
{
case '0':
break;
case '1':cout<<endl<<"---------------------------------"<<endl;
PreOrderTraverse(T3);
cout<<endl<<"---------------------------------"<<endl;
goto SUB3;
case '2':cout<<endl<<"---------------------------------"<<endl;
InOrderTraverse(T3);
cout<<endl<<"---------------------------------"<<endl;
goto SUB3;
case '3':cout<<endl<<"---------------------------------"<<endl;
PostOrderTraverse(T3);
cout<<endl<<"---------------------------------"<<endl;
goto SUB3;
default:
cout<<"选择错误!!!"<<endl;
goto SUB3;
}
}
goto SUB_MENU2;
case '7':
{
Change_Left_Right(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"交换完成，请选择8输出查看!!!"<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '8':
goto select;
default:
cout<<"选择错误!!!"<<endl;
goto SUB_MENU2;
}
}
break;
default :
cout<<endl<<"选择错误!!!"<<endl;
goto select;
}
}

温馨提示：答案为网友推荐，仅供参考

当前网址：http://99.wendadaohang.com/zd/vWzeevtOj.html

其他回答

第1个回答 2011-01-07

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>

typedef int DataType; //定义数据类型,以int为例

struct BSTNode //定义二叉排序树节点类型
{
DataType data;
struct BSTNode *lchild,*rchild;
};
int insert(struct BSTNode **root,DataType data) //插入一个节点,成功返回1，否则返回0
{
struct BSTNode *newNode=(struct BSTNode*)malloc(sizeof(struct BSTNode));
newNode->data=data;
newNode->lchild=newNode->rchild=NULL;
if(*root==NULL) //为空则直接插入
{
*root=newNode;
return 1;
}
if((*root)->data==data) //找到相同元素则返回
return 0;
else if(data<(*root)->data) //递推插入左子树
return insert(&(*root)->lchild,data);
else //递推插入右子树
return insert(&(*root)->rchild,data);
}
void preorder(struct BSTNode *root) //先序遍历
{

if(root==NULL)
return;
printf("%d ",root->data);
preorder(root->lchild);
preorder(root->rchild);
}

void inorder(struct BSTNode *root) //中序遍历,结果必然是由小到大排序
{
if(root==NULL)
return;
inorder(root->lchild);
printf("%d ",root->data);
inorder(root->rchild);
}

int delNode(struct BSTNode **root,DataType key) //在二叉树root中删除关键字为key的节点
{
/*
删除*p结点的三种情况
(1)*p是叶子(即它的孩子数为0)
无须连接*p的子树，只需将*p的双亲*parent中指向*p的指针域置空即可。
(2)*p只有一个孩子*child
只需将*child和*p的双亲直接连接后，即可删去*p。
注意：
*p既可能是*parent的左孩子也可能是其右孩子，而*child可能是*p的左孩子或右孩子，故共有4种状态;
(3)*p有两个孩子
先令q=p，将被删结点的地址保存在q中；然后找*q的中序后继*p，并在查找过程中仍用parent记住*p的双亲位置。
*q的中序后继*p一定是*q的右子树中最左下的结点，它无左子树。
因此，可以将删去*q的操作转换为删去的*p的操作，即在释放结点*p之前将其数据复制到*q中，就相当于删去了*q。
*/
struct BSTNode *parent=NULL,*p=*root,*q,*child;
while(p){ //从根开始查找关键字为key的待删结点
if(p->data==key)
break; //已找到，跳出查找循环
parent=p; //parent指向*p的双亲
p=(key<p->data) ? p->lchild : p->rchild; //在关p的左或右子树中继续找
}
if(!p)
return 0;
q=p; //q记住被删结点*p
if(q->lchild && q->rchild) //*q的两个孩子均非空，故找*q的中序后继*p
for(parent=q,p=q->rchild;p->lchild;parent=p,p=p->lchild);
//现在情况(3)已被转换为情况(2)，而情况(1)相当于是情况(2)中child=NULL的状况
child=(p->lchild)? p->lchild:p->rchild;//若是情况(2)，则child非空；否则child为空
if(!parent) //*p的双亲为空，说明*p为根，删*p后应修改根指针
*root=child;//若是情况(1)，则删去*p后，树为空；否则child变为根
else
{ //*p不是根，将*p的孩子和*p的双亲进行连接，*p从树上被摘下
if(p==parent->lchild) //*p是双亲的左孩子
parent->lchild=child;//*child作为*parent的左孩子
else parent->rchild=child;//*child作为 parent的右孩子

if(p!=q) //是情况(3)，需将*p的数据复制到*q
q->data=p->data;//若还有其它数据域亦需复制
}
free(p);//释放*p占用的空间
return 1;
}

void main()
{
int i,key;
char choice;
struct BSTNode *root=NULL; //建立一棵空树
DataType data[]={5,2,9,4,6,1,7,3}; //节点元素
for(i=0;i<sizeof(data)/sizeof(data[0]);i++)
{
insert(&root,data[i]);
}
printf("\t**********************\n");
printf("\t1,插入一个节点\n");
printf("\t2,删除一个节点\n");
printf("\t3,输出先序遍历\n");
printf("\t4,输出中序遍历\n");
printf("\t5,退出\n");
printf("\t**********************\n");

while(1)
{
printf("请按键选择操作(1~5)\n");
fflush(stdin);
choice=getch();
switch(choice)
{
case '1':
printf("输入插入元素:");
scanf("%d",&key);
if(insert(&root,key))
printf("插入成功\n");
else
printf("已存在此元素\n");
break;
case '2':
printf("输入删除元素:");
scanf("%d",&key);
if(delNode(&root,key))
printf("删除成功\n");
else
printf("不存在此元素\n");
break;
case '3':
preorder(root);
printf("\n");
break;
case '4':
inorder(root);
printf("\n");
break;
case '5':
exit(0);
default:
printf("按键错误\n");
}
}
}本回答被网友采纳

第2个回答 2011-01-09

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>

typedef int DataType; //定义数据类型,以int为例

struct BSTNode //定义二叉排序树节点类型
{
DataType data;
struct BSTNode *lchild,*rchild;
};
int insert(struct BSTNode **root,DataType data) //插入一个节点,成功返回1，否则返回0
{
struct BSTNode *newNode=(struct BSTNode*)malloc(sizeof(struct BSTNode));
newNode->data=data;
newNode->lchild=newNode->rchild=NULL;
if(*root==NULL) //为空则直接插入
{
*root=newNode;
return 1;
}
if((*root)->data==data) //找到相同元素则返回
return 0;
else if(data<(*root)->data) //递推插入左子树
return insert(&(*root)->lchild,data);
else //递推插入右子树
return insert(&(*root)->rchild,data);
}
void preorder(struct BSTNode *root) //先序遍历
{

if(root==NULL)
return;
printf("%d ",root->data);
preorder(root->lchild);
preorder(root->rchild);
}

void inorder(struct BSTNode *root) //中序遍历,结果必然是由小到大排序
{
if(root==NULL)
return;
inorder(root->lchild);
printf("%d ",root->data);
inorder(root->rchild);
}

int delNode(struct BSTNode **root,DataType key) //在二叉树root中删除关键字为key的节点
{
/*
删除*p结点的三种情况
(1)*p是叶子(即它的孩子数为0)
无须连接*p的子树，只需将*p的双亲*parent中指向*p的指针域置空即可。
(2)*p只有一个孩子*child
只需将*child和*p的双亲直接连接后，即可删去*p。
注意：
*p既可能是*parent的左孩子也可能是其右孩子，而*child可能是*p的左孩子或右孩子，故共有4种状态;
(3)*p有两个孩子
先令q=p，将被删结点的地址保存在q中；然后找*q的中序后继*p，并在查找过程中仍用parent记住*p的双亲位置。
*q的中序后继*p一定是*q的右子树中最左下的结点，它无左子树。
因此，可以将删去*q的操作转换为删去的*p的操作，即在释放结点*p之前将其数据复制到*q中，就相当于删去了*q。
*/
struct BSTNode *parent=NULL,*p=*root,*q,*child;
while(p){ //从根开始查找关键字为key的待删结点
if(p->data==key)
break; //已找到，跳出查找循环
parent=p; //parent指向*p的双亲
p=(key<p->data) ? p->lchild : p->rchild; //在关p的左或右子树中继续找
}
if(!p)
return 0;
q=p; //q记住被删结点*p
if(q->lchild && q->rchild) //*q的两个孩子均非空，故找*q的中序后继*p
for(parent=q,p=q->rchild;p->lchild;parent=p,p=p->lchild);
//现在情况(3)已被转换为情况(2)，而情况(1)相当于是情况(2)中child=NULL的状况
child=(p->lchild)? p->lchild:p->rchild;//若是情况(2)，则child非空；否则child为空
if(!parent) //*p的双亲为空，说明*p为根，删*p后应修改根指针
*root=child;//若是情况(1)，则删去*p后，树为空；否则child变为根
else
{ //*p不是根，将*p的孩子和*p的双亲进行连接，*p从树上被摘下
if(p==parent->lchild) //*p是双亲的左孩子
parent->lchild=child;//*child作为*parent的左孩子
else parent->rchild=child;//*child作为 parent的右孩子

if(p!=q) //是情况(3)，需将*p的数据复制到*q
q->data=p->data;//若还有其它数据域亦需复制
}
free(p);//释放*p占用的空间
return 1;
}

void main()
{
int i,key;
char choice;
struct BSTNode *root=NULL; //建立一棵空树
DataType data[]={5,2,9,4,6,1,7,3}; //节点元素
for(i=0;i<sizeof(data)/sizeof(data[0]);i++)
{
insert(&root,data[i]);
}
printf("\t**********************\n");
printf("\t1,插入一个节点\n");
printf("\t2,删除一个节点\n");
printf("\t3,输出先序遍历\n");
printf("\t4,输出中序遍历\n");
printf("\t5,退出\n");
printf("\t**********************\n");

while(1)
{
printf("请按键选择操作(1~5)\n");
fflush(stdin);
choice=getch();
switch(choice)
{
case '1':
printf("输入插入元素:");
scanf("%d",&key);
if(insert(&root,key))
printf("插入成功\n");
else
printf("已存在此元素\n");
break;
case '2':
printf("输入删除元素:");
scanf("%d",&key);
if(delNode(&root,key))
printf("删除成功\n");
else
printf("不存在此元素\n");
break;
case '3':
preorder(root);
printf("\n");
break;
case '4':
inorder(root);
printf("\n");
break;
case '5':
exit(0);
default:
printf("按键错误\n");
}
}
}
回答时间：2011-1-7 17:32

向TA求助回答者： passion_wu128 来自团队百度鸣人 | 六级采纳率：63%

擅长领域： C/C++ 生活常识学习帮助幽默滑稽音乐

参加的活动：

输入内容已经达到长度限制
还能输入 9999 字
插入图片删除图片插入地图删除地图插入视频视频地图回答即可得2分经验值，回答被采纳可同步增加经验值和财富值
参考资料：匿名回答提交回答回答共1条

mark
回答者： plo154100 | 五级 | 2011-1-7 11:28

转发到： huyixuan259一级我的提问我的回答积分商城
（0）条消息等待处理
今天你做任务了没？全部任务新秀集训 +10.新年4-1行动.常来常往 +200.新手任务之回答篇 +20..进入个人中心
使用百度Hi可以第一时间收到“提问有新回答”“回答被采纳”“网友求助”的通知。查看详情

您想在自己的网站上展示百度“知道”上的问答吗？来获取免费代码吧！

如要投诉或提出意见建议，
请到百度知道投诉吧反馈。

©2011 Baidu 使用百度前必读知道协议任务提醒x

第3个回答 2011-01-07

mark