实现二叉树的各种遍历算法实验报告 一实验题目: 实现二叉树的各种遍历算法 二实验要求:
2.1:<1）输出二叉树 b
（2）输出H节点的左右孩子节点值 （3）输出二叉树b 的深度 （4）输出二叉树 b的宽度 （5）输出二叉树 b的节点个数 （6）输出二叉树 b的叶子节点个数 （7）释放二叉树 b
2.2：<1）实现二叉树的先序遍历 （2）实现二叉树的中序遍历 （3）实现二叉树的后序遍历 三实验内容:
3.1 树的抽象数据类型: ADT Tree{
数据对象D：D是具有相同特性的数据元素的集合。 数据关系 R：若D为空集，则称为空树； 若D仅含有一个数据元素，则R为空集，否则 R={H}，H是如下二元关系：
(1> 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；
(2> 若D-{root}≠NULL，则存在D-{root}的一个划分 D1,D2,D3, …,Dm(m>0>，对于任意∈H。b5E2RGbCAP
(3> 对应于D-{root}的划分，H-{,…,}有唯一的一个划分H1，H2,…,Hm(m>0>，对任意j≠k(1≤j,k≤m>有Hj∩Hk=NULL，且对任
j≠k(1≤j,k≤m>有
Dj∩Dk=NULL,且对任意的i(1≤i≤m>，唯一存在数据元素xi∈Di有
意i(1≤i≤m>,Hi是Di上的二元关系，(Di,{Hi}>是一棵符合本定义的树，称为根root的子树。p1EanqFDPw
基本操作P： InitTree(&T>。
操作结果：构造空树T。DestroyTree(&T>。 初始条件：树T存在。操作结果：销毁树T。 CreateTree(&T,definition>。
初始条件：definition给出树T的定义。 操作结果：按definition构造树T。 ClearTree(&T>。 初始条件：树T存在。 操作结果：将树T清为空树。 TreeEmpty(T>。 初始条件：树T存在。
操作结果：若T为空树，则返回TRUE，否则返回FALSE。 TreeDepth(T>。 Root(T>。
初始条件：树T存在。操作结果：返回T的根。 Value(T,cur_e>。
初始条件：树T存在，cur_e是T中某个结点。 操作结果：返回cur_e的值。 Assign(T,cur_e,value>。
初始条件：树T存在，cur_e是T中某个结点。 操作结果：结点cur_e赋值为value。 Parent(T,cur_e>。
初始条件：树T存在，cur_e是T中某个结点。
操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空”。
LeftChild(T,cur_e>。
初始条件：树T存在，cur_e是T中某个结点。
操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空”。
RightSibling(T,cur_e>。
初始条件：树T存在，cur_e是T中某个结点。
操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则返回“空”。
InsertChild(&T,&p,I,c>。
初始条件：树Ｔ存在，ｐ指向Ｔ中某个结点，1≤i≤p指结点的度＋１，非空树ｃ与Ｔ不相交。
操作结果：插入c为Ｔ中ｐ指结点的第ｉ棵子树。 DeleteChild(&T,&p,i>。
初始条件：树T存在，p指向T中某个结点，1≤i≤p指结点的度。 操作结果：删除Ｔ中ｐ所指结点的第ｉ棵子树。 TraverseTree(T,visit(>>。
初始条件：树T存在，visit是对结点操作的应用函数。
操作结果：按某种次序对T的每个结点调用函数visit(>一次且至多一次。一旦visit(>失败，则操作失败。DXDiTa9E3d
}ADT Tree
3.2存储结构的定义。 typedef struct node {
char data。
struct node *lchild。 struct node *rchild。 }BTNode。 3.3基本操作实现:
void Insertnode(BTNode *&p,int &i,char * str> {
int judge = 0。
if(str[i]>='A'&&str[i]<='Z'>
judge++。
p = (BTNode *>malloc(sizeof(BTNode>>。 p->lchild=NULL。 p->rchild=NULL。 p->data = str[i]。 i++。 }
if(str[i]=='\\0'> { return 。 }
if(str[i]=='('> { i++。 if(!judge> {
p = (BTNode *>malloc(sizeof(BTNode>>。 p->lchild=NULL。 p->rchild=NULL。 }
Insertnode(p->lchild,i,str>。 Insertnode(p->rchild,i,str>。 }
if(str[i]==','||str[i]=='>'> { i++。 return 。 } }
/** 由STR创建二叉链 **/
void CreateBTNode(BTNode *&b,char * str> {
int i = 0。
Insertnode(b,i,str>。 ///以递归形式插入数据，i 会跟着变化} /** 查找e的节点指针 **/
BTNode * FindNode(BTNode * p, char e> {
if(p==NULL> return NULL。 if(p->data==e> return p。 else
BTNode *b = FindNode(p->lchild,e>。 if(b!=NULL> return b。 else
return FindNode(p->rchild,e>。 } }
/** 输出二叉树 **/
void DispBTNode(BTNode * b> {
if(b!=NULL> {
printf(\"%c\。
if(b->lchild!=NULL || b->rchild!=NULL> { printf(\"<\">。
DispBTNode(b->lchild>。
if(b->rchild != NULL>printf(\"，\">。 DispBTNode(b->rchild>。 printf(\"）\">。
} } }
/** 深度 **/
int BTNodeDepth(BTNode *b> {
if(b==NULL> return 0。 else {
int l = BTNodeDepth(b->lchild>。 int r = BTNodeDepth(b->rchild>。 return l>r?l+1:r+1。 } }
void search(BTNode *p,int *a,int k> {
if(p!=NULL> { a[k]++。
search(p->lchild,a,k+1>。 search(p->rchild,a,k+1>。 }
/** 求二叉树的宽度 **/ int BTWidth(BTNode * b> {
int a[maxx], i, kmax = 0。 for(i = 0。i < maxx。 ++i> a[i] = 0。 int k = 0。
search(b,a,k>。
for(i = 0。i < maxx。 ++i> if(a[i]>kmax> kmax = a[i]。 return kmax。 }
/** 求二叉树的节点个数 **/ int Nodes(BTNode *b> {
if(b==NULL> return 0。
else if(b->lchild == NULL && b->rchild == NULL> return 1。 else {
int l = Nodes(b->lchild>。 int r = Nodes(b->rchild>。 return l + r + 1。 } }
/** 求叶子节点个数 **/ int leafNodes(BTNode * b> {
if(b==NULL> return 0。
else if(b->lchild == NULL && b->rchild == NULL> return 1。 else {
int l = leafNodes(b->lchild>。 int r = leafNodes(b->rchild>。 return l + r。 }
}
void DestroyBTNode(BTNode *&b> {
if(b!=NULL>
DestroyBTNode(b->lchild>。 DestroyBTNode(b->rchild>。 free(b>。 } }
3.4解题思路：
1 树的先序遍历：递归算法，先输出根节点，再以左子树进行递归最后以右子树进行递归。非递归算法，用栈模拟整个递归过程。RTCrpUDGiT
2 树的中序遍历：递归算法，先以左子树进行递归，再输出根节点，最后以右子树进行递归。非递归算法，同上。5PCzVD7HxA
3 树的后序遍历：递归算法，先以左子树进行递归，再后以右子树进行递归，最后输出根节点。非递归算法，同上。jLBHrnAILg
3.5解题过程： 实验源代码如下：
3.5.1实现二叉树的各种基本运算 #include #include #include #include
#define maxx 100 using namespace std。 typedef struct node {
char data。
struct node *lchild。
struct node *rchild。 }BTNode。
void Insertnode(BTNode *&p,int &i,char * str> {
int judge = 0。
if(str[i]>='A'&&str[i]<='Z'> {
judge++。
p = (BTNode *>malloc(sizeof(BTNode>>。 p->lchild=NULL。 p->rchild=NULL。 p->data = str[i]。 i++。 }
if(str[i]=='\\0'> { return 。 } { i++。 if(!judge> {
p = (BTNode *>malloc(sizeof(BTNode>>。 p->lchild=NULL。 p->rchild=NULL。 }
Insertnode(p->lchild,i,str>。 Insertnode(p->rchild,i,str>。 }
if(str[i]==','||str[i]=='>'>
{ i++。 return 。 } }
/** 由STR创建二叉链 **/
void CreateBTNode(BTNode *&b,char * str> {
int i = 0。
Insertnode(b,i,str>。 ///以递归形式插入数据，i 会跟着变化} /** 查找e的节点指针 **/
BTNode * FindNode(BTNode * p, char e> {
if(p==NULL> return NULL。 if(p->data==e> return p。 else {
BTNode *b = FindNode(p->lchild,e>。 if(b!=NULL> return b。 else
return FindNode(p->rchild,e>。 } }
/** 输出二叉树 **/
void DispBTNode(BTNode * b> {
if(b!=NULL>
printf(\"%c\。
if(b->lchild!=NULL || b->rchild!=NULL> { printf(\"<\">。
DispBTNode(b->lchild>。
if(b->rchild != NULL>printf(\"，\">。 DispBTNode(b->rchild>。 printf(\"）\">。 } } }
/** 深度 **/
int BTNodeDepth(BTNode *b> {
if(b==NULL> return 0。 else {
int l = BTNodeDepth(b->lchild>。 int r = BTNodeDepth(b->rchild>。 return l>r?l+1:r+1。 } }
void search(BTNode *p,int *a,int k> {
if(p!=NULL> { a[k]++。
search(p->lchild,a,k+1>。 search(p->rchild,a,k+1>。 } }
/** 求二叉树的宽度 **/ int BTWidth(BTNode * b> {
int a[maxx], i, kmax = 0。 for(i = 0。i < maxx。 ++i> a[i] = 0。 int k = 0。 search(b,a,k>。
for(i = 0。i < maxx。 ++i> if(a[i]>kmax> kmax = a[i]。 return kmax。
/** 求二叉树的节点个数 **/ int Nodes(BTNode *b> {
if(b==NULL> return 0。
else if(b->lchild == NULL && b->rchild == NULL> return 1。 else {
int l = Nodes(b->lchild>。 int r = Nodes(b->rchild>。 return l + r + 1。 } }
/** 求叶子节点个数 **/ int leafNodes(BTNode * b> {
if(b==NULL> return 0。
else if(b->lchild == NULL && b->rchild == NULL> return 1。 else {
int l = leafNodes(b->lchild>。 int r = leafNodes(b->rchild>。 return l + r。 } }
void DestroyBTNode(BTNode *&b> {
if(b!=NULL> {
DestroyBTNode(b->lchild>。 DestroyBTNode(b->rchild>。 free(b>。 } }
int main( > {
BTNode *root, *p, *lp, *rp。
CreateBTNode(root,\"A(B(D,E(H(J,K(L,M(,N>>>>>,C(F,G(,I>>>\">。xHAQX74J0X
printf(\"二叉树：\\n\">。 DispBTNode(root>。 puts(\"\">。
printf(\"<2）H节点：\">。 p = FindNode(root,'H'>。 if(p!=NULL> {
lp = p->lchild。 if(lp != NULL> {
printf(\"左孩子为 %c \。 } else {
printf(\"无左孩子\">。 }
rp = p->rchild。 if(rp != NULL> {
printf(\"右孩子为 %c \。 } else {
printf(\"无右孩子\">。 } }
puts(\"\">。
printf(\"<3）二叉树的深度： %d\\n\。 printf(\"<4）二叉树的宽带： %d\\n\。 printf(\"<5）二叉树的节点数:%d\\n\。
printf(\"<6）二叉树的叶子节点个数：%d\\n\。 printf(\"<7）释放二叉树\\n\">。
DestroyBTNode(root>。 return 0。 }
3.5.2二叉树的三序遍历 #include
#include
#define maxsize 100 typedef char Elemtype。 typedef struct node {
Elemtype data。 struct node *lchild。 }BTnode。
void CreateBTnode(BTnode *&b,char *str> {
BTnode *st[maxsize], *p = NULL。 int top = - 1, k, j = 0。 char ch。 b = NULL。 ch = str[j]。 while(ch!='\\0'> {
if(ch == '('> { top++。 st[top] = p。 k = 1。 }
else if(ch == '>'> { top--。 }
else if(ch == ','> { k = 2。
} else {
p=(BTnode *>malloc(sizeof(BTnode>>。 p->data = ch。p->lchild = p->rchild = NULL。 if(b == NULL> b = p。 else {
if(k == 1>
st[top]->lchild = p。 else if(k == 2> st[top]->rchild = p。 } } j++。 ch = str[j]。 } }
void PreOrder(BTnode *p> if(p!=NULL> {
printf(\" %c\。 PreOrder(p->lchild>。 PreOrder(p->rchild>。 } }
void InOrder(BTnode *p> {
if(p!=NULL>
{
InOrder(p->lchild>。 printf(\" %c\。 InOrder(p->rchild>。 } }
void PostOrder(BTnode *p> {
if(p!=NULL> {
PostOrder(p->lchild>。 PostOrder(p->rchild>。 printf(\" %c\。 } }
void PreOrder1(BTnode *p> {
BTnode *st[maxsize], *b。 int top = -1。 if(p != NULL> {
因篇幅问题不能全部显示，请点此查看更多更全内容