树形结构及其应用

2021年1月25日发(作者：围魏救赵)

树形结构及其应用


树形结构及其应用

实验题目：树型结构的建立与遍历设计成
绩报告成绩指导老师

一、

实验目的
1
、学会二叉树这一数据结构的用法，掌握二
叉树的存储结构，包括 二叉树顺序存储结构和链式存储结构。
2
、
熟练掌握二叉树与广义表之间的相互转换方 法。
3
、熟练掌握二叉
树的先序、中序、后序，递归与非递归遍历算法。
4< br>、学会二叉树
线索化方法，并掌握线索二叉树的存储结构。
5
、熟练掌握线索二
叉树的先序、中序、后序的遍历算法。

二、实验要求及实验环境
1
、实验要求：
(1)
至少用两种方法， 编写建立二叉树的二叉链表存储结构的程
序，并用广义表的形式显示并保存二叉树；
(2) < br>采用二叉树的二叉链表存储结构，编写程序实现二叉树的先
序、中序和后序遍历的递归和非递归算 法以及层序遍历算法，并
显示二叉树和相应的遍历序列；
(3)
在二叉树的二叉链表 存储结构基础上，编写程序实现二叉树
的先序、中序和后序线索链表存储结构建立的算法，并用广义表< br>的形式显示和保存二叉树的线索链表；
(4)
在二叉树的线索链表存储结构上，编写程 序分别实现求一个
结点的先序（中序、后序）的后继结点的算法；
(5)
在
(4)
第
1
页

共
1
页


基础上，编写程序实现对线索二叉树进行先序、中序和后序
遍历的非递归算法，并显 示线索二叉树和相应的遍历序列。
2
、实
验环境：
Windows
下 的
dev-c++
、

三、设计思想（本程序中的用到的所有数据类型的定义 ，主
程序的流程图及各程序模块之间的调用关系）
Create a bit-
tree1
．逻辑设计主程序流程递归中序线索化

线索化递归中序 线
索化递归先序线索化以广义表格式输出树递归非递归先序遍历递
归非递归中序遍历递归非递归 后序遍历输出节点的后继节点遍历
后序线索化遍历中序线索化遍历先序线索化线索二叉树链式结构
定义
typedef struct bitnode{ char data; struct bitnode
*lchild,*rchild; bool LTag,RTag; }bnode,*btree;2
．物理设
计
Btree create()
创建一棵树并赋值应用数组栈
btree
a[MAX]Void printBTree(btree T)
以广义表形式打印树
Void
preorder(btree t)
先序递归遍历
Void inorder(btree t)
中序递
归遍历
Void postorder(btree t)
后序递归遍历
btree
copy(btree t)
复制二叉树
Int main
（）主函数
Void
preorder2(btree t)
先序非递归遍历
Void inorder2(btree t)
中
序非递归遍历
Void postorder2(btree t)
后序非递归遍历层序遍
历
void levelorder(btree t)void prethreading(btree p)
先序
线索化
Btree preorderthreading(btree prehead,btrreeT);
先序
线索化
void prethreading(btree p)
先序线索化
Btree
inorderthreading(btree prehead,btrreeT);
中序线索化
void
第
1
页

共
1
页


prethreading(btree p)
先序线索化
Btree
postorderthreading(btree prehead,btrreeT);
后序线索化寻找
字符
X
处于线索树中位置
btree locate(char a,btree t)
中序线
索化后继节点
Btree innext(btree p);
输出后继节点先序线索化
后继节点
Btree prenext(btree p)Void printlist(btree t,bool
a)
广义表形式输出线索化后的二叉树

四、测试结果

五、系统不足与经验体会不能连续输入多个广义表。函数设
计不够简洁。

没有实现非递归线索化

加注释后修改代码方便六、附录：源
代码（带注释）
#include、
h>#include、< br>h>#define MAX100typedef struct bitnode{ char data; struct
bitnode *lchild,*rchild; bool LTag,RTag; }bnode,*btree;
//
建立树线索化结构体
struct bitnode *s[MAX];struct bitnode
*pre=NULL; btree create(){ char ch; scanf(
if(ch==#)
return NULL; else { btree
bt=(btree)malloc(sizeof(bnode)); if(bt==NULL)
return NULL; else{ bt->data=ch; bt->lchild=create();
bt->rchild=create(); return bt; } }}btree create2(){ int
i,j; btree bt,t; char ch; printf(
输入一个整数和一个字符
n
第
1
页

共
1
页


{ bt=(btree)malloc(sizeof(bnode)); if(bt==NULL)
return NULL; else { bt->data=ch; bt->lchild=NULL; bt-
>rchild=NULL; s[i]=bt; if(i==1)
t=bt; else { j=i/2; if(i%2==0)
s[j]->lchild=bt; else s[j]->rchild=bt; } } pri ntf(
输
入一个整数和一个字符
n
t;}//
复制一棵二叉树btree copy(btree BT){ btree
tree;if(BT==NULL)
tree=NULL;else{tree=(btr ee)malloc(sizeof(bnode));tree
->data=BT->data;t ree->lchild=copy(BT->lchild);tree-
>rchild=copy (BT->rchild); }return tree; }//
层序遍历并输出
void levelorder(btree bt){ btree t[MAX]; //
建立队列
int
front=0,rear=1; btree p; t[0]=bt; while(front//
如果队列不为空的话，访问结点值再出队列
{ p=t[front];
printf(
//
左孩子进队列（如果有的话），右孩子进队列（如果有的
话）
t[rear++]=t[front]->lchild; if(p->rchild)
t[rear++]=t[front]->rchild; ++front; }} //
先序递归遍
历并输出
void preorder(btree bt)
{ if (NULL!=bt)
{ printf(
preorder(bt->rchild); } } //
先序非递归遍历并输出
void
第
1
页

共
1
页


preorder2(btree bt){ btree t[MAX]; //
建立数组栈
btree p;
p=bt; int i=0; while(p||i>0)
{ while(p)
/*
根结点先进栈，访问结点值，左孩子依次进栈，直到最左
的孩子进栈
*/ { printf(
>lchild; } if(i>0)
/*
出栈
*/ { p=t[i];i; p=p->rchild; } } //
栈 顶指针出
栈，退至上一层，然后访问右子树，右子树访问完成之后，退至
上一层，直至栈空，节 点访问完成
} //
中序递归遍历并输出
void
inorder(btree bt){ if (NULL!=bt)
{ inorder(bt->lchild); printf(
inorder(bt->rchild); } } //
中序非递归遍历并输出
void
inorder2(btree bt){ btree t[MAX]; //
建立数组栈
btree p;
p=bt; int i=0; while(p||i>0)
{ while(p)
/*
根结点先进栈，左孩子依次进栈，直到最左的孩子进栈

*/ { ++i; t[i]=p; p=p->lchild; } if(i>0)
/*
出栈
*/ { p=t[i];i; printf(
>rchild; } } //
栈顶指针出 栈，退至上一层，访问结点值，然后
访问右子树，右子树访问完成之后，退至上一层，直至栈空，节点访问完成
} //
后序递归遍历并输出
void postorder(btree
bt){ if (NULL!=bt)
第
1
页

共
1
页