#include <conio.h>
#include <stdlib.h>
typedef struct BitNode
{
char data
struct BitNode *lchild,*rchild
}BitNode,*BiTree
void CreateBiTree(BiTree &) //生成一个二叉树
void FirstOrder(BiTree) //先序递归遍历二叉树
void MiddleOrder(BiTree) //中序递归遍历二叉树
void LastOrder(BiTree)//后序递归遍历二叉树
void main()
{
BiTree T
int flag=1
char j
printf("本程序实现二叉树的操作。\n")
printf("例如:ABC DE G F (回车)，建立如下二叉树：\n")
printf(" A \n")
printf(" / \n")
printf(" B\n")
printf("/ \\ \n")
printf(" C D \n")
printf(" / \\ \n")
printf(" E F\n")
printf(" \\ \n")
printf(" G \n")
CreateBiTree(T)
getchar()
while(flag)
{
printf("请选择: \n")
printf("1.递归先序遍历\n")
printf("2.递归中序遍历\n")
printf("3.递归后序遍历\n")
printf("4.退出程序\n")
scanf(" %c",&j)
switch(j)
{
case '1': if(T)
{
printf("%c",T->data)//访问结点
FirstOrder(T->lchild) //遍历左子树
FirstOrder(T->rchild) //遍历右子树
}
else printf("二叉树为空!\n")
break
case '2': if(T)
{
MiddleOrder(T->lchild) //遍历左子树
printf("%c",T->data) //访问结点
MiddleOrder(T->rchild) //遍历右子树
}
else printf("二叉树为空!\n")
break
case '3': if(T)
{
LastOrder(T->lchild) //遍历左子树
LastOrder(T->rchild) //遍历右子树
printf("%c",T->data) //访问结点
}
else printf("二叉树为空!\n")
break
default: flag=0printf("程序运行结束，按任意键退出!\n")exit(0)
}
}
getch()
}
void CreateBiTree(BiTree &T)
{
char ch
scanf("%c",&ch)
if(ch==' ') T=NULL
else
{
T=(BitNode *)malloc(sizeof(BiTree))//生成一个新结点
T->data=ch
CreateBiTree(T->lchild)//生成左子树
CreateBiTree(T->rchild)//生成右子树
}
}
void FirstOrder(BiTree T)
{
if(T)
{
printf("%c",T->data)//访问结点
FirstOrder(T->lchild) //遍历左子树
FirstOrder(T->rchild) //遍历右子树
}
}
void MiddleOrder(BiTree T)
{
if(T)
{
MiddleOrder(T->lchild) //遍历左子树
printf("%c",T->data) //访问结点
MiddleOrder(T->rchild) //遍历右子树
}
}
void LastOrder(BiTree T)
{
if(T)
{
LastOrder(T->lchild) //遍历左子树
LastOrder(T->rchild) //遍历右子树
printf("%c",T->data) //访问结点
}
}
#include <stdio.h>#include <stdlib.h>
#define maxNumberLength 16
typedef struct node
{
int data
struct node *lchild,*rchild
} node
node *create(void)
void insert(node *&root,int data)
void inOrder(node *root)
void remove(node *&root,int data)
void subRemove(node *root,node *&now)
bool search(node *root,int data)
void findParent(node *root,node *data,node *&parent)
int main(void)
{
node *root
int engine=1
int data
printf("输入元素: ")
root=create()
printf("构造完成,中序遍历:")
inOrder(root)
putchar('\n')
while(engine!=0)
{
printf("\n\n1.插入 2.删除 3.查找 0.退出\n输入操作编号: ")
fflush(stdin)
scanf("%d",&engine)
switch(engine)
{
case 1:
printf("输入插入的元素值: ")
scanf("%d",&data)
insert(root,data)
printf("插入完成,中序遍历:")
inOrder(root)
break
case 2:
printf("输入删除的元素值: ")
scanf("%d",&data)
remove(root,data)
break
case 3:
printf("输入查找的元素值: ")
scanf("%d",&data)
if(search(root,data))
printf("找到该元素，元素值%d\n",data)
else
printf("没有该元素\n")
case 0:
break
default:
printf("没有该选项\n")
}
}
return 0
}
node *create(void)//构造
{
char numToChar[maxNumberLength]
char inch
int location,data
node *root=NULL
inch=getchar()
while((inch<'0'||inch>'9')&&inch!='\n')
inch=getchar()
while(inch!='\n')
{
location=0
while(inch>='0'&&inch<='9')
{
numToChar[location++]=inch
inch=getchar()
}
numToChar[location]='\0'
while((inch<'0'||inch>'9')&&inch!='\n')
inch=getchar()
data=atoi(numToChar)
insert(root,data)
}
return root
}
void insert(node *&root,int data)//插入
{
if(root==NULL)
{
root=(node *)malloc(sizeof(node))
root->data=data,root->lchild=root->rchild=NULL
}
else
{
if(data<=root->data)
insert(root->lchild,data)
else
insert(root->rchild,data)
}
}
void inOrder(node *root)//中序遍历
{
if(root!=NULL)
{
inOrder(root->lchild)
printf("%d ",root->data)
inOrder(root->rchild)
}
}
void remove(node *&root,int data)//删除
{
if(search(root,data))
{
node *temp=root,*parent
while(temp)
{
if(temp->data<data)
temp=temp->rchild
else if(temp->data>data)
temp=temp->lchild
else
break
}
subRemove(root,temp)
printf("删除成功，中序遍历: ")
inOrder(root)
}
else
printf("没有该元素\n")
}
bool search(node *root,int data)
{
node *temp=root
while(temp)
{
if(temp->data<data)
temp=temp->rchild
else if(temp->data>data)
temp=temp->lchild
else
break
}
return temp
}
void findParent(node *root,node *data,node *&parent)
{
if(root)
{
if(root->lchild==data||root->rchild==data)
parent=root
else
{
findParent(root->lchild,data,parent)
findParent(root->rchild,data,parent)
}
}
}
void subRemove(node *root,node *&now)
{
if(now->lchild==NULL&&now->rchild==NULL)
{
node *parent
findParent(root,now,parent)
if(parent->lchild==now)
parent->lchild=NULL
else
parent->rchild=NULL
free(now)
}
else
{
node *temp=now
int data
if(temp->lchild)
{
temp=temp->lchild
while(temp->rchild)
temp=temp->rchild
}
else
{
temp=temp->rchild
while(temp->lchild)
temp=temp->lchild
}
data=temp->data,temp->data=now->data,now->data=data
now=temp
subRemove(root,now)
}
}
