关于二叉树遍历问题2
#include <stdio.h> /*输入六个整数45、24、53、12、37、9,插入数据元素13,删除数据元素24和53 */#include <stdlib.h>
typedef struct BiTNode/*结点结构 */
{
int data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree Insert(BiTree T,int e)/*插入操作*/
{
BiTree p=T, f=NULL, s;
s=(BiTree)malloc(sizeof(BiTNode));
s->data=e;
s->lchild=s->rchild=NULL;
if (T==NULL) /*插入 s 为新的根结点*/
{
T = s;
}
else
{/*查找插入位置*/
while(p && p->data!=e) /*如果当前节点不为空且节点的值不是插入的值 */
{
if (p->data>e)
{f=p; p=p->lchild;} /*如果当前节点值大于插入的值，则记录当前节点，并将节点的左节点作为当前节点 */
else
{f=p; p=p->rchild;} /*否则，节点的右节点作为当前节点 */
}
if (p==NULL&&e <f->data) /*如果当前节点为空并且插入的值小于父节点中的值； */
f->lchild = s; /*插入 s 为 f 的左孩子 */
else if(p==NULL&&e>f->data) f->rchild = s; /* 插入 s 为 f 的右孩子*/
else {printf("insert wrong!");exit(0);}
}
return T;
}
void Delete(BiTree T,int x)
{
BiTree f=NULL,p=T,q,s;
while(p&&p->data!=x)
{
if(p->data>x)/*如果节点的数值大于x,则记录当前节点，查找其左节点 */
{f=p;p=p->lchild;}
else
{f=p;p=p->rchild;}
}
if(p==NULL)
{printf("search fail！");exit(0);}
if(p->lchild==NULL)/*当前节点左孩子为空，重接右结点或左右均为空 */
{
if(f->lchild==p) /*当前节点为左孩子（f->data>p->data） */
f->lchild=p->rchild;
else
f->rchild=p->rchild;
free(p);
} 这段程序怎么理解，望高手给解释下。
else if(p->rchild==NULL)/*右为空，重接左结点 */
{
if(f->lchild==p)
f->lchild=p->lchild;
else
f->rchild=p->lchild;
free(p);
}
else/*左右都不为空 */
{
q=p;
s=p->lchild;
while(s->rchild!=NULL)
{
q=s;
s=s->rchild;
}
p->data=s->data;
if(q==p)
p->lchild=s->lchild;
else
q->rchild=s->lchild; 这段程序怎么实现中序遍历的，望高手给解释下。
}
}
void Inorder(BiTree T)
{ /* 中序遍历二叉树 */
if (T)
{
Inorder(T->lchild); /* 遍历左子树 */
printf("%d ",T->data); /*访问结点 */
Inorder(T->rchild);/* 遍历右子树 */
}
}
void Menu(BiTree T)
{
int i,e;
printf("1.input\n");
printf("2.delete\n");
printf("3.end\n");
printf("choice：\n");
scanf("%d",&i);
switch(i)
{
case 1:
printf("input element：");
scanf("%d",&e);
T=Insert(T,e);
printf("inorder：\n");
Inorder(T);
printf("\n");
break;
case 2:
printf("delete element：");
scanf("%d",&e);
Delete(T,e);
printf("inorder：\n");
Inorder(T);
printf("\n");
break;
default:
exit(0);
break;
}
Menu(T);
}
void main()
{
int e,i;
BiTree T;
T=NULL;
printf("input 6 num:\n");
for(i=1;i <7;i++)
{
scanf("%d",&e);
T=Insert(T,e);
}
printf("inorder：\n");
Inorder(T);
printf("\n");
Menu(T);
getch();
}
