数据结构实验报告

2021年1月25日发(作者：editorial)


数据结构实验报告

Data Structures










班级：信息管理与信息系统
1301
班


学号：



1302080114
















姓名：





龚

婧



















In
a
preorder
traversal
，
work
at
a
node
is
perfprmed
before
（
pre
）
its
children
are
r common method of traversing a tree is the postorder traversal. In a postorder
traversal,the work at a node is performed after(post) its children are evaluated.

#include
#include
#include
#include
#include
#include
using namespace std;
//
二叉树的二叉链表存储表示

typedef char TElemType;
typedef struct BiNode
{
TElemType data;
struct BiNode *lchild, *rchild;
} BiNode , *BiTree;
/* *
按先序次 序输入二叉树中结点的值
(
一个字符
)
，空格字符表示空树，构造二叉链表表 示
的二叉树
T
。

*/
Status CreatBiTree(BiTree *T)
{
char ch;
scanf(
//
如果当前输入的字符为空格，则
(*T)
指向空树。

if (ch == ' ')
{
(*T) = NULL;
}
else
{
if (!((*T) = (BiTree)malloc(sizeof(BiNode))))
exit(OVERFLOW);
(*T)->data = ch;
//
生成根结点

CreatBiTree(&((*T)->lchild));
//
构造左子树

CreatBiTree(&((*T)->rchild));
//
构造右子树

}
return OK;
}
/**
假设输入字符为：
ABC##DE#G##F###
，实 际输入时，
#
用空格代替。
*/
#define _CRT_SECURE_NO_W
ARNINGS
#include
#include
#include
typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
//
二叉树的二叉链表

typedef char TElemType;
typedef struct BiNode
{
TElemType data;
struct BiNode *lchild, *rchild;
} BiNode , *BiTree;
//
栈的顺序存储结构

#define STACK_INIT_SIZE 100
//
存储空间初始分配量

#define STACKINCREMENT 10
//
存储空间分配增量

typedef struct
{
BiTree *base;
BiTree *top;
int stacksize;
} Stack;
//
函数声明

Status InitStack(Stack *S);
Status Push(Stack *S, BiTree p);
Status Pop(Stack *S, BiTree *p);
Status GetTop(Stack *S, BiTree *p);
Status StackEmpty(Stack *S);
Status CreatBiTree(BiTree *T);
Status PreOrderTraverse_Recursive(BiTree T, Status(*Visit)(TElemType e));
Status InOrderTraverse_Recursive(BiTree T, Status(*Visit)(TElemType e));
Status PostOrderTraverse_Recursive(BiTree T, Status(*Visit)(TElemType e));
Status PreOrderTraverse_NonRecursive(BiTree T, Status(*Visit)(TElemType e));
Status InOrderTraverse_NonRecursive(BiTree T, Status(*Visit)(TElemType e));
Status InOrderTraverse_NonRecursive_2(BiTree T, Status(*Visit)(TElemType e));
Status PostOrderTraverse_NonRecursive(BiTree T, Status(*Visit)(TElemType e));
Status PrintElement(TElemType e);
int main()
{
BiTree T;
CreatBiTree(&T);
//
先序

PreOrderTraverse_Recursive(T, PrintElement); putchar('n');
PreOrderTraverse_NonRecursive(T, PrintElement); putchar('n');
//
中序

InOrderTraverse_Recursive(T, PrintElement); putchar('n');
InOrderTraverse_NonRecursive(T, PrintElement); putchar('n');
InOrderTraverse_NonRecursive_2(T, PrintElement); putchar('n');
//
后序

PostOrderTraverse_Recursive(T, PrintElement); putchar('n');
PostOrderTraverse_NonRecursive(T, PrintElement); putchar('n');
return 0;
}

/* *
按先序次序输入二叉树中结点的值
(
一个字符
)
，
空格字 符表示空树，
构造二叉链表表示的
二叉树
T
。
*/
Status CreatBiTree(BiTree *T)
{
char ch;
scanf(
//
如果当前输入的字符为空格，则
(*T)
指向空树

if (ch == ' ')
{
(*T) = NULL;
}
else
{
if (!((*T) = (BiTree)malloc(sizeof(BiNode))))
exit(OVERFLOW);
(*T)->data = ch;
//
生成根结点

CreatBiTree(&((*T)->lchild));
//
构造左子树

CreatBiTree(&((*T)->rchild));
//
构造右子树

}
return OK;
}


/*
*
先序遍历二叉树，非递归

Status PreOrderTraverse_NonRecursive(BiTree T, Status(*Visit)(TElemType e))
{
Stack *S;
//
栈
S
中
BiTree p;
S = (Stack*)malloc(sizeof(Stack));
InitStack(S);
Push(S, T); //
根指针进栈。

while (!StackEmpty(S))
{