数据结构实验二二叉树的创建与访问算法的设计
- 格式：docx
- 大小：111.26 KB
- 文档页数：7
内蒙古工业大学信息工程学院实验报告
1
实验二 二叉树的创建与访问算法的设计
一、目的
本实验的目的是通过理解二叉树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。
二、选题
1—4.
源代码:
#include
#include
typedef struct BiTnode
{ char data;
struct BiTnode *lchild,*rchild;
}BiTree;
#define N 30
BiTree *bt,*BT[N];
int M; /*记录数据相同的结点的个数*/
int deepth=0; /*记录深度*/
/*按先序遍历序列建立二叉树的二叉链表*/
BiTree *Pre_create_BiTree(BiTree *bt)
{ char ch;
scanf("%c",&ch);
fflush(stdin);
if(ch=='0') bt=NULL;
else
{ bt=(BiTree *)malloc(sizeof(BiTree));
bt->data=ch;
deepth++;
printf("请输入第 %d 层上结点 %c 的在第 %d 层的左孩子:\t",
deepth,bt->data,deepth+1);
bt->lchild = Pre_create_BiTree(bt->lchild);
deepth++;
printf("请输入第 %d 层上结点 %c 的在第 %d 层的右孩子:\t",
deepth,bt->data,deepth+1);
bt->rchild=Pre_create_BiTree(bt->rchild);
}
deepth--;
return(bt);
}
A
B E
C D F
E
内蒙古工业大学信息工程学院实验报告
2
/*先序递归遍历*/
void Preorder_BiTree(BiTree *bt)
{ if(bt!=NULL)
{ printf("%c\t",bt->data);
Preorder_BiTree(bt->lchild);
Preorder_BiTree(bt->rchild);
}
}
/*中序递归遍历*/
void Inorder_recursive_BiTree(BiTree *bt)
{ if(bt!=NULL)
{ Inorder_recursive_BiTree(bt->lchild);
printf("%c\t",bt->data);
Inorder_recursive_BiTree(bt->rchild);
}
}
/*中序非递归遍历*/
void Inorder_non_recursive_BiTree(BiTree *bt)
{ int i=0;
BiTree*p,*s[N];
p=bt;
do
{ while(p!=NULL)
{ s[i++]=p;
p=p->lchild;
}
if(i>0)
{ p=s[--i];
printf("%c\t",p->data);
p=p->rchild;
}
}while(i>0||p!=NULL);
}
/*后序递归遍历*/
void Postorder_BiTree(BiTree *bt)
{ if(bt!=NULL)
{ Postorder_BiTree(bt->lchild);
Postorder_BiTree(bt->rchild);
printf("%c\t",bt->data);
}
}
内蒙古工业大学信息工程学院实验报告
3
void Search_BiTree(BiTree *bt,char x)
{
if(bt)
{ if(bt->data==x)
{BT[M]=bt;M++;}
Search_BiTree(bt->lchild,x);
Search_BiTree(bt->rchild,x);
}
}
void Parent_BiTree(BiTree *bt,BiTree *BT[])
{
if(bt)
{ if(bt->lchild!=NULL)
if(bt->lchild==BT[M])
{
printf("符合数据 %c 的第 %d 个结点的双亲结点的数据是: %c\n",BT[M]->data,M+1,bt->data);
M++;
}
Parent_BiTree(bt->lchild,BT);
if(bt->rchild!=NULL)
if(bt->rchild==BT[M])
{
printf("符合数据 %c 的第 %d 个结点的双亲结点的数据是: %c\n",BT[M]->data,M+1,bt->data);
M++;
}
Parent_BiTree(bt->rchild,BT);
}
}
int main()
{
BiTree *BTnode1,*BTnode2;
int choice,i=0;
char ch;
do
{ printf(" #二叉树菜单# \n");
printf("******************************\n\n");
printf("-_-||-_-1.建立二叉树 -_-||-_-\n");
printf("-_-||-_-2.遍历二叉树 -_-||-_-\n");
printf("-_-||-_-3.查找二叉结点-_-||-_-\n");
printf("-_-||-_-4.查找双亲结点-_-||-_-\n");
内蒙古工业大学信息工程学院实验报告
4
printf("-_-||-_-5.退出 -_-||-_-\n\n");
printf("******************************\n");
printf("请输入操作序号(1,2,3,4,5): ");
scanf("%d", &choice);
getchar();
switch(choice)
{
case 1:
printf("请输入要构建的二叉树的先序序列,以'0'表示空\n");
printf("请输入根结点: \t\t\t\t");
bt=Pre_create_BiTree(bt);
printf("构建二叉树成功!\n");
break;
case 2:
if(bt != NULL) //树不为空且已进行“创建”操作时执行
{
printf("先序递归遍历结果:\n");
Preorder_BiTree(bt);
printf("\n----------------------------------\n");
printf("中序递归遍历结果:\n");
Inorder_recursive_BiTree(bt);
printf("\n----------------------------------\n");
printf("中序非递归遍历结果:\n");
Inorder_non_recursive_BiTree(bt);
printf("\n----------------------------------\n");
printf("后序递归遍历结果:\n");
Postorder_BiTree(bt);
printf("\n----------------------------------\n");
}
else
printf("\n还没建立二叉树!\n\n");
break;
case 3:printf("请输入要查找的二叉树的数据: ");
scanf("%c",&ch);
if(bt)
{ M=0;
Search_BiTree(bt,ch);
if(BT[0])
for(i=0;i
内蒙古工业大学信息工程学院实验报告
5
printf("符合数据: %c 的第 %d 个结点在: %x
\n",BT[i]->data,i+1,BT[i]);
else printf("无该结点!\n");
for(i=0;i
BT[i]=NULL;
M=0;
}
else
printf("\n还没建立二叉树!\n\n");
break;
case 4:
printf("求某结点双亲请输入该结点的数据: ");
scanf("%c",&ch);
if(bt)
{ for(i=0;i
BT[i]=NULL;
