数据结构全部上机实验及答案 - 图文

更新时间：2024-04-26 01:48:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

数据结构第五版上机实验答案推荐度：
相关推荐

淮海工学院

数据结构实验指导书

计算机软件教研室

实验1线性表的抽象数据类型的实现

实验目的

1）掌握线性表的顺序存储结构和链式存储结构； 2）熟练掌握顺序表和链表基本算法的实现；

3）掌握利用线性表数据结构解决实际问题的方法和基本技巧；

4）按照实验题目要求独立正确地完成实验内容（编写、调试算法程序，提交程序清单及及相关实验数据与运行结果）； 5）按时提交实验报告。

实验环境

计算机、C语言程序设计环境

实验学时

2学时，必做实验。

实验内容

一、顺序表的基本操作实现实验

要求：数据元素类型ElemType取整型int。按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出）：

1）创建任意整数线性表（即线性表的元素值随机在键盘上输入），长度限定在25之内； 2）打印（遍历）该线性表（依次打印出表中元素值）； 3）在线性表中查找第i个元素，并返回其值； 4）在线性表中第i个元素之前插入一已知元素； 5）在线性表中删除第i个元素；

6）求线性表中所有元素值（整数）之和；

二、链表（带头结点）基本操作实验

要求：数据元素类型ElemType取字符型char。按照动态单循环链表结构实现如下算法（各算法边界条件适当给出）：

1）创建任意字符型有序（递增排序）单循环链表（即链表的字符元素随机在键盘上输入），长度限定在15之内；

2）打印（遍历）该链表（依次打印出表中元素值）；

3）在链表中查找第i个元素，i合法返回元素值，否则，返回FALSE；

4）在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE； 5）在链表中按照有序方式插入一已知字符元素； 6）在线性表中删除第i个结点； 7）计算链表的长度。

实验步骤

一、顺序表的源程序 #include

#include #include

int list[25];int i,n,a,sum=0,k,l; int eleminsert;

/*------------------创建函数--------------*/ void initlist()

{

printf(\scanf(\

if(n>25||n<1) {printf(\printf(\for(i=0;i

{scanf(\ }

return; }

/*------------------打印函数--------------*/ void Print(int list[],int n) {

int j;

for(j=0;j

/*------------------查找函数------------*/ int Search(int list[],int n,int m) {

if(m<1||m>n){printf(\

else printf(\return; }

/*----------------插入函数------------*/

void Insert(int list[],int n,int m,int elem) {

int j;

if(m<1||m>n){printf(\for(j=n-1;j>=m-1;i--) {list[j+1]=list[j];} list[m-1]=elem; n=n+1;

printf(\Print(list,n); return; }

/*---------------删除函数-----------*/ void Delete(int list[],int n,int m) {

int q;int j; if(m<1||m>n)

{printf(\j=list[m-1];

for(q=m-1;q<=n;q++) {list[q]=list[q+1];}

printf(\Print(list,n-1); free(j); return; }

/*-------------求和函数------------*/ void Sum(int list[],int n,int sum) {

int j;

for(j=0;j

{sum=sum+list[j];}

printf(\return; }

void menu() {

int j;

/*------------菜单函数------------*/

menulab:

printf(\printf(\printf(\printf(\printf(\printf(\printf(\printf(\printf(\printf(\checklabel: scanf(\if(j<0||j>7)

{printf(\ goto checklabel; }

printf(\printf(\getchar();

clrscr(); /*clear screen*/

switch(j)

{

case 1:/*创建任意整数线性表*/ initlist();

clrscr(); /*clear screen*/ goto menulab;

case 2: /*打印（遍历）该线性表*/ printf(\Print(list,n);

printf(\getchar();

clrscr(); /*clear screen*/ goto menulab;

case 3:/*在线性表中查找第i个元素，并返回其值*/

printf(\scanf(\getchar();

Search(l,n,a);

printf(\ getchar();

clrscr(); /*clear screen*/

goto menulab;

case 4:/*在线性表中第i个元素之前插入一已知元素*/

printf(\scanf(\

Insert(list,n,k,eleminsert);

printf(\getchar();

clrscr(); /*clear screen*/ goto menulab;

case 5:/*在线性表中删除第i个元素*/

printf(\scanf(\n=n+1;

Delete(list,n,l); n=n-1;

printf(\getchar();

clrscr(); /*clear screen*/

goto menulab;

case 6:/*求线性表中所有元素值（整数）之和*/ Sum(list,n,sum);

printf(\

getchar();

clrscr(); /*clear screen*/ goto menulab;

case0:/*退出程序*/

printf(\getchar(); exit(0); }}

void main() {

void menu(); menu(); }

二、链表（带头结点）的源程序 #include #include

struct LNode{ char elem;

struct LNode* next; }*l,*p,*new;

int i,a,k,n;char c,s;

/*----------------创建函数-------------*/ void intilist(void) {

l=(struct LNode *)malloc(sizeof(struct LNode)); l->next=NULL;

clrscr();

printf(\ scanf(\ getchar(); if(n>15)

printf(\

for(i=n;i>0;i--) {

new=(struct LNode *)malloc(sizeof(struct LNode)); new->next=l->next;l->next=new;

}

p=l;

while(p->next!=NULL) p=p->next; p->next=l;

printf(\p=l->next;

for(i=1;i<=n;i++) {

scanf(\ p=p->next; } return; }

/*----------------排序函数-------------*/ void Sequence(struct LNode * l, int n) {

int i;char swap,*e,*f; for(i=1;i<=n-1;i++) { p=l->next;

while(p->next!=l)

{if(p->elem>p->next->elem) {e=&p->elem; f=&p->next->elem;swap=*e;*e=*f;*f=swap;} p=p->next;} }

return;

}

/*----------------打印函数-------------*/

void Print(struct LNode * l, int n) {

int i;

p=l->next;

for(i=1;i<=n;i++) {

printf(\p=p->next; }

printf(\return; }

/*----------------查找函数-------------*/ void Locate(struct LNode * l, int n,int m) {

int i;

if(m>n) { printf(\else { p=l;

for(i=1;i<=m;i++) {p=p->next;}

printf(\} return; }

/*------已知字母匹配首结点查找函数------*/

void LocateLNode(struct LNode * l, int n,char m) { int i;

p=l;

for(i=1;i<=n;i++)

{p=p->next; if(p->elem==m) {printf(\if(i>n) printf(\return; }

/*----------------插入函数-------------*/ void Insert(struct LNode * l, int n,char m) {

new=(struct LNode *)malloc(sizeof(struct LNode)); new->next=l->next; l->next=new; new->elem=m; n=n+1;

Sequence(l,n); Print(l,n);

return; }

/*----------------删除函数-------------*/ void Delete(struct LNode * l, int n,int m) { int i; p=l;

for(i=1;inext;}

p->next=p->next->next; n=n-1;

printf(\Print(l,n); return;}

/*----------------求表长函数-------------*/ void Length(int n) {

int i;int length=0; for(i=1;i<=n+1;i++)

{length=length+sizeof(struct LNode);}

printf(\return; }

/*----------------菜单函数-------------*/ void menu() { int j;

menulab:

printf(\printf(\printf(\printf(\printf(\printf(\printf(\printf(\printf(\printf(\printf(\checklabel: scanf(\if(j<0||j>7)

{printf(\ goto checklabel; }

printf(\printf(\getchar();

clrscr(); /*clear screen*/

switch(j) {

case 1:/*创建链表并输入元素*/ intilist();

clrscr(); /*clear screen*/ goto menulab;

case 2: /*排序并打印链表*/

Sequence(l,n);

printf(\Print(l,n);

printf(\getchar();

clrscr(); /*clear screen*/ goto menulab;

case 3:/*查找第i个元素*/

printf(\scanf(\

Locate(l,n,a);

printf(\ getchar();

clrscr(); /*clear screen*/ goto menulab;

case 4:/*查找与已知字符相同的第一个结点*/

printf(\scanf(\LocateLNode(l,n,c);

printf(\getchar();

clrscr(); /*clear screen*/ goto menulab;

case 5:/*插入已知字符的结点*/

printf(\scanf(\Insert(l,n,s); n=n+1;

printf(\getchar();

clrscr(); /*clear screen*/ goto menulab;

case 6:/*删除第i个结点*/

printf(\scanf(\

if(k<1||k>n)printf(\else{Delete(l,n,k);} n=n-1; getchar();

clrscr(); /*clear screen*/ goto menulab;

case 7:/*计算链表长度*/

Length(n);

printf(\

getchar();

clrscr(); /*clear screen*/ goto menulab;

case0:/*退出链表程序*/

printf(\getchar(); exit(0); }}

/*------------------主函数---------------*/ main() {

void menu(void); menu(); }

测试数据与实验结果（可以抓图粘贴）一、顺序表程序抓图及其简要说明

菜单选项如下图所示：该菜单由八个函数组成，实现八项功能。

关于顺序表的函数的具体执行情况请参照链表说明和抓图。两程序执行情况基本类似。

二、链表（带头结点）程序抓图及其简要说明

菜单函数如下图所示：该菜单包含了程序的八项基本操作，实现了创建、排序、查找、以及删除等功能。具体执行过程如下。

选择菜单1，创建一个链表。

如上图所示的操作，其余也是一样例如，当选择“2”时如下图：

当执行1时如下图：创建链表完成，按任意键返回到菜单。

当执行2时如下图：链表排序成功，将排好的链表打印出来，按任意键返回到菜单。

当执行3时如下图：按排序位置查找节点，并打印出查得元素，按任意键返回到菜单。

当执行4时如下图：按元素查找与之相同的节点，返回TURE或FALSE，按任意键返回到菜单。

当执行5时如下图：插入元素，自动排序，打印出新链表元素，按任意键返回到菜单。

当执行6时如下图：删除一元素，打印出要删除的元素，按任意键返回到菜单。

当执行7时如下图：打印出链表长度，按任意键返回到菜单。

当执行0时：退出程序，按任意键返回到菜单。（图略）

实验2 栈和队列的算法实现实验2栈和队列的算法实现

实验目的

1）掌握栈与队列的数据类型描述及特点；

2）熟练掌握栈的顺序和链式存储存表示与基本算法的实现； 3）掌握队列的链式存储表示与基本操作算法实现; 4) 掌握栈与队列在实际问题中的应用和基本编程技巧;

4）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）； 5）认真书写实验报告,并按时提交。

实验环境

计算机、C语言程序设计环境

实验学时

2学时，必做实验。

实验内容

汉诺塔问题。程序结果：给出程序执行过程中栈的变化过程与圆盘的搬动状态。

实验步骤

源程序：

/ *编译环境Visual C++6.0 */

#include

void move(int h,char c,char f) { }

printf(\

void hanoi(int n,char x,char y,char z) {

if(n==1) move(1,x,z); else { }

hanoi(n-1,x,z,y); move(n,x,z); hanoi(n-1,y,x,z);

}

void main(void) { int flag;

}

do {

printf(\汉诺塔问题\\n\\n\printf(\开始\\n\printf(\退出\\n\printf(\请选择:\scanf(\printf(\switch(flag) {

case 1:

printf(\输入盘子的总数:\int total;

scanf(\printf(\移动步骤:\\n\hanoi(total,'A','B','C');

break; case 2:

printf(\确认退出吗!Y/N:\char temp; cin>>temp;

if(temp=='Y'||temp=='y') {

flag=3;

printf(\谢谢使用!\\n\\n\

} break; default: printf(\您的选择超出范围,1--2请选择!\\n\}

printf(\}while(flag!=3);

测试数据与实验结果（可以抓图粘贴）

int BTreeCount();

// 用于求二叉树所有结点数的递归函数,被函数BTreeCount调用 int Count(BTreeNode *&BT); // 求二叉树中所有叶子结点数 int BTreeLeafCount();

// 用于求二叉树中所有叶子结点数的递归函数,被函数BTreeLeafCount调用 int LeafCount(BTreeNode *&BT); // 输出二叉树的所有叶子结点 void BTreeLeafPrint();

// 用于输出二叉树的所有叶子结点的递归函数,被函数BTreeLeafPrint调用 void LeafPrint(BTreeNode *&BT);

/***********************二叉树中从根结点到叶子结点的路径相关函数****************/ // 输出从根结点到叶子结点的路径,以及最长路径

void BTreePath();

// 输出从根结点到叶子结点的路径的递归函数,被函数BTreePath调用 void PathLeaf(BTreeNode *&BT,ElemType path[],int pathlen); // 求最长路径的递归函数,被函数BTreePaht调用

void BTreeLongpath(BTreeNode *&BT,ElemType path[],int pathlen,ElemType longpath[],int &longpathlen);

// 非递归方法输出从根结点到叶子结点的路径 void BTreePath_N1();

// 返回data域为x的结点指针 void BTreeFind(ElemType x);

// 返回data域为x的结点指针的递归函数,被函数BTreeFind调用 BTreeNode *FindNode(BTreeNode *&BT,ElemType x);

/*************************************线索二叉树****************************/

// 线索化二叉树

void CreateThread();

// 中序线索化二叉树的递归函数,被函数CreateThread调用 void InOrderThread(BTreeNode *&BT,BTreeNode *&pre); // 中序线索化二叉树中实现中序遍历,被函数CreateThread调用 void ThInOrder(BTreeNode *&BT);

/****************************销毁二叉数的相关成员函数***********************/

// 置空二叉树 void BTreeClear();

// 用于清除二叉树的递归函数,被函数BTreeClear和~BinaryTree调用 void Clear(BTreeNode *&BT); // 析构函数,清除二叉树 ~BinaryTree();

};

/******************************创建二叉数的相关成员函数*************************/

// 按照二叉树的广义表表示创建二叉树 void BinaryTree::CreateBTree1() {

cout<<\输入广义表形式的二叉树:\root=NULL; // 给树根指针置空

Create1(root); }

// 递归创建二叉树,被函数CreateBTree1调用 void BinaryTree::Create1(BTreeNode *&BT)

{ BTreeNode *stack[MAXSIZE],*p=NULL; int k,top=-1;

char ch; while((ch=getchar())!='#')

{ switch(ch)

{

case '(': top++;

stack[top]=p;

k=1; // 即将建立左结点

break; case ')': top--; break; case ',':

k=2; // 即将建立右结点 break; default: if(!(p=new BTreeNode))

{ }

cout<<\堆内存分配失败\\n\exit(1);

p->data=ch;

p->left=p->right=NULL;

if(BT==NULL) // p指向二叉树的根结点,建立根结点 BT=p;

else // 已经建立根结点 {

if(k==1) // 建立左结点

}

stack[top]->left=p;

else // 建立右结点 stack[top]->right=p;

}//switch(ch)

}//while

}

// 按一定次序输入二叉树中结点的值(一个字符),空格表示空树 void BinaryTree::CreateBTree2(int mark) {

switch(mark) { case 1:

puts(\按先序输入二叉树:\break;

case 2: puts(\按中序输入二叉树:\ break; case 3: }

puts(\按后序输入二叉树:\break;

root=NULL; // 给树根指针置空

BTreeNode *&p=root; // 定义p为指向二叉树结点的指针 Greate2(p,mark); }

// 递归创建二叉树,被函数CreateBTree2调用

void BinaryTree::Greate2(BTreeNode *&BT,int mark) {

char ch;

ch=getchar(); switch(mark) {

case 1: // 先序创建 if(ch==' ')

BT=NULL; else {

if(!(BT=new BTreeNode)) {

cout<<\堆内存分配失败\\n\exit(1);

}

BT->data=ch;

Greate2(BT->left,mark);

Greate2(BT->right,mark); }

break; break;

case 2: case 3: break; } }

// 复制二叉树

void BinaryTree::BTreeCopy(BTreeNode *&root,BTreeNode *&BT) { if(root) {

if(!(BT=new BTreeNode)) {

exit(1); }

BT->data=root->data;

BTreeCopy(root->left,BT->left); BTreeCopy(root->right,BT->right); }

else

BT=NULL; }

/*******************************遍历二叉数的相关成员函数************************/

// 按任一种遍历次序输出二叉树中的所有结点 void BinaryTree::TraverseBTree(int mark) {

srand(time(NULL)); // 产生随机种子数,用来选择相同顺序遍历的不同算法 Traverse(root,mark); cout<

}

// 用于遍历的递归函数,被函数TraverseBTree调用 void BinaryTree::Traverse(BTreeNode *&BT,int mark) {

int option; switch(mark) {

case 1: // 先序遍历 {

option=rand()%3+1; switch(option) // 随机选择一种先序算法 {

case 1:

PreOrder(BT); break;

case 2: PreOrder_N1(BT); break; case 3: PreOrder_N2(BT); }

break;

}

case 2: // 中序遍历

{

option = rand()%3 + 1;

switch(option) // 随机选择一种中序算法 { case 1:

InOrder(BT); break;

case 2: InOrder_N1(BT); break; case 3: InOrder_N2(BT); break; }

break;

}

case 3: // 后序遍历 {

option=rand()%3+1;

switch(option) // 随机选择一种先序算法 {

case 1:

PostOrder(BT); break;

PostOrder_N1(BT); break;

case 2:

case 3: PostOrder_N2(BT);

} { }

break;

}

break;

case 4: // 层序遍历

LayerOrder(BT); break;

default: cout<<\的值无效!遍历失败!\} }

// 先序遍历的递归函数

void BinaryTree::PreOrder(BTreeNode *&BT) {

if(BT!=NULL) { } }

// 先序遍历的非递归函数一

void BinaryTree::PreOrder_N1(BTreeNode *&BT) {

BTreeNode *p; struct

{ BTreeNode *pt; int tag;

}stack[MAXSIZE]; int top=-1; top++;

stack[top].pt=BT; stack[top].tag=1;

while(top>-1) // 栈不空时循环 {

cout<data<<' '; PreOrder(BT->left); PreOrder(BT->right);

if(stack[top].tag==1) // 不能直接访问 {

p=stack[top].pt;

top--;

if(p!=NULL) // 按右,左,结点顺序进栈,后进先出,即先序遍历

} }

{ }

top++;

stack[top].pt=p->right; // 右孩子入栈 stack[top].tag=1; top++;

stack[top].pt=p->left; // 左孩子入栈 stack[top].tag=1; top++;

stack[top].pt=p; // 根结点入栈 stack[top].tag=0; // 可以直接访问

}

if(stack[top].tag==0) // 可以直接访问 { }

cout<data<<' '; top--;

// 先序遍历的非递归函数二

void BinaryTree::PreOrder_N2(BTreeNode *&BT) {

BTreeNode *stack[MAXSIZE],*p; int top = -1;

if(BT!=NULL) { top++; // 根结点入栈 stack[top] = BT;

while(top>-1) // 栈不空时循环 {

p=stack[top]; top--;

cout<data<<\

if(p->right != NULL) // 右孩子入栈 { }

if(p->left != NULL) // 左孩子入栈 {

top++;

stack[top] = p->left; top++;

stack[top] = p->right;

} }//while

}//if(root!=NULL) }

// 中序遍历的递归函数

void BinaryTree::InOrder(BTreeNode *&BT) {

if(BT!=NULL) { InOrder(BT->left); } }

// 中序遍历的非递归函数一

void BinaryTree::InOrder_N1(BTreeNode *&BT) {

BTreeNode *p; struct {

BTreeNode *pt; int tag;

}stack[MAXSIZE]; int top = -1; top++;

stack[top].pt = BT; stack[top].tag = 1;

while(top>-1) // 栈不空时循环 {

cout<data<<' '; InOrder(BT->right);

if(stack[top].tag == 1) // 不能直接访问 {

p = stack[top].pt; top--;

if(p!=NULL) // 按右,左,结点顺序进栈,后进先出,即先序遍历 {

top++;

stack[top].pt=p->right; // 右孩子入栈 stack[top].tag = 1; top++;

stack[top].pt = p; // 根结点入栈 stack[top].tag = 0; // 可以直接访问 top++;

stack[top].pt =p->left; // 左孩子入栈 stack[top].tag = 1;

} }

}

if(stack[top].tag == 0) // 可以直接访问 { }

cout<data<<' '; top--;

// 中序遍历的非递归函数二

void BinaryTree::InOrder_N2(BTreeNode *&BT) {

BTreeNode *stack[MAXSIZE],*p; int top = -1; if(BT != NULL) {

p = BT;

while(top > -1||p != NULL) { }

while(p != NULL) // 所有左结点入栈 {

top++;

stack[top] = p; p = p->left;

}

if(top > -1) { p = stack[top]; }

top--;

cout<data<<\p = p->right;

}//if }

// 后序遍历的递归函数

void BinaryTree::PostOrder(BTreeNode *&BT) {

if(BT!=NULL) {

PostOrder(BT->left); PostOrder(BT->right); cout<data<<' ';

}

// 后序遍历的非递归函数一

void BinaryTree::PostOrder_N1(BTreeNode *&BT) {

BTreeNode *p; struct {

BTreeNode *pt; int tag;

}stack[MAXSIZE]; int top = -1; top++;

stack[top].pt = BT; stack[top].tag = 1;

while(top>-1) // 栈不空时循环 { } }

// 后序遍历的非递归函数二

if(stack[top].tag == 1) // 不能直接访问 { }

p = stack[top].pt;

top--;

if(p!=NULL) // 按右,左,结点顺序进栈,后进先出,即先序遍历 { }

top++;

stack[top].pt = p; // 根结点入栈 stack[top].tag = 0; // 可以直接访问 top++;

stack[top].pt=p->right; // 右孩子入栈 stack[top].tag = 1;

top++;

stack[top].pt =p->left; // 左孩子入栈 stack[top].tag = 1;

if(stack[top].tag == 0) // 可以直接访问 { }

cout<data<<' '; top--;

void BinaryTree::PostOrder_N2(BTreeNode *&BT) {

BTreeNode *stack[MAXSIZE],*p,*q; q=BT;

int top = -1,flag; if(q != NULL)

{ do {

while(q != NULL) // 所有左结点入栈 {

top++;

stack[top] = q; q = q->left;

}

p=NULL; // p指向当前结点的前一个已访问的结点 flag=1; // 设置q的访问标记为已访问过 while(top > -1&&flag) {

q = stack[top]; // 取出当前栈顶元素

if(q->right == p) // 当右孩子不存在或已被访问时,则访问 {

cout<data<<\

top--;

p = q; // p指向刚被访问的结点

} else { q = q->right; // 指向右孩子

flag = 0; // 设置未被访问的标记

}

} }while(top>-1); }//if }

// 层序遍历的非递归函数

void BinaryTree::LayerOrder(BTreeNode *&BT) {

BTreeNode *Queue[MAXSIZE]; // 定义存储二叉树结点指针的数组空间作为队列使用 int front=0,rear=0; // 定义队首指针和队尾指针,初始均置0表示空队 BTreeNode *p; if(BT!=NULL) {

rear=(rear+1)%MAXSIZE; // 后移队尾指针

Queue[rear]=BT; // 将树根结点指针进队

}

while(front!=rear) // 当队列非空时执行循环 { } }

// 按照二叉树的广义表表示输出整个二叉树 void BinaryTree::GPrintBTree() {

GPrint(root); cout<

}

// 广义表形式输出整个二叉树的递归函数,被函数Print调用 void BinaryTree::GPrint(BTreeNode *&BT) {

if(BT==NULL)

return; // 树为空时返回 else // 否则执行如下操作 { }

front=(front+1)%MAXSIZE; // 后移队首指针 p=Queue[front]; // 删除队首结点的值

cout<data<<' '; // 输出队首结点的值

if(p->left!=NULL) // 若结点存在左孩子,则左孩子结点指针进队 {

rear=(rear+1)%MAXSIZE; Queue[rear]=p->left;

}

if(p->right!=NULL) // 若结点存在右孩子,则右孩子结点指针进队 { }

rear=(rear+1)%MAXSIZE; Queue[rear]=p->right;

cout<data; // 输出根结点的值 if(BT->left!=NULL||BT->right!=NULL) { }

cout<<'('; // 输出左括号 GPrint(BT->left); // 输出左子树 if(BT->right!=NULL)

cout<<','; // 若右子树不为空则输出逗号分隔符 GPrint(BT->right); // 输出右子树 cout<<')'; // 输出右括号

}

// 以凹凸表示法输出二叉树

void BinaryTree::OPrintTree() {

cout<

BTreeNode *stack[MAXSIZE],*p;

int level[MAXSIZE][2],top=-1,n,i,width=4; int maxwidth=40; char type[20];

char *pre_type=type; if(root!=NULL) {

top++; // 根结点入栈 stack[top]=root;

level[top][0]=width;

level[top][1]=2; // 2表示是根 while(top>-1) {

p=stack[top]; // 退栈并凹入显示该结点值 n=level[top][0]; switch(level[top][1]) {

case 0: pre_type=\左结点\ break; case 1: pre_type=\右结点\ break; case 2:

pre_type=\根结点\}

for(i=1;i<=n;i++) // n为显示场宽,字符以右对齐显示 cout<<\cout<<\for(i=n+1;i<=maxwidth;i+=2) cout<<\cout<

if(p->right!=NULL) {

top++; // 将右子树树根结点入栈 stack[top]=p->right;

level[top][0]=n+width; // 显示场宽增加width level[top][1]=1; // 1表示右子树

}

if(p->left!=NULL) { top++; // 将左子树树根结点入栈

stack[top]=p->left;

level[top][0]=n+width; // 显示场宽增加width

level[top][1]=0; // 0表示左子树 } }//while

}//if }

/******************计算二叉数深度,宽度,叶子,结点的相关成员函数******************/

// 求二叉树的深度

int BinaryTree::BTreeDepth() {

return Depth(root); }

// 用于求二叉树深度的递归函数,被BTreeDepth调用 int BinaryTree::Depth(BTreeNode *&BT) {

if(BT==NULL) return 0; // 对于空树,返回0并结束递归

else { int dep_left=Depth(BT->left); // 计算左子树的深度 int dep_right=Depth(BT->right); // 计算右子树的深度 }

if(dep_left>dep_right) // 返回树的深度 return dep_left+1; else return dep_right+1;

}

// 求二叉树的宽度

int BinaryTree::BTreeWidth() {

struct Queue {

int layer; // 结点的层次编号

BTreeNode *p; // 结点指针

}Queue[MAXSIZE]; // 定义顺序队列,存储二叉数所有的结点 int front,rear; front=rear=0;

int cur_layer; // 存储当前结点所在的层数 BTreeNode *q=root; if(q!=NULL) {

rear++;

Queue[rear].p=q; // 根结点指针入队

Queue[rear].layer=1; // 根结点的层次编号为1

while(rear!=front) // while循环通过层次遍历求每个结点的层次 {

front++;

q=Queue[front].p; // 队头出队

cur_layer=Queue[front].layer; // 当前结点所在的层数 if(q->left!=NULL) // 左孩子入队 { }

rear++;

Queue[rear].p=q->left;

Queue[rear].layer=cur_layer+1; // 当前结点的孩子在该结点的下一层

if(q->right!=NULL) // 右孩子入队 {

rear++;

Queue[rear].p=q->right;

Queue[rear].layer=cur_layer+1; // 当前结点的孩子在该结点的下一层

} }//while

int max_layer=0,i=1,n;

cur_layer=1; // 从第一层开始

while(i<=rear) // 通过比较相同层次的结点数求树的深度 {

n=0;

while(i<=rear&&Queue[i].layer==cur_layer) { n++; // n累计cur_lay层中的结点层次 i++;

}

cur_layer=Queue[i].layer; // 取下一个层次,此时Queue[i]存放下一个层次的第一个if(n>max_layer)

max_layer=n; // 将最大层的结点树赋给max

结点

}

return max_layer;

} else }

return 0;

// 求二叉树中所有结点数

int BinaryTree::BTreeCount() {

return Count(root); }

// 用于求二叉树中所有结点数的递归函数,被函数BTreeCount调用 int BinaryTree::Count(BTreeNode *&BT) {

if(BT==NULL) return 0;

else return Count(BT->left)+Count(BT->right)+1; }

// 求二叉树中所有叶子结点数 int BinaryTree::BTreeLeafCount() {

return LeafCount(root); }

// 用于求二叉树中所有叶子结点数的递归函数,被函数BTreeLeafCount调用 int BinaryTree::LeafCount(BTreeNode *&BT) {

if(BT == NULL)

return 0;

else if(BT->left==NULL&&BT->right==NULL) return 1; else

return LeafCount(BT->left)+LeafCount(BT->right); }

// 输出二叉树的所有叶子结点

void BinaryTree::BTreeLeafPrint() {

LeafPrint(root); }

// 用于输出二叉树的所有叶子结点的递归函数,被函数BTreeLeafPrint调用 void BinaryTree::LeafPrint(BTreeNode *&BT) {

if(BT != NULL) {

if(BT->left == NULL && BT->right==NULL) cout<<\

}

else { }

LeafPrint(BT->left); LeafPrint(BT->right);

}

// 返回data域为x的结点指针

void BinaryTree::BTreeFind(ElemType x) {

BTreeNode *p;

p=FindNode(root,x); if(p!=NULL)

cout<<\在二叉树中\else }

cout<<\不在二叉树中\

// 返回data域为x的结点指针的递归函数,被函数BTreeFind调用 BTreeNode *BinaryTree::FindNode(BTreeNode *&BT,ElemType x) {

BTreeNode *p; if(BT==NULL) return NULL; else if(BT->data==x) return BT; else { } }

/***********************二叉树中从根结点到叶子结点的路径相关函数****************/

// 输出从根结点到叶子结点的路径,以及最长路径 void BinaryTree::BTreePath() {

int longpathlen=0;

ElemType path[MAXSIZE],longpath[MAXSIZE];

p=FindNode(BT->left,x);

if(p!=NULL) return p; else return FindNode(BT->right,x);

PathLeaf(root,path,0);

cout<

BTreeLongpath(root,path,0,longpath,longpathlen); cout<<\第一条最长为 \的路径:\for(int i=longpathlen-1;i>=0;i--)

cout<<\cout<

// 输出从根结点到叶子结点的路径的递归函数,被函数BTreePath调用

void BinaryTree::PathLeaf(BTreeNode *&BT,ElemType path[],int pathlen) {

if(BT!=NULL) {

if(BT->left==NULL&&BT->right==NULL) // BT为叶子结点 {

cout<<\叶子结点\到根结点路径:\cout<data<<\

for(int i=pathlen-1;i>=0;i--) cout<

} else { }

path[pathlen]=BT->data; // 将当前结点放入路径中 pathlen++; // 路径长度加1

PathLeaf(BT->left,path,pathlen); // 递归扫描左子树 PathLeaf(BT->right,path,pathlen); // 递归扫描右子树 pathlen--; // 恢复环境

} }

// 求最长路径的递归函数,被函数BTreePaht调用

void BinaryTree::BTreeLongpath(BTreeNode *&BT,ElemType path[],int pathlen,ElemType longpath[],int &longpathlen) {

if(BT==NULL) {

if(pathlen>longpathlen) // 若当前路径更长,将路径保存在longpath中 { }

for(int i=pathlen-1;i>=0;i--) longpath[i]=path[i]; longpathlen=pathlen;

}

else { path[pathlen]=BT->data; // 将当前结点放入路径中 } }

// 非递归方法输出从根结点到叶子结点的路径 void BinaryTree::BTreePath_N1() {

BTreeNode *q=root; struct {

BTreeNode *pt; // 存放当前结点的指针 pathlen++; // 路径长度加1

BTreeLongpath(BT->left,path,pathlen,longpath,longpathlen); // 扫描左子树 BTreeLongpath(BT->right,path,pathlen,longpath,longpathlen); // 扫描右子树 pathlen--; // 恢复环境

int parent; // 存放双亲结点在队列中的位置 }Queue[MAXSIZE]; int front,rear,p; front=rear=-1; rear++;

Queue[rear].pt=q; // 根结点入队

Queue[rear].parent=-1; // 根结点没有双亲结点 while(front

if(q->left==NULL&&q->right==NULL) // q为叶子结点 { }

if(q->left!=NULL) // 左孩子入队 {

rear++;

Queue[rear].pt=q->left; Queue[rear].parent=front;

cout<<\叶子结点\到根结点路径:\p=front;

while(Queue[p].parent!=-1) // p指向根结点时退出循环 { }

cout<data<<\p=Queue[p].parent;

cout<data<

}

if(q->right!=NULL) // 右孩子入队 { rear++;

Queue[rear].pt=q->right; Queue[rear].parent=front;

} }//while cout<

/*************************************线索二叉树********************************/

// 线索化二叉树

void BinaryTree::CreateThread() {

BTreeNode *pre;

BTreeNode *t_root;

BTreeCopy(root,t_root); // 复制二叉树root给t_root BTreeNode *throot; // 二叉线索树的头结点指针 throot=new BTreeNode; // 创建二叉线索树头结点 throot->ltag=0; throot->rtag=1;

throot->right=throot;

if(root==NULL) throot->left=throot; // 空二叉树 else {

throot->left=t_root;

pre=throot; // pre是p的前驱结点

InOrderThread(t_root,pre); // 中序线索化二叉树

pre->right=throot; // 最后处理,加入指向根结点的线索 pre->rtag=1;

throot->right=pre; // 根结点右线索化 }

ThInOrder(throot); // 中序线索化二叉树中实现中序遍历 }

// 中序线索化二叉树的递归函数,被函数CreateThread调用

void BinaryTree::InOrderThread(BTreeNode *&BT,BTreeNode *&pre) {

if(BT!=NULL) {

} }

InOrderThread(BT->left,pre); // 左子树线索化 if(BT->left==NULL) // 前驱线索 { BT->left=pre; // 建立当前结点的前驱线索 }

else BT->ltag=0;

if(pre->right==NULL) // 后续线索 { }

pre->right=BT; // 建立前驱结点的后续线索 pre->rtag=1; BT->ltag=1;

else

pre->rtag=0; pre=BT;

InOrderThread(BT->right,pre); // 右子树线索化

// 中序线索化二叉树中实现中序遍历,被函数CreateThread调用 void BinaryTree::ThInOrder(BTreeNode *&BT) {

BTreeNode *p=BT->left; // p指向根结点 while(p!=BT) // 空树或遍历结束时,p==BT { }

while(p->ltag==0) p=p->left;

cout<<\访问其左子树为空的结点 while(p->rtag==1&&p->right!=BT) { }

p=p->right;

cout<<\访问后续结点

p=p->right;

cout<

/******************************销毁二叉数的相关成员函数*************************/

// 置空二叉树

void BinaryTree::BTreeClear() {

Clear(root);

}

// 析构函数,清除二叉树 BinaryTree::~BinaryTree() {

Clear(root);

}

// 用于清除二叉树的递归函数

void BinaryTree::Clear(BTreeNode *&BT) {

if(BT!=NULL) { } }

2) 源文件Btree.cpp

#include \

int main(void) {

BinaryTree Btree; char option;

int flag=0; // 标志当前二叉树是否已经创建,初始化为0,即还没有创建 do { cout<<\二叉树演示程序\\n\\n\ if(flag==0) // 标志二叉树还没有创建

// 当二叉树非空时进行如下操作 Clear(BT->left); // 删除左子树 Clear(BT->right); // 删除右子树 delete BT; // 删除根结点 BT=NULL;

cout<<\二叉树创建\else // 标志二叉树已经创建

cout<<\二叉树创建＋\cout<<\二叉树遍历\cout<<\二叉树属性\cout<<\二叉树路径\cout<<\二叉树线索\cout<<\二叉树置空\cout<<\退出\cout<<\请选择: \cin>>option;

cout<

switch(option) {

case '1': // 二叉树创建

{

char option1;

do { if(flag==0) // 标志二叉树还没有创建

cout<<\二叉树创建\else // 标志二叉树已经创建

cout<<\二叉树创建＋\

cout<<\广义表形式输入\cout<<\先序式输入\cout<<\返回主菜单\cout<<\请选择: \cin>>option1; cout<

case '1': // 广义表形式输入

{

Btree.CreateBTree1();

flag=1; // 标志二叉树已经创建

cout<<\

cin.get(); cin.get(); break; } { }

case '2': // 先序式输入

Btree.CreateBTree2(1);

flag=1; // 标志二叉树已经创建

cout<<\cin.get(); cin.get(); break;

case '3': // 返回主菜单

break;

cout<<\您的选择超出范围,请重新选择\cout<<\default:

cin.get(); cin.get();

} {

}

cout<<\}while(option1!='3'); break;

case '2': // 二叉树遍历

char option2; do {

cout<<\二叉树遍历\

cout<<\先序遍历\cout<<\中序遍历\cout<<\后序遍历\cout<<\层序遍历\

cout<<\广义表式遍历\cout<<\凹凸式遍历\cout<<\查找结点\cout<<\返回主菜单\cout<<\请选择: \cin>>option2; cout<

switch(option2) {

case '1': // 先序遍历

{

cout<<\先序遍历: \

Btree.TraverseBTree(1);

cout<<\cin.get();

cin.get(); break; }

case '2': // 中序遍历

{

cout<<\中序遍历: \

Btree.TraverseBTree(2);

cout<<\cin.get(); cin.get(); break;

}

case '3': // 后序遍历

{

cout<<\后序遍历: \

}

Btree.TraverseBTree(3);

cout<<\cin.get(); cin.get(); break;

case '4': // 层序遍历 { cout<<\层序遍历: \

Btree.TraverseBTree(4);

cout<<\cin.get(); cin.get(); break;

}

case '5': // 广义表式遍历

{

cout<<\广义表式遍历: \

Btree.GPrintBTree();

cout<<\cin.get(); cin.get(); break;

}

case '6': // 凹凸式遍历

{

cout<<\凹凸式遍历: \Btree.OPrintTree();

cout<<\cin.get();

cin.get(); break; }

case '7': // 查找结点

{

cout<<\请输入要查找的数据: \ElemType find; cin>>find;

Btree.BTreeFind(find);

cout<<\cin.get(); cin.get(); break;

}

case '8': // 返回主菜单

{

}

{

break; } default:

cout<<\您的选择超出范围,请重新选择\cout<<\

cin.get(); cin.get(); }

cout<<\}while(option2!='8'); break;

case '3': // 二叉树属性

char option3; do {

cout<<\二叉树属性\

cout<<\显示属性\cout<<\返回主菜单\cout<<\请选择: \cin>>option3; cout<

switch(option3) {

case '1': // 显示属性 { int temp;

temp=Btree.BTreeDepth();

cout<<\二叉树的深度: \temp=Btree.BTreeWidth();

cout<<\二叉树的宽度: \temp=Btree.BTreeCount();

cout<<\二叉树的结点数: \temp=Btree.BTreeLeafCount();

cout<<\二叉树的叶子数: \cout<<\cin.get(); cin.get(); break;

}

case '2': // 返回主菜单

{

break;

}

default: cout<<\您的选择超出范围,请重新选择\ cout<<\

cin.get(); cin.get();

} cout<<\}while(option3!='2'); break;

case '4': // 二叉树路径 {

char option4; do {

cout<<\二叉树属性\

cout<<\显示叶子到根结点的路径\cout<<\返回主菜单\cout<<\请选择: \cin>>option4; cout<

switch(option4)

{

case '1': // 显示叶子到根结点的路径

{

Btree.BTreePath();

cout<<\cin.get(); cin.get();

break; }

case '2': // 返回主菜单 {

}

break;

default: cout<<\您的选择超出范围,请重新选择\

cout<<\cin.get(); cin.get();

}

cout<<\

}while(option4!='2'); break;

}

case '5': // 二叉树线索 { char option4;

do {

cout<<\二叉树线索\

cout<<\中序线索\cout<<\返回主菜单\cout<<\请选择: \cin>>option4; cout<

switch(option4) {

case '1': // 中序线索 {

}

cout<<\中序线索化二叉树内中序遍历: \Btree.CreateThread();

cout<<\cin.get(); cin.get(); break;

case '2': // 返回主菜单 {

break; } default: cout<<\您的选择超出范围,请重新选择\

cout<<\ cin.get(); cin.get(); }

cout<<\

}while(option4!='2'); break;

}

case '6': // 二叉树置空

{

cout<<\是否置空当前二叉树(Y/N): \char dtemp;

cin>>dtemp;

if(dtemp=='Y'||dtemp=='y') {

Btree.BTreeClear();

flag=0; // 标志二叉树还没有创建

}

cout<<\cin.get(); cin.get();

cout<<\

break; }

case '7': // 退出

{ }

cout<<\是否退出(Y/N): \char temp; cin>>temp;

if(temp=='Y'||temp=='y')

option='~';

cout<<\cin.get(); cin.get();

cout<<\break;

case '~': // 真正退出 break;

default: cout<<\您的选择超出范围,请重新选择\ }

cout<<\cin.get(); cin.get();

cout<<\

}while(option!='~'); return 0; }

测试数据与实验结果（可以抓图粘贴）

以下共10幅图片，分别展示如下内容：

1) 创建二叉树：广义表式创建和先序创建；

2) 遍历二叉树：先，中，后，层序遍历，广义表式遍历，凹凸式遍历； 3) 二叉树属性：深度，宽度，结点数，叶子结点数 4) 二叉树路径：叶子结点到根结点的路径； 5）二叉树线索：中序线索二叉树； 6）二叉树置空：清空二叉树。

本文来源：https://www.bwwdw.com/article/zb6p.html

相关文章：

正在阅读：

数据结构全部上机实验及答案 - 图文04-26

企业性质的演化经济学解释_基于对正统经济学解释基础的批判05-07

辽宁石油化工大学分析化学试题01-22

枇杷膏的作用与功效02-13

2010—2011学年度八年级下学期期末考试数学试题04-11

ERP计算和简答09-10

党性分析材料02-17

传感器计算题详解.06-24

小学奥数读本五年级01-31

《电场-电场强度》课堂教学设计03-08

上一篇：介绍贿赂中截留行贿款的行为应如何认定下一篇：《宏观经济学》第二讲：国民收入核算