• 数据结构先序序列创建二叉树


    2022.11.19连发两回。


    任务描述

    本关任务:利用先序遍历创建二叉树,并给出相应二叉树的中序遍历结果。

    相关知识

    为了完成本关任务,你需要掌握:1.二叉树的前序遍历,2.如何创建一颗二叉树,3.二叉树的中序遍历

    二叉树的前序遍历
    前序遍历preorder traversal是指按照先根节点,再左节点,最后右节点的次序访问二叉树中所有的节点,使得每个节点被访问且仅被访问一次。
    例:图1表示一个二叉树,前序遍历的顺序如节点上面数字所示,结果为ABCDEF。
    在这里插入图片描述
    利用先序遍历创建二叉树,我们需要知道先序遍历的叶子节点,通过增加符合#表示叶子节点的子节点,则图1的先序遍历为:ABC##D##EF###。

    根据先序遍历的过程,首先创建根节点,然后使用递归的方法创建左子树节点,直到遇到符号#,表示到了叶子节点,回溯父节点并创建右子树节点。
    伪代码如下:
    在这里插入图片描述
    二叉树的中序遍历
    中序遍历inorder traversal是指按照先左节点,再根节点,最后右节点的次序访问二叉树中所有的节点,使得每个节点被访问且仅被访问一次。
    例:图2表示一个二叉树,中序遍历的顺序如节点上面数字所示,结果为CBDAFE。
    在这里插入图片描述

    编程要求

    本关的编程任务是补全右侧代码片段CreatBiTree和InOrder中Begin至End中间的代码,具体要求如下:

    在CreatBiTree中,利用先序遍历创建二叉树,并返回二叉树根节点指针。
    在InOrder中,完成二叉树的中序遍历,并输出遍历结果,中间没有空格,末尾不换行。

    测试说明

    平台将自动编译补全后的代码,并生成若干组测试数据,接着根据程序的输出判断程序是否正确。

    以下是平台的测试样例:

    测试输入:ABC##D##EF###
    预期输出:CBDAFE

    测试输入:ABCD###E#F##G##
    预期输出:DCBEFAG

    开始你的任务吧,祝你成功!

    C/C++代码

    //
    //  binary_tree.cpp
    
    #include "binary_tree.h"
    
    //创建新结点的工具函数
    BTNode* getNewNode(char e)
    {
        BTNode* p = (BTNode*)malloc(sizeof(BTNode));
        p->data = e;
        p->lchild = p->rchild = NULL;
        return p;
    }
    
    
    BTNode* CreateTree(char* s, int &i, int len)
    // 利用先序遍历创建二叉树
    // 参数:先序遍历字符串s,字符串初始下标i=0,字符串长度len。
    // 返回:二叉树
    {
        // 请在这里补充代码,完成本关任务
        /********** Begin *********/
        if(s[i]=='#' || i>len){i++;return NULL;}
        BTNode* BTP = getNewNode(s[i++]);
        BTP->lchild = CreateTree(s,i,len);
        BTP->rchild = CreateTree(s,i,len);
        return BTP;
        /********** End **********/
    }
    
    // 二叉树的中序遍历
    // 参数:二叉树根节点root
    // 输出:中间没有空格,末尾不换行。
    void InOrder(BTNode* root)
    {
        // 请在这里补充代码,完成本关任务
        /********** Begin *********/
        if(root==NULL){
            return;
        }
        InOrder(root->lchild);
        printf("%c",root->data);
        InOrder(root->rchild);
        /********** End **********/
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
  • 相关阅读:
    高级架构师_Elasticsearch_第一章_Elasticsearch安装
    计算机毕设(附源码)JAVA-SSM基于驾校管理系统
    修改Docker镜像默认下载地址
    PCV0.S10.0N.000,VIS插装式压力补偿器
    golang pprof监控系列(2) —— memory,block,mutex 使用
    C语言--输入三角形的三边,输出三角形的面积
    四、Web开发
    空洞卷积学习笔记
    flutter升级+生成drift文件
    算法day 14 第六章二叉树
  • 原文地址:https://blog.csdn.net/m0_63142359/article/details/127931018