当前位置: article > 正文

头歌（C语言）-数据结构与算法-二叉树-先序遍历/中序遍历_头哥实践教学平台数据结构二叉树

作者：爱喝兽奶帝天荒 | 2024-06-19 20:45:50

踩

头哥实践教学平台数据结构二叉树

先序遍历二叉树

任务描述

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

相关知识

实验目的

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

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

实验任务

说明：为使实验程序简洁直观，下面的部分实验程序中的一些功能实现仍以调用库函数程序"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 扩展二叉树

编程要求

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

测试说明

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

右侧数据框说明：
测试输入：
一个字符串表示扩展二叉树的先序遍历字符串
结构体说明：
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 Inorder(bitre &t){
    if(t==NULL)return;
    Inorder(t->lchild);
    putchar(t->data);
    Inorder(t->rchild);
}
void Preorder(bitre &t){
    if(t==NULL)return;
    putchar(t->data);
    Preorder(t->lchild);
    Preorder(t->rchild);
}
void create(bitre &t){
    char c;
    c=getchar();
    if(c=='.')return;
    t=new bnode;
    t->data= c;
    create(t->lchild);
    create(t->rchild);
}
void display(bitre t){
    printf("PreOrder: ");
    Preorder(t);
    printf("\nInOrder: ");
    Inorder(t);
    printf("\n");
}
void solve()
{
    bitre t;
    create(t);
    display(t);
    bitrepreorder(t);
    puts("");
}
 
}

中序遍历二叉树