数据结构---二叉树基础和遍历

简介: 数据结构---二叉树基础和遍历

写在前面

二叉树的几乎所有实现都是依靠递归实现,递归的核心思路是把任何一个二叉树看成根和左右子树,而二叉树递归的核心玩法就是把二叉树的左右子树再看成根,再找左右子树,再看成根...

因此,解决二叉树问题实际上要把二叉树转换成一个一个子树的过程,找到一个一个的子树再组装起来就形成了二叉树

二叉树的创建

二叉树建立的正统方法是利用递归,这里展示递归的一种写法

BTNode* BuyNode(BTDataType a)
{
   
   
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    newnode->data = a;
    newnode->left = NULL;
    newnode->left = NULL;
    return newnode;
}

BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
   
   
    if (a[*pi] == '#')
    {
   
   
        (*pi)++;
        return NULL;
    }

    BTNode* root = BuyNode(a[*pi]);
    (*pi)++;

    root->left = BinaryTreeCreate(a, pi);
    root->right = BinaryTreeCreate(a, pi);

    return root;
}
AI 代码解读

如果你对递归的认识并不熟悉,下面我画了一幅递归展开图,更好解释这其中的原理

在这里插入图片描述
(右子树的部分过程由于空间原因不够完全展开,但如果看懂左子树的构建过程,右子树不难自己画出)

这里注意的是,函数栈帧的创建并不是每一个都不一样的位置,当一个栈帧被销毁后,另外一个栈帧创建就会在原来的位置,因此在计算空间复杂度的时候需要考虑这个问题:
==空间是可以重复利用的,时间是一去不复返的==

从这幅图中,相信可以理解这段代码的含义了

首先创建一个根节点,根节点去寻找左子树进入递归,而进入递归后继续寻找左子树...直到遇到NULL截止,而遇到空后就寻找右子树,右子树也找到空后返回,这样就构建出了二叉树中最小的一棵树,而这棵树会返回,作为根的左子树,然后继续进入递归寻找根的右子树...

由于是借助链表进行实现的,因此我们可以理解为首先创建好根,而根的左右子树用函数创建好后再连接起来...当遇到#就返回,形成了一个一个的小树,小树最后组成大树,就形成了二叉树

二叉树的遍历

二叉树的遍历主要有前序遍历,中序遍历,后序遍历,层序遍历

前序遍历

前序遍历是指遍历时先访问根,再访问左子树,再访问右子树

代码实现如下

void BinaryTreePrevOrder(BTNode* root)
{
   
   
    if (root == NULL)
    {
   
   
        printf("N ");
        return;
    }

    printf("%c ", root->data);
    BinaryTreePrevOrder(root->left);
    BinaryTreePrevOrder(root->right);
}
AI 代码解读

下面依旧画出它的递归展开图

在这里插入图片描述

中序遍历

中序遍历是先访问左子树,再访问根,最后访问右子树

void BinaryTreeInOrder(BTNode* root)
{
   
   
    if (root == NULL)
    {
   
   
        printf("N ");
        return;
    }

    BinaryTreeInOrder(root->left);
    printf("%c ", root->data);
    BinaryTreeInOrder(root->right);
}
AI 代码解读

递归图和上面基本类似,就不做画出了

后序遍历

后序遍历是先访问左子树,再访问右子树,最后访问根

void BinaryTreePostOrder(BTNode* root)
{
   
   
    if (root == NULL)
    {
   
   
        printf("N ");
        return;
    }

    BinaryTreePostOrder(root->left);
    BinaryTreePostOrder(root->right);
    printf("%c ", root->data);
}
AI 代码解读

递归图和上面基本类似,就不做画出了

相关文章
|
18天前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
39 12
|
18天前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
39 10
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
40 2
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
【C++数据结构——图】图的遍历(头歌教学实验平台习题) 【合集】
本文介绍了图的遍历算法,包括深度优先遍历(DFS)和广度优先遍历(BFS)。深度优先遍历通过递归方式从起始节点深入探索图,适用于寻找路径、拓扑排序等场景;广度优先遍历则按层次逐层访问节点,适合无权图最短路径和网络爬虫等应用。文中提供了C++代码示例,演示了如何实现这两种遍历方法,并附有测试用例及结果,帮助读者理解和实践图的遍历算法。
30 0
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法,包括先序、中序、后序的递归与非递归遍历方法。通过编程实践,加深对二叉树结构的理解,学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
118 4
|
2月前
|
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
182 8
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
40 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
53 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
3月前
|
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
38 1

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等