学院
实践课程设计
题 目 | 二叉树 |
学 院 | 工程技术学院 |
专 业 | 计算机科学与技术 |
班 级 | 计算机1701班 |
姓 名 | |
指导教师 | |
| |
一、实验目的
掌握二叉树的定义、基本操作,综合应用所学的知识分析问题、解决问题,学会用建立二叉树并对其进行遍历,提高实际编程能力及程序调试能力。
读用英语怎么说
二、实验要求
建立二叉树,并进行遍历(前序遍历、中序遍历、后序遍历、层次遍历)。
三、实验方法内容
1.算法设计思路
二叉树的非递归遍历是用显示栈来储存二叉树的节点指针,先序遍历时,按二叉树的前序遍历的顺序访问接点,并将结点指针入栈,直到栈顶指针指向结点的左指针域为空时取出栈顶指针并删除栈顶指针,访问刚取出的指针指向的结点的右指针指向结点并将其指针入栈,如此反复执行则为非递归操作。
二叉树的递归遍历:若二叉树为空,则空操作
先序遍历:
(a)访问根结点;
(b)先序遍历左子树;
(c)先序遍历右子树。
中序遍历:
一氧化碳的物理性质 (a)中序遍历左子树
(b) 访问根结点;
(c)中序遍历右子树。
后序遍历:
(a)后序遍历左子树
(b)后序遍历右子树
(c)访问根结点;
层次遍历:
从二叉树第一层(根节点)开始,从上至下逐层遍历,在同一层中,则按从左到右的顺序对结点逐个访问。
2.算法中用到的数据结构
(1)void CreateBiTree 以二叉链表表示二叉树,建立一棵二叉树;
(2)void PreOrderTraver 输出二叉树的前序遍历结果;
(3)void InOrderTraver 输出二叉树的中序遍历结果;
(4)void PostOrderTraver 输出二叉树的后序遍历结果;
(5)int LeafNodeCount 统计二叉树的叶结点个数;
(6)int Node Count 统计二叉树的结点个数;
(7)int Depth 计算二叉树的深度。
(8)int Swap 交换二叉树每个结点的左孩子和右孩子;父母的爱作文400字
3.主要的常量变量
void CreateBiTree
void PreOrderTraver
void InOrderTraver
void PostOrderTraver
int LeafNodeCount
int NodeCount
int Depth
int Swap
四、实验代码
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
//二叉树结构定义
尽力做某事英语typedef struct node
{
char data;
struct node *lchild,*rchild;
}binnode;
typedef binnode *bintree;
typedef struct Qnode *Queue;
//队列结构定义
struct Qnode{
bintree data[MAX];
int front;
int rear;
};
//判断队列是否为空
int IsQueue(Queue Q){
坎地沙坦酯
if(Q->front==Q->rear)
return 0;
el return 1;
}
//定义一个队列并初始化
Queue CreateEmptyQueue(){
Queue Ptrq;
Ptrq=(Queue)malloc(sizeof(struct Qnode));
Ptrq->front=0;
Ptrq->rear=0;
return Ptrq;
}
//入队
void EnQueue(Queue *Ptrq,bintree t){
if((((*Ptrq)->rear)+1)%MAX==(*Ptrq)->front)
{
printf("队满\n");
}
el{
(*Ptrq)->data[((*Ptrq)->rear)++]=t;
(*Ptrq)->rear=((*Ptrq)->rear)%MAX;
海参崴火车站 }
泼水节的由来}
//出队
bintree DeQueue(Queue *Ptrq){
bintree t;
if((*Ptrq)->front==(*Ptrq)->rear)
{
printf("队空\n");
return NULL;
}
el{
t=(*Ptrq)->data[(*Ptrq)->front];