二叉树的各种基本操作实验报告

a.输入完全二叉树的先序序列,用#代表虚结点(空指针),如ABD###CE##F## 建立二叉树,实现先序、中序和后序以及按层次遍历序列。b. 求所有叶子及结点总数。掌握二叉树的存储实现; 掌握二叉树的遍历思想; 掌握二叉树的常见算法的程序实现。

实 目 项 型

验

项二叉树的操作

目

类

综合型

完 成 时 间

2009-11-2

实 验 目 的及 要 求

掌握二叉树的存储实现; 掌握二叉树的遍历思想; 掌握二叉树的 常见算法的程序实现。

(实验步骤 【实验过程】 实验步骤、绘图、记录、数据、分析、结果) 实验过程】 实验步骤、绘图、记录、数据、分析、结果) ( 实验内容： 实验内容：a.输入完全二叉树的先序序列， 用#代表虚结点 (空指针) 如 ABD###CE##F## 建 ， 立二叉树，实现先序、中序和后序以及按层次遍历序列。 b. 求所有叶子及结点总数。

实验步骤： 实验步骤：#include <stdio.h> #include <stdlib.h> #define MAX 10 #define STACK_INIT_SIZE 40 //存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 typedef struct BiTNode { char data; struct BiTNode *lchild; struct BiTNode *rchild; }BiTNode,*BiTree;//将 BiTree 定义为指向二叉链表结点结构的指针类型 BiTNode *bt; typedef struct { BiTree *base; int top; int stacksize; }SqStack; typedef struct { BiTree *base;

a.输入完全二叉树的先序序列,用#代表虚结点(空指针),如ABD###CE##F## 建立二叉树,实现先序、中序和后序以及按层次遍历序列。b. 求所有叶子及结点总数。掌握二叉树的存储实现; 掌握二叉树的遍历思想; 掌握二叉树的常见算法的程序实现。

int front; int rear; }SqQueue; void InitStack(SqStack &S) { // 构造一个空栈 S S.base=(BiTree*) malloc(STACK_INIT_SIZE*sizeof(BiTree)); if (!S.base) exit (0); //存储分配失败 S.top=0; //空表长度为 0 S.stacksize=STACK_INIT_SIZE; //初始存储容量 }//InitStack int StackEmpty(SqStack &S) { // 判断栈 S 是否是空栈，是返回 1,否则返回 0 if(S.top==0) return 1; else return 0; }//StcakEmpty void Push(SqStack &S, BiTree e) { // 插入元素 e 为新的栈顶元素, if (S.top>=S.stacksize) {//栈满追加空间 S.base=(BiTree*) realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree)); if(!S.base) exit(0);//存储分配失败 S.stacksize+=STACKINCREMENT; } S.base[S.top++]=e; }//Push void Pop(SqStack &S,BiTree &e) { //若栈不空则删除 S 的栈顶元素，并用 e 返回其值 if (S.top==0) { printf("栈空"); //栈为空 exit(0); } e=S.base[--S.top];

a.输入完全二叉树的先序序列,用#代表虚结点(空指针),如ABD###CE##F## 建立二叉树,实现先序、中序和后序以及按层次遍历序列。b. 求所有叶子及结点总数。掌握二叉树的存储实现; 掌握二叉树的遍历思想; 掌握二叉树的常见算法的程序实现。

}//Pop int GetTop(SqStack S, BiTree &e) { //若栈不空则用 e 返回 S 的栈顶元素 if (S.top==0) { printf("栈空"); return 0;//栈为空 } else { e=S.base[S.top-1]; return 1; } }//GetTop void InitQueue(SqQueue &Q) {//构建新队列 Q Q.base=(BiTree*)malloc(MAX * sizeof(BiTree)); Q.front=Q.rear=0; } int QueueEmpty(SqQueue Q) {//判断队列是否是一个空队列 if(Q.front==Q.rear) return 1; return 0; } void EnQueue(SqQueue &Q,BiTree e) {//将元素 e 插入到队列 Q 中 if((Q.rear+1)%MAX==Q.front) exit(0); Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAX; } void DeQueue(SqQueue &Q,BiTree &e) {//将非空队列 Q 的队头元素出队列 if(Q.front==Q.rear) exit(0); e=Q.base[Q.front]; Q.front=(Q.front+1)%MAX;

a.输入完全二叉树的先序序列,用#代表虚结点(空指针),如ABD###CE##F## 建立二叉树,实现先序、中序和后序以及按层次遍历序列。b. 求所有叶子及结点总数。掌握二叉树的存储实现; 掌握二叉树的遍历思想; 掌握二叉树的常见算法的程序实现。

} //int n0,n;//n0 统计叶子结点数，n 统计总的结点数 void PreCreatBiTree(BiTree &bt) {//按照先序建立二叉树的二叉链表"#"表示虚结点 char ch; ch=getchar(); if(ch=='#') bt=NULL; else { bt=(BiTree)malloc(sizeof(Bi

TNode)); bt->data=ch; PreCreatBiTree(bt->lchild); PreCreatBiTree(bt->rchild); } } void InOrderTraverse1(BiTree bt) {//利用递归算法中序遍历一个二叉树 if(bt) { InOrderTraverse1(bt->lchild); printf("%2c",bt->data); InOrderTraverse1(bt->rchild); } } void PreOrderTraverse1(BiTree bt) {//递归算法对二叉树进行先序便利 if(bt) { printf("%2c",bt->data); PreOrderTraverse1(bt->lchild); PreOrderTraverse1(bt->rchild); } } void PostOrderTraverse1(BiTree bt) {//利用递归后序遍历二叉树 if(bt) { PostOrderTraverse1(bt->lchild); PostOrderTraverse1(bt->rchild); printf("%2c",bt->data);

a.输入完全二叉树的先序序列,用#代表虚结点(空指针),如ABD###CE##F## 建立二叉树,实现先序、中序和后序以及按层次遍历序列。b. 求所有叶子及结点总数。掌握二叉树的存储实现; 掌握二叉树的遍历思想; 掌握二叉树的常见算法的程序实现。

} } void LeverlOrderTraverse(BiTree bt) {//层次遍历二叉树 SqQueue Q; BiTree p; if(bt) { InitQueue(Q); EnQueue(Q,bt); while(!QueueEmpty(Q)) { DeQueue(Q,p); printf("%2c",p->data); if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); }//while }//if }//LeverlOrderTraverse void PreOrderTraverse2(BiTree bt) { //非递归对 bt 进行先序遍历 SqStack S; BiTree p; if(bt){ InitStack(S); Push(S, bt);//根指针进栈 while(!StackEmpty(S)) { while(GetTop(S,p) && p) { printf("%2c",p->data); Push(S, p->lchild); } //向左一直走到尽头 Pop(S,p); //空指针退栈 if(!StackEmpty(S)) { Pop(S,p); Push(S, p->rchild); }

a.输入完全二叉树的先序序列,用#代表虚结点(空指针),如ABD###CE##F## 建立二叉树,实现先序、中序和后序以及按层次遍历序列。b. 求所有叶子及结点总数。掌握二叉树的存储实现; 掌握二叉树的遍历思想; 掌握二叉树的常见算法的程序实现。

}//while }//if }// PreOrderTraverse

void InOrderTraverse2(BiTree bt) {//非递归对 bt 进行中序遍历 if(bt) { SqStack S; BiTree p; InitStack(S); Push(S, bt); //根指针进栈 while(!StackEmpty(S)) { while(GetTop(S,p)&&p)//栈顶元素非空 Push(S, p->lchild); //向左一直走到尽头 Pop(S, p); //空指针退栈 if(!StackEmpty(S)) { Pop(S,p); printf("%2c",p->data); Push(S, p->rchild); }//if }//while }//if }// InOrderTraverse void PostOrderTraverse2(BiTree bt) { //非递归对 bt 进行后序遍历 SqStack S; BiTree p,q; InitStack(S); Push(S,bt);//根指针进栈 while …… 此处隐藏：4772字，全部文档内容请下载后查看。喜欢就下载吧 ……