《数据结构与算法》实验报告三
——二叉树的操作与应用
一.实验目的
熟悉二叉链表存储结构的特征，掌握二叉树遍历操作及其应用
二.实验要求（题目）
说明：以下题目中（一）为全体必做，（二）（三）任选其一完成
（一）从键盘输入二叉树的扩展先序遍历序列，建立二叉树的二叉链表存储结构；
（二）分别用递归和非递归算法实现二叉树的三种遍历；
（三）模拟WindowsXP资源管理器中的目录管理方式,模拟实际创建目录结构,并以二叉链表形式存储,按照凹入表形式打印目录结构（以扩展先序遍历序列输入建立二叉链表结构），如下图所示: (基本要求:限定目录名为单字符;扩展:允许目录名是多字符组合)
三.分工说明
一起编写、探讨流程图，根据流程图分工编写算法，共同讨论修改，最后上机调试修改。
四.概要设计
  实现算法，需要链表的抽象数据类型：
ADT Binarytree {
数据对象：D是具有相同特性的数据元素的集合
数据关系R：
若D为空集，则R为空集，称binarytree为空二叉树；
若D不为空集，则R为{H}，H是如下二元关系；
（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；
（2）若D－{root}不为空，则存在D－{root}＝{D1，Dr}，且D1∩Dr为空集；
（3）若D1不为空，则D1中存在唯一的元素x1，<root，x1>∈H，且存在D1上的关系H1是H的子集；若Dr不为空集，则Dr中存在唯一的元素Xr，<root，Xr>∈H，且存在Dr上的关系Hr为H的子集；H={<root，x1>,<root，Xr>,H1,Hr};
          (4)  (D1,{H1})是一颗符合本定义的二叉树，称为根的左子树，(Dr,{Hr})是一颗符合本定义的二叉树，称为根的右子树。
基本操作:
Creatbitree(&S，definition)
初始条件：definition给出二叉树S的定义
操作结果：按definition构造二叉树S
counter(T)
    初始条件：二叉树T已经存在
    操作结果：返回二叉树的总的结点数
onecount(T)
初始条件：二叉树T已经存在
操作结果：返回二叉树单分支的节点数
Clearbintree(S)
初始条件：二叉树S已经存在
操作结果：将二叉树S清为空树
Bitreeempty(S)
初始条件：二叉树S已经存在
操作结果：若S为空二叉树，则返回TRUE，否则返回FALSE
Bitreedepth(S,&e)
初始条件：二叉树S已经存在
    操作结果：返回S的深度
Parent(S)
初始条件：二叉树S已经存在，e是S中的某个结点
操作结果：若e是T的非根结点，则返回它的双亲，否则返回空
Preordertraverse(S)
初始条件：二叉树S已经存在，Visit是对结点操作的应用函数。
操作结果：先序遍历S，对每个结点调用函数visit一次且仅一次。一旦visit失败，则操作失败。
Inordertraverse (S,&e)
初始条件：二叉树S已经存在，Visit是对结点操作的应用函数。
    操作结果：中序遍历S，对每个结点调用函数visit一次且仅一次。一旦visit失败，则操作失败。
Postordertraverse (&S,e)
初始条件：二叉树S已经存在，Visit是对结点操作的应用函数。
操作结果：后序遍历S，对每个结点调用函数visit一次且仅一次。一旦visit失败，则操作失败。
              }ADT Binarytree
五、详细设计
扩展先序遍历：
# include<stdio.h>
# include<stdlib.h>
#include<string.h>
typedef struct binarytree
{
char data;
struct binarytree *lchild,*rchild;
}BiTreeNode,*BiTree;
void CreateBiTree(BiTree *bt)
{char ch;
ch=getchar();
if(ch=='.') *bt=NULL;
    else
{ 
*bt=(BiTreeNode *)malloc(sizeof(BiTreeNode));
(*bt)->data=ch;
CreateBiTree(&((*bt)->lchild));
CreateBiTree(&((*bt)->rchild));
}
}
void PreOder(BiTree root)
{if(root!=NULL)
{printf("%4c",root->data);
PreOder(root->lchild);
PreOder(root->rchild);
}
}
main()
{
BiTree root;
CreateBiTree(&root);
printf("先序遍历:\n");
PreOder(root);
}
递归算法：
#include "stdio.h"
#define PR printf
#define ERROR 0
#define MAX 100
/*============================建立各结构体===============================*/
typedef struct node
{
  char data;  /*数据域*/
  struct node *lchild;
  struct node *rchild; /*结点的左右指针，分别指向结点的左右孩子*/
}BTNode;
typedef BTNode *DataType;
typedef struct
{
    DataType data[MAX];
    int top;
}SeqStack;
SeqStack *s;
/*============================栈的操作===================================*/
SeqStack *createemptystacks()  /*创建一个空栈*/
{
    SeqStack *s;
    s=(SeqStack*)malloc(sizeof(SeqStack));
    s->top=0;
    return s;
    }
int stackemptys(SeqStack *s)    /*判栈空*/
{   
    return s->top==0;
    }
int stackfulls(SeqStack *s)    /*判栈满*/
{   
    return s->top==MAX;
    }
void pushs(SeqStack *s,DataType x)    /*进栈*/
{
    if(stackfulls(s))
        PR("over flow\n");
    else抽象类的使用   
        s->data[s->top++]=x;
    }
   
void pops(SeqStack *s)    /*退栈*/
{
    if(stackemptys(s))
        PR("underflow\n");
    else
        s->top--;
    }
DataType gettops(SeqStack *s)  /*栈非空时取栈顶元素*/
{
    return s->data[s->top-1];
    }
/*============================建立二叉树==================================*/
BTNode *createbintree()  /*输入扩充的先序序列，建立二叉树*/
{
    BTNode *t;
    char x;
    scanf("%c",&x);
    if(x=='#')
    t=NULL;      /*读入#，返回空指针 */
    else
    {
        t=(BTNode *)malloc(sizeof(BTNode));  /*生成结点*/
        t->data=x;
        t->lchild=createbintree();      /*构造左子树*/
        t->rchild=createbintree();      /*构造右子树*/

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。