二叉树实验

数据结构C语言版

AIains

3312人浏览 · 2022-10-24 20:24:00

AIains · 2022-10-24 20:24:00 发布

第1关：头文件基本函数的实现

任务描述

本关任务：实现本实训所需头文件的基本函数。

相关知识

实验目的

掌握二叉树的动态链表存储结构及表示；
掌握二叉树的三种遍历算法（递归和非递归两类）；
运用二叉树三种遍历的方法求解有关问题。

二叉树是一种非常重要的结构。由于二叉树是树结构的基础，因此，掌握二叉树的性质、存储结构、运算及其实现显得尤为重要。由于二叉树的各子结构与整个结构具有相似的特性，因而其算法大多采用递归形式，这是一个难点，但也是非常重要的技术基础。因此，在理解和掌握二叉树的相关性质、存储结构和遍历算法的基础上，要求能熟练地运用于实际问题的求解。从实验的要求和特点出发，偏重于二叉树的存储结构和遍历运算及其应用，同时，借助于递归算法的运用熟练掌握递归技术。

实验任务

说明：为使实验程序简洁直观，下面的部分实验程序中的一些功能实现仍以调用库函数程序"btrechar.h"中的函数的形式给出，并假设该库函数中定义了二叉树指针和结点类型分别为bitre和bnode，以及部分常用运算，例如构建二叉树、以某种方式显示二叉树等。各运算的名称较为直观，因而易于理解。

实验说明

下面重点讨论实验所涉及到的一些基础部分的实现方法。

二叉树的存储结构

在上机实现程序时，存储结构及其构建是基础。如教科书中所述，存储结构可分为顺序存储和二叉链表存储两种形式，其中二叉链表存储形式的适用范围更大。因此，大多数情况下采用这种形式。本书所采用的结构形式与教科书类似，描述如下。

结点结构: 每个结点主要有三个字段：存放字符型数据的字段data，存放左右孩子指针的字段lchild和rchild。类型描述如下; 将二叉链表中的指针类型定为bitre，结点类型定为bnode，类型描述如下：

typedef struct bnode
{
char data; // 数据字段
struct bnode *lchild,*rchild; // 左右孩子指针
};
typedef bnode *bitre;

扩展二叉树

将所要建的二叉树中每个结点的空指针处再引出一个“孩子”结点，其值为一特定的值以标识其为空。例如，如果二叉树的结点值为字符型，则可以“.” 标识其为空，如图1和图2所示。称这样处理后的二叉树为原二叉树的扩展二叉树。扩展二叉树的先序或后序序列以及层次序列能唯一确定其原二叉树, 处理时只要将“.”作为空二叉树即可。下面讨论采用扩展二叉树的先序序列输入构建二叉树的方法。例如，为构造图1所示二叉树，则输入序列为ABD..E..CF..G..。

图1 原二叉树

图2 扩展二叉树

编程要求

在本关卡中，需要实现头文件"btrechar.h"的一些基本函数，各个函数的功能与参数说明如下：

函数: void load_bitre(bitre & t); 功能: 在函数内读取拓展二叉树的先序遍历序列构建原二叉树；返回值: 通过引用返回。
函数: void display_bitre(bitre & root)；功能: 输出二叉树的先序遍历序列和中序遍历序列；格式: PreOrder: xxxxxxx InOrder: xxxxxxx

测试说明

平台会对你编写的代码进行测试：

输入数据: 一行字符串表示拓展二叉树的先序遍历序列。

输出数据: 调用你编写的display_bitre函数的输出。

```

开始你的任务吧，祝你成功！

#pragma once
# include <bits/stdc++.h>
using namespace std;

namespace exa{

struct bnode {
    struct bnode * lchild, * rchild;
    char data;
};
typedef bnode * bitre;
static void pre(bitre);
static void mid(bitre);

//读取扩展二叉树的先序序列来构建原二叉树
static void load_bitre(bitre & t) {
    char ch;
    scanf("%c",&ch);
    if(ch=='.'){
        //叶子节点处
        t=NULL;
        return;
    }
    else{
        bitre temp=(bitre)malloc(sizeof(struct bnode));
        if(!temp)
            return;
        temp->data=ch;
        //分配空间后让t指向新节点
        t=temp;
        load_bitre(t->lchild);
        load_bitre(t->rchild);
    }
}

//输出二叉树的先序和后序遍历序列
//输出格式为:
//PreOrder: xxxxxxx
//InOrder: xxxxxxx
static void display_bitre(bitre & root) {
    printf("PreOrder: ");
    pre(root);
    printf("\n");
    printf("InOrder: ");
    mid(root);
    printf("\n");
}
static void pre(bitre t){
    printf("%c",t->data);
    if(t->lchild)
        pre(t->lchild);
    if(t->rchild)
        pre(t->rchild);
}
static void mid(bitre t){
    if(t->lchild)
        mid(t->lchild);
    printf("%c",t->data);
    if(t->rchild)
      mid(t->rchild);
}
}

第2关：访问二叉树的叶子节点

任务描述

本关任务：请在右侧编辑器的注释行填入适当内容来完成算法，以实现指定的功能，并通过运行来验证。

相关知识

实验目的

掌握二叉树的动态链表存储结构及表示；
掌握二叉树的三种遍历算法（递归和非递归两类）；
运用二叉树三种遍历的方法求解有关问题。

实验任务

实验说明

下面重点讨论实验所涉及到的一些基础部分的实现方法。

二叉树的存储结构

typedef struct bnode
{
char data; // 数据字段
struct bnode *lchild,*rchild; // 左右孩子指针
};
typedef bnode *bitre;

扩展二叉树

将所要建的二叉树中每个结点的空指针处再引出一个“孩子”结点，其值为一特定的值以标识其为空。例如，如果二叉树的结点值为字符型，则可以“.” 标识其为空，如图1和图2所示。称这样处理后的二叉树为原二叉树的扩展二叉树。扩展二叉树的先序或后序序列以及层次序列能唯一确定其原二叉树, 处理时只要将“.”作为空二叉树即可。下面讨论采用扩展二叉树的先须序列输入构建二叉树的方法。例如，为构造图1所示二叉树，则输入序列为ABD..E..CF..G..。

图1 原二叉树

图2 扩展二叉树

编程要求

请在右侧编辑器的注释行填入适当内容来完成算法，以使算法仅访问其中的叶子结点，并通过运行来验证。

测试说明

平台会对你编写的代码进行测试：

右侧数据框说明：
测试输入：
一行字符串表示扩展二叉树的先序遍历字符串
结构体说明：
struct bnode {
struct bnode * lchild, * rchild;
char data;
};
typedef bnode * bitre;
库函数详细可查看右侧头文件 "btrechar.h"

开始你的任务吧，祝你成功！

#include "test.h"
#include "../btrechar.h"  // 引用库函数文件
namespace exa {     //请在命名空间内编写代码，否则后果自负

void visite_leaf(bitre t)
{
    if(t!=NULL)//Blank 1
    {
        if (t->lchild==NULL&&t->rchild==NULL) {//Blank 2
            cout << t->data << endl;}
        visite_leaf(t->lchild);                 // 递归调用算法对左子树执行
        visite_leaf(t->rchild);                 // 递归调用算法对右子树执行
	}
}
void solve()
{
    bitre t;
    load_bitre(t);                              // 取出二叉树
    display_bitre(t);                   // 显示二叉树
    visite_leaf(t);                             // 调用算法运行以检验
}

}

第3关：先序遍历二叉树

任务描述

本关任务：试修改右侧算法的错误。

相关知识

实验目的

掌握二叉树的动态链表存储结构及表示；
掌握二叉树的三种遍历算法（递归和非递归两类）；
运用二叉树三种遍历的方法求解有关问题。

实验任务

实验说明

下面重点讨论实验所涉及到的一些基础部分的实现方法。

二叉树的存储结构

typedef struct bnode
{
char data; // 数据字段
struct bnode *lchild,*rchild; // 左右孩子指针
};
typedef bnode *bitre;

扩展二叉树

将所要建的二叉树中每个结点的空指针处再引出一个“孩子”结点，其值为一特定的值以标识其为空。例如，如果二叉树的结点值为字符型，则可以“.” 标识其为空，如图1和图2所示。称这样处理后的二叉树为原二叉树的扩展二叉树。扩展二叉树的先序或后序序列以及层次序列能唯一确定其原二叉树, 处理时只要将“.”作为空二叉树即可。下面讨论采用扩展二叉树的先须序列输入构建二叉树的方法。例如，为构造图1所示二叉树，则输入序列为ABD..E..CF..G..。

图1 原二叉树

图2 扩展二叉树

编程要求

右侧算法的原定功能是先序遍历二叉树，试修改其中的错误。

测试说明

平台会对你编写的代码进行测试：

右侧数据框说明：
测试输入：
一个字符串表示扩展二叉树的先序遍历字符串
结构体说明：
struct bnode {
struct bnode * lchild, * rchild;
char data;
};
typedef bnode * bitre;
库函数详细可查看右侧头文件 "btrechar.h"

开始你的任务吧，祝你成功！

#include "test.h"
#include "../btrechar.h"  // 引用库函数文件
namespace exa {     //请在命名空间内编写代码，否则后果自负

void bitrepreorder(bitre t)
{
    if(t != NULL){
        putchar(t->data);
        bitrepreorder(t->lchild);       // 递归调用算法对t的左子树执行算法
        bitrepreorder(t->rchild);       // 递归调用算法对t的右子树执行算法
    }
}
void solve()
{
    bitre t;
    load_bitre(t);
    display_bitre(t);
    bitrepreorder(t);
    puts("");
}

}

第4关：求二叉树的高度

任务描述

本关任务：求二叉树的高度。

相关知识

实验目的

掌握二叉树的动态链表存储结构及表示；
掌握二叉树的三种遍历算法（递归和非递归两类）；
运用二叉树三种遍历的方法求解有关问题。

实验任务

实验说明

下面重点讨论实验所涉及到的一些基础部分的实现方法。

二叉树的存储结构

typedef struct bnode
{
char data; // 数据字段
struct bnode *lchild,*rchild; // 左右孩子指针
};
typedef bnode *bitre;

扩展二叉树

将所要建的二叉树中每个结点的空指针处再引出一个“孩子”结点，其值为一特定的值以标识其为空。例如，如果二叉树的结点值为字符型，则可以“.” 标识其为空，如图1和图2所示。称这样处理后的二叉树为原二叉树的扩展二叉树。扩展二叉树的先序或后序序列以及层次序列能唯一确定其原二叉树, 处理时只要将“.”作为空二叉树即可。下面讨论采用扩展二叉树的先须序列输入构建二叉树的方法。例如，为构造图1所示二叉树，则输入序列为ABD..E..CF..G..。

图1 原二叉树

图2 扩展二叉树

编程要求

请在右侧编辑器的命名空间内填写相关代码，求出给定二叉树的高度。若题目有其它要求，应当将题目要求的结果在solve函数内通过返回或引用的形式传递参数。

测试说明

平台会对你编写的代码进行测试：

函数说明：
int solve(bitre & t)
参数 t 为给出的二叉树的根节点
返回一个值表示二叉树的高度
右侧数据框说明：
测试输入：
一个字符串表示扩展二叉树的先序遍历字符串
实际输出：
你返回的值
结构体说明：
struct bnode {
struct bnode * lchild, * rchild;
char data;
};
typedef bnode * bitre;
库函数详细可查看右侧头文件 "btrechar.h"

开始你的任务吧，祝你成功！

#include "test.h"
#include "../btrechar.h"  // 引用库函数文件
namespace exa {     //请在命名空间内编写代码，否则后果自负
#define MAX(a,b)((a)>(b)?(a):(b))
int solve(bitre & t) {
    //NULL
    if(!t)
       return 0;
    int high= 0;//对于一个结点来说，子树初始高度0
    if(t->lchild){
        int lh = solve(t->lchild);
        //递归返回的时候，当前层到叶子结点的高度为lh
        high=MAX(lh,high);//更新左子树高度
    }
    if(t->rchild){
        int rh=solve(t->rchild);
        high=MAX(rh,high);//右递归结束，返回到当前层，更新左右子树的最大值
    }
    //当前结点t是叶子结点的时候，该层函数结束，层数+1
    return high+1;

}

}

第5关：中序遍历二叉树

任务描述

本关任务：设计算法按中序次序输出二叉树中各结点的值及其所对应的层次数。

相关知识

实验目的

掌握二叉树的动态链表存储结构及表示；
掌握二叉树的三种遍历算法（递归和非递归两类）；
运用二叉树三种遍历的方法求解有关问题。

实验任务

实验说明

下面重点讨论实验所涉及到的一些基础部分的实现方法。

二叉树的存储结构

typedef struct bnode
{
char data; // 数据字段
struct bnode *lchild,*rchild; // 左右孩子指针
};
typedef bnode *bitre;

扩展二叉树

将所要建的二叉树中每个结点的空指针处再引出一个“孩子”结点，其值为一特定的值以标识其为空。例如，如果二叉树的结点值为字符型，则可以“.” 标识其为空，如图1和图2所示。称这样处理后的二叉树为原二叉树的扩展二叉树。扩展二叉树的先序或后序序列以及层次序列能唯一确定其原二叉树, 处理时只要将“.”作为空二叉树即可。下面讨论采用扩展二叉树的先须序列输入构建二叉树的方法。例如，为构造图1所示二叉树，则输入序列为ABD..E..CF..G..。

图1 原二叉树

图2 扩展二叉树

编程要求

请在右侧编辑器的命名空间内填写相关代码，按中序次序输出二叉树中各结点的值及其所对应的层次数。若题目有其它要求，应当将题目要求的结果在solve函数内通过返回或引用的形式传递参数。

测试说明

平台会对你编写的代码进行测试：

函数说明：
void solve(bitre & t)
参数 t 为给出的二叉树的根节点
对于一棵具有 n 个节点的二叉树，你需要在函数内输出 n 行，其中第 i 行为 Ci Li形式，其中Ci表示第i个节点的值，Li表示第i个节点对应的层次数
默认根节点为第 1 层。
右侧数据框说明：
测试输入：
一个字符串表示扩展二叉树的先序遍历字符串
实际输出：
你的输出
结构体说明：
struct bnode {
struct bnode * lchild, * rchild;
char data;
};
typedef bnode * bitre;
库函数详细可查看右侧头文件 "btrechar.h"

开始你的任务吧，祝你成功！

#include "test.h"
#include "../btrechar.h"  // 引用库函数文件
namespace exa {     //请在命名空间内编写代码，否则后果自负

int count=1;
void solve(bitre & t) { 
    if(!t)
        return ;
    count++;
    if(t->lchild)
    {   
        solve(t->lchild);
    } 
    printf("%c %d\n",t->data,count-1);
    if(t->rchild)
    {
        solve(t->rchild);
    }
    count--; 
}

}

第6关：顺序存储二叉树转二叉链表

任务描述

本关任务：设计算法将按顺序方式存储在数组中的二叉树转换为二叉链表形式。

相关知识

实验目的

掌握二叉树的动态链表存储结构及表示；
掌握二叉树的三种遍历算法（递归和非递归两类）；
运用二叉树三种遍历的方法求解有关问题。

实验任务

实验说明

下面重点讨论实验所涉及到的一些基础部分的实现方法。

二叉树的存储结构

typedef struct bnode
{
char data; // 数据字段
struct bnode *lchild,*rchild; // 左右孩子指针
};
typedef bnode *bitre;

扩展二叉树

将所要建的二叉树中每个结点的空指针处再引出一个“孩子”结点，其值为一特定的值以标识其为空。例如，如果二叉树的结点值为字符型，则可以“.” 标识其为空，如图1和图2所示。称这样处理后的二叉树为原二叉树的扩展二叉树。扩展二叉树的先序或后序序列以及层次序列能唯一确定其原二叉树, 处理时只要将“.”作为空二叉树即可。下面讨论采用扩展二叉树的先须序列输入构建二叉树的方法。例如，为构造图1所示二叉树，则输入序列为ABD..E..CF..G..。

图1 原二叉树

图2 扩展二叉树

编程要求

请在右侧编辑器的命名空间内填写相关代码，将按顺序方式存储在数组中的二叉树转换为二叉链表形式。若题目有其它要求，应当将题目要求的结果在solve函数内通过返回或引用的形式传递参数。

测试说明

平台会对你编写的代码进行测试：

函数说明：
bitre solve(char * c, int n)
参数 c 为题意中给出的字符串数组的首地址，参数 n 为数组的大小。
返回数组转换成的二叉树的根节点
右侧数据框说明：
测试输入：
一个字符串 s 表示顺序存储的二叉树，其中 s(i) 的左儿子为 s(2*i+1)，右儿子为 s(2*i+2)，当 s(i)='.'时表示此处没有节点。
实际输出：
第一行为你返回的二叉树的先序遍历
第二行为你返回的二叉树的中序遍历
结构体说明：
struct bnode {
struct bnode * lchild, * rchild;
char data;
};
typedef bnode * bitre;
库函数详细可查看右侧头文件 "btrechar.h"

开始你的任务吧，祝你成功！

#include "test.h"
#include "../btrechar.h"  // 引用库函数文件
namespace exa {     //请在命名空间内编写代码，否则后果自负

bitre f(char*,int,int);

bitre solve(char * c, int n) {
    return f(c,0,n);
}
bitre f(char *c,int i,int n){
    bitre temp=NULL;
    if(i<n&&c[i]!='.'){
        temp=(bitre)malloc(sizeof(struct bnode));
        temp->data=c[i];
        temp->lchild=f(c,2*i+1,n);
        temp->rchild=f(c,2*i+2,n);
    }
    return temp;
}
}

第7关：复制二叉树

任务描述

本关任务：复制一棵二叉树T到T1。

相关知识

实验目的

掌握二叉树的动态链表存储结构及表示；
掌握二叉树的三种遍历算法（递归和非递归两类）；
运用二叉树三种遍历的方法求解有关问题。

实验任务

实验说明

下面重点讨论实验所涉及到的一些基础部分的实现方法。

二叉树的存储结构

typedef struct bnode
{
char data; // 数据字段
struct bnode *lchild,*rchild; // 左右孩子指针
};
typedef bnode *bitre;

扩展二叉树

将所要建的二叉树中每个结点的空指针处再引出一个“孩子”结点，其值为一特定的值以标识其为空。例如，如果二叉树的结点值为字符型，则可以“.” 标识其为空，如图1和图2所示。称这样处理后的二叉树为原二叉树的扩展二叉树。扩展二叉树的先序或后序序列以及层次序列能唯一确定其原二叉树, 处理时只要将“.”作为空二叉树即可。下面讨论采用扩展二叉树的先须序列输入构建二叉树的方法。例如，为构造图1所示二叉树，则输入序列为ABD..E..CF..G..。

图1 原二叉树

图2 扩展二叉树

编程要求

请在右侧编辑器的命名空间内里填写相关代码，复制一棵二叉树T到T1。若题目有其它要求，应当将题目要求的结果在solve函数内通过返回或引用的形式传递参数。

测试说明

平台会对你编写的代码进行测试：

函数说明：
bitre solve(bitre & t)
参数 t 为题意中给出的二叉树 t 。
返回数组复制后的二叉树的根节点
右侧数据框说明：
测试输入：
一个字符串表示扩展二叉树的先序遍历字符串
实际输出：
第一行为你返回的二叉树的先序遍历
第二行为你返回的二叉树的中序遍历
结构体说明：
struct bnode {
struct bnode * lchild, * rchild;
char data;
};
typedef bnode * bitre;
库函数详细可查看右侧头文件 "btrechar.h"

开始你的任务吧，祝你成功！

#include "test.h"
#include "../btrechar.h"  // 引用库函数文件
namespace exa {     //请在命名空间内编写代码，否则后果自负

bitre solve(bitre & t) {
    return t;
}

}

第8关：交换二叉树的左右孩子指针

任务描述

本关任务：交换二叉树中每个结点的左右孩子指针的值。

相关知识

实验目的

掌握二叉树的动态链表存储结构及表示；
掌握二叉树的三种遍历算法（递归和非递归两类）；
运用二叉树三种遍历的方法求解有关问题。

实验任务

实验说明

下面重点讨论实验所涉及到的一些基础部分的实现方法。

二叉树的存储结构

typedef struct bnode
{
char data; // 数据字段
struct bnode *lchild,*rchild; // 左右孩子指针
};
typedef bnode *bitre;

扩展二叉树

将所要建的二叉树中每个结点的空指针处再引出一个“孩子”结点，其值为一特定的值以标识其为空。例如，如果二叉树的结点值为字符型，则可以“.” 标识其为空，如图1和图2所示。称这样处理后的二叉树为原二叉树的扩展二叉树。扩展二叉树的先序或后序序列以及层次序列能唯一确定其原二叉树, 处理时只要将“.”作为空二叉树即可。下面讨论采用扩展二叉树的先须序列输入构建二叉树的方法。例如，为构造图1所示二叉树，则输入序列为ABD..E..CF..G..。

图1 原二叉树

图2 扩展二叉树

编程要求

请在右侧编辑器的命名空间内填写相关代码，交换二叉树中每个结点的左右孩子指针的值。若题目有其它要求，应当将题目要求的结果在solve函数内通过返回或引用的形式传递参数。

测试说明

平台会对你编写的代码进行测试：

函数说明：
void solve(bitre & t)
参数 t 为题意中给出的二叉树 t 。
在函数内对 t 进行操作
右侧数据框说明：
测试输入：
一个字符串表示扩展二叉树的先序遍历字符串
实际输出：
第一行为你返回的二叉树的先序遍历
第二行为你返回的二叉树的中序遍历
结构体说明：
struct bnode {
struct bnode * lchild, * rchild;
char data;
};
typedef bnode * bitre;
库函数详细可查看右侧头文件 "btrechar.h"

开始你的任务吧，祝你成功！

#include "test.h"
#include "../btrechar.h"  // 引用库函数文件
namespace exa {     //请在命名空间内编写代码，否则后果自负


void solve(bitre & t) {
    if(!t)
        return ;
    if(t->lchild)
        solve(t->lchild);
    if(t->rchild)
        solve(t->rchild);

        bitre temp=t->lchild;
        t->lchild=t->rchild;
        t->rchild=temp;
    
}

}