首页 > 代码库 > 数据机构实验报告-实验三 二叉树基本操作的实现
数据机构实验报告-实验三 二叉树基本操作的实现
实验三 二叉树基本操作的实现
l 实验目的
1、二叉树的基本操作
（1）掌握二叉树链表的结构和二叉排序树的建立过程。
（2）掌握二叉树排序树的插入和删除操作。
（3）加深对二叉树的理解，逐步培养解决实际问题的编程能力。
2、树的遍历和哈夫曼树
（1）掌握用递归方法实现二叉树遍历的操作。
（2）掌握用非递归方法实现二叉树遍历的操作。
（3）掌握建立Huffman树的操作。
（4）加深对二叉树的理解，逐步培养解决实际问题的编程能力。
l 实验内容
1、二叉树的基本操作
（一）基础题
（1）SearchNode(TREE *tree,int key,TREE **pkpt,TREE **kpt)查找结点函数；
（2）InsertNode(TREE **tree,int key)二叉排序树插入函数；
（3）DeleteNode(TREE **tree,int key)二叉排序树删除函数；
2.调用上述函数实现下列操作：
（1）初始化一棵二叉树；
（2）调用插入函数建立一棵二叉排序树；
（3）调用查找函数在二叉树中查找指定的结点；
（二）提高题
【问题描述】已知以二叉树链表作为存储结构，试编写按中序遍历并打印二叉树的算法。
【程序设计思路】采用一个栈，先将二叉树的根结点入栈，若它有左子树，便将左子树的根节点入栈，直到左子树为空，然后依次退栈并输出结点值；若输出的结点有右子树，便将右子树的根结点入栈，如此循环入栈、退栈，直到栈为空为止。
2、树的遍历和哈夫曼树
（1）re_preorder(TREE *tree) 先序遍历，采用递归方法；
（2）re_midorder(TREE *tree)中序遍历，采用递归方法；
（3）re_posorder(TREE *tree) 后序遍历，采用递归方法；
（4）st_preorder(TREE *tree)先序遍历，采用链接栈的迭代方法；
（5）st_midorder(TREE *tree)中序遍历，采用链接栈的迭代方法；
（6）st_posorder(TREE *tree)后序遍历，采用链接栈的迭代方法；
2.调用上述函数实现下列操作：
（1）用递归方法分别实现先序、中序和后序遍历二叉树；
（2）用非递归方法分别实现先序、中序和后序遍历二叉树。
（3）程序源代码
#include<stdio.h>
#include<malloc.h>
#include<conio.h>
#include <windows.h>
#include<stdlib.h>
typedef struct tree /* 定义树的结构*/
{
int data; /*假定树的元素类型为int*/
struct tree *lchild; /*左孩子*/
struct tree *rchild; /*右孩子*/
}TREE;
typedef struct stack /*定义链接栈结构*/
{
TREE *t; /*栈结点元素为指向二叉树结点的指针*/
int flag; /*后序遍历时用到该标志*/
struct stack *link;/*栈结点链接指针*/
}STACK;
void gotoxy(int x,int y) //x为列坐标,y为行坐标
{
COORD pos={x,y}; //设定坐标
HANDLE hOut=GetStdHandle(STD_OUTPUT_HANDLE); //函数句柄
SetConsoleCursorPosition(hOut,pos);
}
void push(STACK **top,TREE *tree)/*树结点入栈*/
{
STACK *p; /*工作指针*/
p=(STACK*)malloc(sizeof(STACK));/*申请栈结点*/
p->t=tree; /*根结点进栈*/
p->link=*top; /*新栈结点指向栈顶*/
*top=p; /*栈顶为新结点*/
}
void pop(STACK **top,TREE **tree)/*出栈*/
{
STACK *p;
if(*top==NULL)
*tree=NULL;
else
{
*tree=(*top)->t;
p=*top;
*top=(*top)->link;
free(p);
}
}
void SearchNode(TREE *tree,int key,TREE **pkpt,TREE **kpt)/*查找树的根结点*/
{
*pkpt=NULL;
*kpt=tree;
while(*kpt!=NULL)
{
if((*kpt)->data=http://www.mamicode.com/=key)
return;
*pkpt=*kpt;
if(key<(*kpt)->data)
*kpt=(*kpt)->lchild;
else
*kpt=(*kpt)->rchild;
}
}
int InsertNode(TREE **tree,int key) /*在查找树上插入新结点，返回1表示该键值结点已存在，返回-1表示内存申请失败*/
{
TREE *p,*q,*r;
SearchNode(*tree,key,&p,&q);
if(q!=NULL)
return 1;
if((r=(TREE*)malloc(sizeof(TREE)))==NULL)
return -1;
r->data=http://www.mamicode.com/key;
r->lchild=r->rchild=NULL;
if(p==NULL)
*tree=r;
else if(p->data>key)
p->lchild=r;
else
p->rchild=r;
return 0;
}
int DeleteNode(TREE **tree,int key) /*在查找树上删除结点，返回1表示该键值结点不存在*/
{
TREE *p,*q,*r;
SearchNode(*tree,key,&p,&q);
if(q==NULL)
return 1;
if(p==NULL)
if(q->lchild==NULL)
*tree=q->rchild;
else
{
*tree=q->lchild;
r=q->lchild;
while(r->rchild!=NULL)
r=r->rchild;
r->rchild=q->rchild;
}
else if(q->lchild==NULL)
if(q==p->lchild)
p->lchild=q->rchild;
else
p->rchild=q->rchild;
else
{
r=q->lchild;
while(r->rchild!=NULL)
r=r->rchild;
r->rchild=q->rchild;
if(q==p->lchild)
p->lchild=q->lchild;
else
p->rchild=q->lchild;
}
free(q);
return 0;
}
void OutputTree(TREE *tree) /*层次打印树结点，中序遍历，采用链接栈的迭代方法*/
{
STACK *top;
int deep=0,no=0,maxdeep=0;
top=NULL;
while(tree!=NULL||top!=NULL)
{
while(tree!=NULL)
{
push(&top,tree);
top->flag=++deep;
if(maxdeep<deep)
maxdeep=deep;
tree=tree->lchild;
}
if(top!=NULL)
{
deep=top->flag;
no++;
pop(&top,&tree);
gotoxy(no *4,deep+2);
printf("%d",tree->data);
fflush(stdout);
tree=tree->rchild;
}
}
gotoxy(1,maxdeep+3);
printf("任意键继续\n");
getch();
}
int main()
{
TREE *t;
int op=-1,i,ret;
t=NULL;
while(op!=0)
{
printf("请选择操作:\n-1-：增加树结点\n-2-：删除树结点\n-0-：结束操作\n");
fflush(stdin);
scanf("%d",&op);
switch(op)
{
case 0:
break;
case 1:
printf("请输入树结点元素：");
scanf("%d",&i);
switch(InsertNode(&t,i))
{
case 0:
system("cls");
gotoxy(1,1);
printf("成功，树结构为：\n");
OutputTree(t);
break;
case 1:
printf("该元素已存在");
break;
default:
printf("内存操作失败");
break;
}
break;
case 2:
printf("请输入要删除的树结点元素：");
scanf("%d",&i);
if(DeleteNode(&t,i)){
system("cls");
gotoxy(1,1);
printf("删除成功，树结构为：\n");
OutputTree(t);
}
else
printf("该键植树结点不存在\n");
break;
}
}
}
（二）提高题
（1）程序源代码：
#include<stdio.h>
#include<malloc.h>
#include<conio.h>
#include <windows.h>
#include<stdlib.h>
typedef struct tree
{
int data;
struct tree *lchild;
struct tree *rchild;
}TREE;
typedef struct stack
{
TREE *t;
int flag;
struct stack *link;
}STACK;
void gotoxy(int x,int y) //x为列坐标,y为行坐标
{
COORD pos={x,y}; //设定坐标
HANDLE hOut=GetStdHandle(STD_OUTPUT_HANDLE); //函数句柄
SetConsoleCursorPosition(hOut,pos);
}
void push(STACK **top,TREE *tree)
{
STACK *p;
p=(STACK*)malloc(sizeof(STACK));
p->t=tree;
p->link=*top;
*top=p;
}
void pop(STACK **top,TREE **tree)
{
STACK *p;
if(*top==NULL)
*tree=NULL;
else
{
*tree=(*top)->t;
p=*top;
*top=(*top)->link;
free(p);
}
}
void OutputTree(TREE *tree)
{
STACK *top;
int deep=0,no=0,maxdeep=0;
top=NULL;
while(tree!=NULL||top!=NULL)
{
while(tree!=NULL)
{
push(&top,tree);
top->flag=++deep;
if(maxdeep<deep)
maxdeep=deep;
tree=tree->lchild;
}
if(top!=NULL)
{
deep=top->flag;
no++;
pop(&top,&tree);
gotoxy(no *4,deep+2);
printf("%d",tree->data);
fflush(stdout);
tree=tree->rchild;
}
}
gotoxy(1,maxdeep+3);
printf("任意键继续\n");
getch();
}
2、树的遍历和哈夫曼树
（1）画出数据结构基本运算的流程图
（2）程序运行主要结果截图
（3）程序源代码
#include<stdio.h>
#include<malloc.h>
#include<conio.h>
#include <windows.h>
#include<stdlib.h>
typedef struct tree /*定义树结构*/
{
int data;
struct tree *lchild;
struct tree *rchild;
}TREE;
typedef struct stack /*定义链接栈结构*/
{
TREE *t;
int flag;
struct stack *link;
}STACK;
void re_preorder(TREE *tree) /*先序遍历，采用递归方法*/
{
if(tree!=NULL)
{
printf("%d",tree->data);
re_preorder(tree->lchild);
re_preorder(tree->rchild);
}
}
void re_midorder(TREE *tree) /*中序遍历，采用递归方法*/
{
if(tree!=NULL)
{
re_midorder(tree->lchild);
printf("%d",tree->data);
re_midorder(tree->rchild);
}
}
void re_posorder(TREE *tree) /*后序遍历，采用递归方法*/
{
if(tree!=NULL)
{
re_posorder(tree->lchild);
re_posorder(tree->rchild);
printf("%d",tree->data);
}
}
void push(STACK **top,TREE *tree)/*树结点入栈*/
{
STACK *p;
p=(STACK*)malloc(sizeof(STACK));
p->t=tree;
p->link=*top;
*top=p;
}
void pop(STACK **top,TREE **tree)/*出栈，栈内元素赋值给树结点*/
{
STACK *p;
if(*top==NULL)
*tree=NULL;
else
{
*tree=(*top)->t;
p=*top;
*top=(*top)->link;
free(p);
}
}
void st_preorder(TREE *tree)/*先序遍历，采用链接栈的迭代方法*/
{
STACK *top;
top=NULL;
while(tree!=NULL)
{
printf("%d",tree->data);
if(tree->rchild!=NULL)
push(&top,tree->rchild);
if(tree->lchild!=NULL)
push(&top,tree->lchild);
push(&top,tree->lchild);
pop(&top,&tree);
}
}
void st_midorder(TREE *tree)/*中序遍历，采用链接栈的迭代方法*/
{
STACK *top;
top=NULL;
while(tree!=NULL||top!=NULL)
{
while(tree!=NULL)
{
push(&top,tree);
tree=tree->lchild;
}
if(top!=NULL)
{
pop(&top,&tree);
printf("%d",tree->data);
tree=tree->rchild;
}
}
}
void st_posorder(TREE *tree)/*后序遍历，采用链接栈的迭代方法*/
{
STACK *top;
top=NULL;
do{
while(tree!=NULL){
push(&top,tree);
top->flag=0;
tree=tree->lchild;
}
if(top!=NULL)
{
while(top!=NULL&&top->flag==1){
pop(&top,&tree);
printf("%d",tree->data);
}
if(top!=NULL)
{
top->flag=1;
tree=(top->t)->rchild;
}
}
}while(top!=NULL);
}
void SearchNode(TREE *tree,int key,TREE **pkpt,TREE **kpt)/*查找树根结点*/
{
*pkpt=NULL;
*kpt=tree;
while(*kpt!=NULL)
{
if((*kpt)->data=http://www.mamicode.com/=key)
return;
*pkpt=*kpt;
if(key<(*kpt)->data)
*kpt=(*kpt)->lchild;
else
*kpt=(*kpt)->rchild;
}
}
int InsertNode(TREE **tree,int key)/*在查找树上插入新结点*/
{
TREE *p,*q,*r;
SearchNode(*tree,key,&p,&q);
if(q!=NULL)
return 1;
if((r=(TREE*)malloc(sizeof(TREE)))==NULL)
return -1;
r->data=http://www.mamicode.com/key;
r->lchild=r->rchild=NULL;
if(p==NULL)
*tree=r;
else if(p->data>key)
p->lchild=r;
else
p->rchild=r;
return 0;
}
void gotoxy(int x,int y) //x为列坐标,y为行坐标
{
COORD pos={x,y}; //设定坐标
HANDLE hOut=GetStdHandle(STD_OUTPUT_HANDLE); //函数句柄
SetConsoleCursorPosition(hOut,pos);
}
void OutPutTree(TREE *tree)/*层次打印树结点，*/
{
STACK *top;
int deep=0,no=0,maxdeep=0;
top=NULL;
while(tree!=NULL||top!=NULL)
{
while(tree!=NULL)
{
push(&top,tree);
top->flag=++deep;
if(maxdeep<deep)
maxdeep=deep;
tree=tree->lchild;
}
if(top!=NULL)
{
deep=top->flag;
no++;
pop(&top,&tree);
gotoxy(no *4,deep+2);
printf("%d",tree->data);
fflush(stdout);
tree=tree->rchild;
}
}
gotoxy(1,maxdeep+3);
printf("任意键继续\n");
getch();
}
int main()
{
TREE *t;
int i,op=-1;
t=NULL;
while(op!=0)
{
printf("请选择操作：\n-1-：增加数结点；\n-0-：结束操作\n");
fflush(stdin);
scanf("%d",&op);
switch(op)
{
case 0:
break;
case 1:
printf("请输入树结点元素：");
scanf("%d",&i);
switch(InsertNode(&t,i))
{
case 0:
system("cls");
gotoxy(1,1);
printf("成功，数据结构为：\n");
OutPutTree(t);
break;
case 1:
printf("该元素已存在");
break;
default:
printf("内存操作失败");
break;
}
break;
}
}
printf("先序遍历，递归方法\n");
re_preorder(t);
printf("\n任意键继续\n\n");
getch();
printf("中序遍历，递归方法\n");
re_midorder(t);
printf("\n任意键继续\n\n");
getch();
printf("后序遍历，递归方法\n");
re_posorder(t);
printf("\n任意键继续\n\n");
getch();
printf("先序遍历，采用链接栈的迭代方法\n");
st_preorder(t);
printf("\n任意键继续\n\n");
getch();
printf("中序遍历，采用链接栈的迭代方法\n");
st_midorder(t);
printf("\n任意键继续\n\n");
getch();
printf("后序遍历，采用链接栈的迭代方法\n");
st_posorder(t);
printf("\n任意键继续\n\n");
getch();
}
l 小结
数据机构实验报告-实验三 二叉树基本操作的实现