二叉树的建立与遍历【数据结构实验报告】

我就是我 2022-06-06 10:35 192阅读 0赞

**数据结构实验报告**

**实验名称**：实验四 二叉树的建立和遍历

学号：\*\*\*

姓名：gnosed

实验日期：2017.11.5

**一、实验目的**

1、掌握树的先根构造

2、了解树的遍历

**二、实验具体内容**

**1、实验题目1：**

**（1）题目**

构造一棵二叉树，并进行遍历

要求：

1、二叉树的构造，可以输入树的先根序遍历序列，然后进行构造

2、先使用递归的中根，先根，后根序对二叉树做遍历，然后对二叉树进行中根序非递归遍历

提示：

1、 在构造二叉树的时候，输入树的先根序的时候，树的先根序必须是完整的

2、 在进行二叉树的中根序非递归遍历代码书写时，使用的栈，可以使用STL的栈。

**（2）分析**

二叉树是递归定义的，其建立和遍历都可以通过递归来实现。

对于给定一种遍历序列，不能唯一确定一颗二叉树，而需要给定中序序列和另外一种遍历序列。而对于一般二叉树，如果对于所有缺少左孩子或者右孩子的结点，将其扩充完整，使得所有叶子结点都是外来的，那么其遍历序列是唯一的。所以，如果给定上述一种完整的遍历序列（外来节点用\#代替），就能确定唯一的一颗二叉树。

现如给定先序序列: ABD\#\#\#CE\#G\#\#FH\#I\#\#J（最右结点J可不用添加\#）

其对应的二叉树：

/ \\

B C

/ \\ / \\

D \# E F

/ \\ / \\ / \\

\# \# \# G H J

/ \\ / \\

\# \#\# I

/ \\

\# \#

利用给定序列创建一颗二叉树，然后对其进行前序、中序和后序遍历，输出遍历序列，根据上图验证二叉树。

**（3）实验代码**

源代码：

**头文件 Bintree.h**

#ifndef BINTREE_H_INCLUDED
    #define BINTREE_H_INCLUDED
    
    
    #define ELEMENTTYPE char
    typedef struct node* pnode;
    typedef struct node* PBintree;
    
    
    struct node{
        ELEMENTTYPE n;
        pnode lchild;
        pnode rchild;
    };
    
    
    PBintree create(char seq[],int &i,int k);
    void pre_order(PBintree t);
    void in_order(PBintree t);
    void aft_order(PBintree t);
    void destroy(PBintree t);
    
    
    #endif // BINTREE_H_INCLUDED

**方法文件 Bintree.cpp**

#include "Bintree.h"
    #include <iostream>
    #include <cstdlib>
    #include <stack>
    
    
    PBintree create(char seq[],int &i,int k){//整型指针i代表当前搜索序列的位置
       if(i>k||seq[i]=='#')                 //搜索全部序列或搜索到树叶
           return NULL;
       pnode p=new struct node;             //构造新的结点
       if(p!=NULL){
           p->n=seq[i];                     //赋值
           i++;                             //考虑序列的下一个字符
           
                                            //递归地构造二叉树
           p->lchild=create(seq,i,k);       //构造左子树
           i++;                             //构造左子树结束，接着考虑序列下一个字符
           
           p->rchild=create(seq,i,k);       //构造右子树
           return p;                        //返回已成功构造的二叉树
        }
        return NULL;
    }
    void pre_order(PBintree t){             //递归前序遍历
       if(t==NULL) return;
       std::cout<<t->n;
       pre_order(t->lchild);
       pre_order(t->rchild);
    }
    void in_order(PBintree t){              //非递归中序遍历
       if(t==NULL) return;
       std::stack<pnode> s;
       pnode p=t;
       while(!s.empty()||p){
           while(p){
               s.push(p);
               p=p->lchild;
            }
           p=s.top();s.pop();
           std::cout<<p->n;
           p=p->rchild;
        }
    
    
    }
    void aft_order(PBintree t){              //递归后序遍历
       if(t==NULL) return;
       aft_order(t->lchild);
       aft_order(t->rchild);
       std::cout<<t->n;
    }
    void destroy(PBintree t){                 //递归摧毁二叉树
        if(t){
           destroy(t->lchild);
           destroy(t->rchild);
           free(t);
        }
    }

**main函数**

#include "Bintree.h"
    #include <iostream>
    #include <cstdio>
    #include <string.h>
    #define maxn 100
    using namespace std;
    
    int main()
    {
       int k=0;
       char seq[maxn];
       printf("Pre_order of tree:\n");
       scanf("%s",seq);
       PBintree tree=create(seq,k,strlen(seq)-1);
       cout<<endl<<"Pre_order:";
       pre_order(tree);
       cout<<endl<<endl<<"In_order:";
       in_order(tree);
       cout<<endl<<endl<<"Aft_order:";
       aft_order(tree);
       destroy(tree);
       return 0;
    }

测试结果：

Pre_order of tree:
    ABD###CE#G##FH#I##J
     
    Pre_order:ABDCEGFHIJ
     
    In_order:DBAEGCHIFJ
     
    Aft_order:DBGEIHJFCA

通过分析验证，正确。

**三、实验小结**

1. 在递归创建二叉树时，一直不知为何用seq\[i\]==’\\0’ 结束不了创建过程，导致创建了乱码结点，于是干脆改变判断方式，添加序列的一个长度形参，用其结束创建。可是为什么？主函数里的scanf输入序列，末尾已经带有 \\0了，为何作为实参传入到方法文件里创建二叉树就识别不出来？thinking……

2. 分析方案时，未明确要求，即每个叶子结点和孩子空缺处都要添加\#，导致一度创建偏差。

3. 关于二叉树的递归遍历、非递归遍历，笔者另有总结 http://blog.csdn.net/gnosed/article/details/78164272 。