二叉树的构建及遍历

这篇具有很好参考价值的文章主要介绍了二叉树的构建及遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

二叉树的构建及遍历

题目要求

二叉树的构建及遍历,刷题,笔记,c语言
题目链接

示例

解答

方法一、

先构建二叉树,再中序遍历。

实现思路

按照给出的字符串创建二叉树,先依次访问字符串中的字符,如果遇到不为’#'的字符,就将该结点的值赋值为该字符,然后再创建两个新结点,分别为该结点的左孩子和右孩子,然后递归调用方法,使左孩子和右孩子进行同样操作。如果遇到#字符,就将该结点堆顶值赋值为#,然后直接退出函数,即不再创建该结点的左右孩子结点。

时间复杂度和空间复杂度

代码

#include <stdio.h>
#include <stdlib.h>
typedef char BTDataType;
//定义二叉树的结点
typedef struct BinaryTreeNode
{
    BTDataType data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTNode;

void CreateBinaryTree(BTNode* root, char** arr)
{
    //如果**arr为'\0',则说明字符串已经结束
    if (*(*arr) == '\0')
    {
        return;
    }
    //如果**arr不为#,就将该结点的值为**arr,同时让(*arr)++
    //此时arr里面存的还是*arr的地址,但是(*arr)++后,*arr中存的地址已经为字符串中下一个字符的地址。
    if (*(*arr) != '#')
    {
        root->data = *(*arr);
        (*arr)++;
    }
    //如果**arr为#,就将该结点的值为#,然后同样将*arr中存的地址向后移一位。
    else
    {
        root->data=*(*arr);
        (*arr)++;
        return;
    }
    //如果该结点不为空结点,就创建两个结点,来当作该结点的左右孩子。
    BTNode* left = (BTNode*)malloc(sizeof(BTNode));
    BTNode* right = (BTNode*)malloc(sizeof(BTNode));
    root->left = left;
    root->right = right;
    //然后递归使该结点的左右孩子完成上述同样操作。
    CreateBinaryTree(root->left, arr);
    CreateBinaryTree(root->right, arr);
}
void InOrder(BTNode* root)
{
    //如果root结点的值为#,就说明该结点为空结点,不需要打印,直接退出函数
    if (root->data=='#')
    {
        return;
    }
    //先遍历该结点的左子树
    InOrder(root->left);
    //然后再打印该节点的值
    printf("%c ", root->data);
    //然后再遍历该结点的右子树
    InOrder(root->right);
}
int main() {
    char arr[100] = { 0 };
    scanf("%s", arr);
    //创建二叉树的根节点
    BTNode* bt = (BTNode*)malloc(sizeof(BTNode));
    //将字符串中第一个字符的地址赋值给pa
    char* pa = &arr[0];
    //将指针pa的地址赋给ppa,即ppa为二级指针,通过*ppa就可以得到pa,即得到字符串中第一个字符的地址。
    //当*ppa+1时,即*ppa+1指向字符串的第二个字符的地址,所以可以通过*ppa++来访问字符串的每个字符
    char** ppa = &pa;
    //将二叉树根节点和ppa当作实参
    CreateBinaryTree(bt, ppa);
    InOrder(bt);
    return 0;
}

方法二、

比第一种方法更简洁易懂

实现思路

和第一种方法相似,都是先按照给出的先序遍历的顺序创建二叉树,然后进行中序遍历。文章来源地址https://www.toymoban.com/news/detail-683890.html

时间复杂度和空间复杂度

代码

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef char BTDataType;
//定义二叉树的结点
typedef struct BinaryTreeNode
{
    BTDataType data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTNode;

//创建一个二叉树结点并返回
BTNode* BuyBTNode(BTDataType x)
{
    BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
    newNode->data=x;
    newNode->left=NULL;
    newNode->right=NULL;
    return newNode;
}

BTNode* CreateBinaryTree(char* arr,int* count)
{
    //如果现在访问的字符为#,则说明该结点为NULL,让(*count)++,即访问下一个字符,然后返回NULL
    if(arr[*count]=='#')
    {
        (*count)++;
        return NULL;
    }
    //如果现在访问的字符不为#,将该字符存入到新创建的结点中,
    BTNode* root = BuyBTNode(arr[(*count)++]);
    //然后再将该结点的左孩子和右孩子递归调用该函数
    //如果该结点有左孩子,则会返回创建的新结点
    //如果该结点没有左孩子,则会返回NULL
    root->left = CreateBinaryTree(arr, count);
    root->right = CreateBinaryTree(arr, count);
    //然后将根结点返回
    return root;
}
void InOrder(BTNode* root)
{
    if(root==NULL)
    {
        return ;
    }
    InOrder(root->left);
    printf("%c ",root->data);
    InOrder(root->right);
}
int main()
{
    char arr[100]={0};
    scanf("%s",arr);
    int count = 0;
    //CreateBinaryTree函数会返回创建的二叉树的根节点
    BTNode* bt = CreateBinaryTree(arr, &count);
    InOrder(bt);
}

到了这里,关于二叉树的构建及遍历的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 二叉树OJ题进阶(二叉树层序遍历、根据二叉树创建字符串、判断完全二叉树、二叉树的构建及遍历、二叉树的最近公共祖先(2种))

    1.思路 用队列写: 1.从上到下,从左到右的顺序 2.非递归的方法:使用队列来完成 3.cur充当根结点,当cur不为空的时候,cur进入队列,队列不为空,cur弹出队列打印 4.如果cur的左边不为空,左边进队,右边不为空,右边进队 5.此时队列不为空,弹出队头(也就是cur的左边)打

    2024年02月05日
    浏览(37)
  • 根据二叉树的先序、中序、后序遍历构建二叉树-图文详解

    引言:根据一颗二叉树,可以得出他的先序、中序、后序三种遍历方式,那么如果我们知道了他的前序、中序、后序遍历,如何绘制出这颗二叉树呢? 特性A,对于前序遍历,第⼀个肯定是根节点; 特性B,对于后序遍历,最后⼀个肯定是根节点; 特性C,利⽤前序或后序遍历

    2024年02月06日
    浏览(42)
  • 【数据结构之二叉树的构建和遍历】

    前言: 前篇学习了 数据结构之树和二叉树的基本概念知识,那么这篇继续完善二叉树的相关知识并完成实现二叉树的构建和遍历的内容。 / 知识点汇总 / 因为前篇已经非常详细的单独学习了数和二叉树的基本知识概念,那么这里就简单回顾一下即可。 概念 : 二叉树(Bina

    2024年02月21日
    浏览(46)
  • 算法刷题Day14 二叉树的前序、中序、后序遍历(递归、迭代、统一迭代方法)

    二叉树的定义 递归 迭代 普通的遍历(包括前序,中序和后续)迭代方法都需要借助到栈 统一迭代 统一迭代使用标记法,在栈中要处理的结点压入空指针 递归 迭代 中序遍历的迭代方法稍微特殊一点 中序遍历是左中右,先访问的是二叉树顶部的节点,然后一层一层向下访问

    2024年02月15日
    浏览(46)
  • 二叉树的层次遍历(C语言)

    二叉树是n(n=0)个节点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树组。 先序遍历 中序遍历    后序遍历  层次遍历     一、头文件   二、二叉树的结构   三、队列的结构   四、队列的初始化

    2024年02月07日
    浏览(35)
  • 【C语言 数据结构】二叉树的遍历

    所谓先序遍历二叉树,指的是从根结点出发,按照以下步骤访问二叉树的每个结点: 访问当前结点; 进入当前结点的左子树,以同样的步骤遍历左子树中的结点; 遍历完当前结点的左子树后,再进入它的右子树,以同样的步骤遍历右子树中的结点; 先序遍历这棵二叉树的过

    2024年02月04日
    浏览(42)
  • C语言二叉树的创建与遍历

    二叉树(binary tree)是指树中节点的度不大于2的有序树,它是一种最简单且最重要的树。二叉树的递归定义为:二叉树是一棵空树,或者是一棵由一个根节点和两棵互不相交的,分别称作根的左子树和右子树组成的非空树;左子树和右子树又同样都是二叉树。以下是对链式存

    2024年02月05日
    浏览(38)
  • 二叉树的链式结构 - 遍历 - C语言递归实现

    前序、中序以及后序遍历         二叉树遍历 (Traversal) 是按照某种特定的规则,依次对二叉 树中的节点进行相应的操作,并且每个节点只操作一次 。 按照规则,二叉树的遍历有: 前序/中序/后序 的递归结构遍历 : 1. 前序遍历 (Preorder Traversal 亦称先序遍历 )—— 访问根结

    2024年02月15日
    浏览(32)
  • 【C语言题解】 | 144. 二叉树的前序遍历

    提示: 树中节点数目在范围 [0, 100] 内 函数原型: 首先先观察一下这个函数原型, TreeNode* root 为形参,传入根节点, int* returnSize 为形参,在函数调用时用于返回改题目所求数组的长度,因为由于C语言的局限,只能返回一个参数,所以采用这种通过传入指针的形参,来改变

    2024年01月18日
    浏览(43)
  • C语言完整代码实现:二叉树的先序遍历、中序遍历、后序遍历

    一、先序遍历原理        先序遍历就是: 根、左、右 ,也就是先遍历根结点再遍历左结点最后再遍历右结点,注意:如果遍历到的结点不是叶子结点的话需要对该结点进行拆分,比如这棵二叉树: 先遍历 A ,然后是 B ,然后再是 C ,但是由于B并不是叶子结点,他本身又是

    2024年02月07日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包