二叉树的四种遍历方式以及必备的面试题（附图解）

二叉树的四种遍历方式以及必备的面试题

文章目录

  • 二叉树的四种遍历方式以及必备的面试题
  • 前言
  • 一、构建一个二叉树
  • 二、四种遍历方式
    • 1.前序遍历
    • 2.中序遍历
    • 3.后序遍历
    • 附加: 前三种遍历对比图
    • 4.层序遍历
  • 三、四种遍历相关的面试题
  • 1.第一题：144. 二叉树的前序遍历
    • (1)题目
    • （2）思路
    • （3）源码
  • 2.第二题：94. 二叉树的中序遍历
  • 3.第三题：145. 二叉树的后序遍历
  • 4.第四题：判断二叉树是否是完全二叉树
    • （1）思路
    • （2）源码
  • 5.第五题：KY11 二叉树遍历
    • （1）题目
    • （2）思路
    • （3）源码
  • 最后：销毁二叉树
    • （1）源码
    • （2）递归图解
  • 总结

前言

本文介绍二叉树前序遍历、中序遍历、后序遍历、层序遍历以及各自相关的面试OJ题的讲解！

一、构建一个二叉树

构建如图所示的二叉树，在这里不做过多介绍，想了解怎么构建的可以参考之前的博客！

在这里插入图片描述

代码如下（示例）：

typedef char BTDataType;
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	node->data = x;
	node->left = node->right = NULL;
	return node;
}
BTNode* CreatBinaryTree()
{
	BTNode* nodeA = BuyNode('A');
	BTNode* nodeB = BuyNode('B');
	BTNode* nodeC = BuyNode('C');
	BTNode* nodeD = BuyNode('D');
	BTNode* nodeE = BuyNode('E');
	BTNode* nodeF = BuyNode('F');
	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeC->left = nodeE;
	nodeC->right = nodeF;
	return nodeA;
}

二、四种遍历方式

1.前序遍历

前序遍历的顺序为 根 —> 左子树 —> 右子树，下面给大家介绍一种简便方法

在这里插入图片描述

代码如下（示例）：

// 二叉树前序遍历 
void PreOrder(BTNode* root)
{
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

2.中序遍历

中序遍历的顺序为 左子树 —> 根 —> 右子树。
在这里插入图片描述

代码如下（示例）：

// 二叉树中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%C ", root->data);
	InOrder(root->right);
}

3.后序遍历

后序遍历的顺序为 左子树 —> 右子树 —> 根。
在这里插入图片描述

代码如下（示例）：

// 二叉树后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%C ", root->data);
}

附加: 前三种遍历对比图

在这里插入图片描述

4.层序遍历

层序遍历就是一层一层地遍历，如下图+源码！
在这里插入图片描述

这里我们用队列来实现层序遍历，如下图思路！由于这里会遇到大量队列知识，可以参考：队列实现

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

代码如下（示例）：

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	if (root == NULL)
		return;

	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", front->data);

		// 孩子带进队列
		if (front->left)
			QueuePush(&q, front->left);

		if (front->right)
			QueuePush(&q, front->right);
	}
	printf("\n");
	QueueDestroy(&q);
}

三、四种遍历相关的面试题

1.第一题：144. 二叉树的前序遍历

Leedcode链接

(1)题目

在这里插入图片描述

题目如下（示例）：

int* preorderTraversal(struct TreeNode* root, int* returnSize)
{ }

（2）思路

这里要注意：这道题的返回值为 int* 即要返回一个数组，且*returnSize为数组元素大小
1.size需要自己计算，可以用之前写过的 TreeSize ,不太懂得可以参考 ：二叉树节点个数
2.用1子函数来写前序遍历的三步
3.在递归的时候要注意传的是i的地址，因为在传参时，形参是实参的一份临时拷贝，要传&i
4.最后把size 给 *returnSize ，以保证数组大小！

（3）源码

代码如下（示例）：

//先求下数组的大小，便于开辟空间
int Treesize(struct TreeNode* root)
{
    return root == NULL ? 0 : Treesize(root->left) + Treesize(root->right) + 1 ;
}
void _preorderTraversal(struct TreeNode* root , int* a, int* pi)
{
     if(root == NULL)
    {
        return;
    }
    a[(*pi)++] = root->val;
    _preorderTraversal(root -> left ,a,pi);
    _preorderTraversal(root->right , a ,pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    int size = Treesize(root);
    int* a = (int*)malloc(sizeof(int)*size);
    int i = 0;
    _preorderTraversal(root , a , &i);
    *returnSize = size;
    return a;
}

2.第二题：94. 二叉树的中序遍历

Leedcode链接

3.第三题：145. 二叉树的后序遍历

Leecode链接

第二题和第三题和第一题解法一样，这里不做过多介绍，这里直接给出答案！

第二题答案：如下（示例）：

int Treesize(struct TreeNode* root)
{
    return root == NULL ? 0 : Treesize(root->left) + Treesize(root->right) + 1 ;
}
void _inorderTraversal(struct TreeNode* root , int* a, int* pi)
{
     if(root == NULL)
    {
        return;
    }
    _inorderTraversal(root -> left ,a,pi);
    a[(*pi)++] = root->val;
    _inorderTraversal(root->right , a ,pi);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
    int size = Treesize(root);
    int* a = (int*)malloc(sizeof(int)*size);
    int i = 0;
    _inorderTraversal(root , a , &i);
    *returnSize = size;
    return a;
}

第三题答案：如下（示例）：

int Treesize(struct TreeNode* root)
{
    return root == NULL ? 0 : Treesize(root->left) + Treesize(root->right) + 1 ;
}
void _postorderTraversal(struct TreeNode* root , int* a, int* pi)
{
     if(root == NULL)
    {
        return;
    }
    _postorderTraversal(root -> left ,a,pi);
    _postorderTraversal(root->right , a ,pi);
    a[(*pi)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize)
{
    int size = Treesize(root);
    int* a = (int*)malloc(sizeof(int)*size);
    int i = 0;
    _postorderTraversal(root , a , &i);
    *returnSize = size;
    return a;
}

4.第四题：判断二叉树是否是完全二叉树

（1）思路

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

（2）源码

代码如下（示例）：

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front == NULL)
		{
			break;
		}
		else
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}

	// 遇到空了以后，检查队列中剩下的节点
	// 1、剩下全是空给，则是完全二叉树
	// 2、剩下存在非空，则不是完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front)
		{
			QueueDestroy(&q);
			return false;
		}
	}

	QueueDestroy(&q);
	return true;
}

5.第五题：KY11 二叉树遍历

牛客网链接

（1）题目

在这里插入图片描述

（2）思路

这道题需要分成不同地模块来完成！
1.构建树，用 结构体 TreeNode
2.写中序遍历，不会写的看前面文章！
3.如果是 # 就跳过并返回NULL ，如下图所示！

在这里插入图片描述在这里插入图片描述

构建完二叉树之后，就可以对每一个节点进行中序遍历并打印，不会中序遍历的可以参考前面！
在这里插入图片描述

（3）源码

代码如下（示例）：

#include<stdio.h>
#include <stdlib.h>
struct TreeNode {
    struct TreeNode* left;
    struct TreeNode* right;
    char val;
};
struct TreeNode* CreateTree(char* str, int* pi) {
    if (str[*pi] == '#') {
        (*pi)++;
        return NULL;
    }
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root -> val = str[(*pi)++];
    root -> left = CreateTree(str, pi);
    root -> right = CreateTree(str, pi);
    return root;
}
void InOrder(struct TreeNode* root) {
    if (root == NULL)
        return;
    InOrder(root->left);
    printf("%c ", root->val);
    InOrder(root->right);
}
int main() {
    char str[100];
    while ((scanf("%s", str) != EOF)) {
        int i = 0;
        struct TreeNode* root = CreateTree(str, &i);
        InOrder(root);
    }
    return 0;
}

最后：销毁二叉树

在我们每次创建完二叉树之后要销毁二叉树，否则会导致内存泄漏！

（1）源码

代码如下（示例）：

void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}

（2）递归图解

想销毁如图所示的二叉树！为了方便我只画了一条路径上的销毁递归图，感兴趣的可以都画！
在这里插入图片描述

在这里插入图片描述

总结

以上就是今天要讲的内容，本文介绍二叉树的四种遍历方式以及必备的面试题。
如果我的博客对你有所帮助记得三连支持一下，感谢大家的支持！
在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/6524.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

LeetCode.每日一题 831. 隐藏个人信息

LeetCode.每日一题 831. 隐藏个人信息

Halo&#xff0c;这里是Ppeua。平时主要更新C语言&#xff0c;C&#xff0c;数据结构算法......感兴趣就关注我吧&#xff01;你定不会失望。 &#x1f308;个人主页&#xff1a;主页链接 &#x1f308;算法专栏&#xff1a;专栏链接 我会一直往里填充内容哒&#xff01; &…
阅读更多...
C语言函数：内存函数memcmp()

C语言函数：内存函数memcmp()

wpC语言函数&#xff1a;内存函数memcmp()以及函数实现与使用。 memcmp()&#xff1a; 头文件:#include <string.h> 作用&#xff1a; 进行内存比较。 参数&#xff1a; 解释&#xff1a;ptr1和ptr2是指针&#xff0c;从这个两个指针开始往后num个字节&#xff0c;将两…
阅读更多...
【Python入门第四十六天】Python丨NumPy 数组重塑

【Python入门第四十六天】Python丨NumPy 数组重塑

数组重塑 重塑意味着更改数组的形状。 数组的形状是每个维中元素的数量。 通过重塑&#xff0c;我们可以添加或删除维度或更改每个维度中的元素数量。 从 1-D 重塑为 2-D 实例 将以下具有 12 个元素的 1-D 数组转换为 2-D 数组。 最外面的维度将有 4 个数组&#xff0c;…
阅读更多...
【Redis】BigKey问题

【Redis】BigKey问题

文章目录MoreKey案例大批量往redis里面插入100W测试数据key(管道)生产上限制keys*/flushdb/flushall等危险命令以防止误删误用scan命令代替了keys *,避免了查询卡顿BigKey案例多大算大key危害如何产生如何发现 redis-cli --bigkeys、memory usage如何删除->渐进式删除BigKey…
阅读更多...
C++面经总结4

C++面经总结4

说一下new和malloc的区别 new是操作符&#xff0c; malloc是函数 malloc申请的空间是不能初始化的&#xff0c; 而new是可以初始化的 malloc申请空间的时候需要手动计算空间大小&#xff0c;而new可以直接在[]里面给个数就行。 malloc的返回值是void*, 使用时必须强转&#xf…
阅读更多...
FFmpeg添加字幕的详细操作

FFmpeg添加字幕的详细操作

FFmpeg添加字幕的详细操作 在视频中添加字幕可以使视频更具可读性&#xff0c;并为观众提供更好的观看体验&#xff0c;这在多语种内容中尤为重要。FFmpeg是一个流行的开源视频处理工具&#xff0c;它可以被用来给视频添加字幕。本文将介绍FFmpeg集成libass的编译流程&#xf…
阅读更多...
【沐风老师】教你在3dMax中使用Greeble插件结合变形修改器建模

【沐风老师】教你在3dMax中使用Greeble插件结合变形修改器建模

3dMax在Greeble中使用变形修改器 Greeble一个有趣的修改器插件，用于快速生成诸如低模城市建筑群、太空船模型、死亡星等的随机细节。。。 我们在之前的教程中介绿过Greeble的安装和基本使用方法，在本教程中，我们将学习如何使用Greeble插件和变形修改器来制作效果。 【开始…
阅读更多...
深度学习数据集—水果数据集大合集

深度学习数据集—水果数据集大合集

近期整理的各类水果&#xff08;包括干果&#xff09;数据集&#xff0c;分享给大家。 1、8类水果图片数据集&#xff08;每类100张图片左右&#xff09;[橘子&#xff0c;菠萝&#xff0c;苹果&#xff0c;木瓜&#xff0c;火龙果&#xff0c;香蕉&#xff0c;樱桃&#xff0…
阅读更多...
聊天Chat

聊天Chat

前言 加油 原文 聊天常用会话 ❶ Don’t count on him. 别指望他。 ❷ They underestimated the enemy’s strength. 他们低估了敌人的力量。 ❸ The plan went according to his perspective. 计划是按照他的想法进行的。 ❹ This project involves many difficulties. …
阅读更多...
【C++】开散列哈希表封装实现unordered_map和unordered_set

【C++】开散列哈希表封装实现unordered_map和unordered_set

在未达成目的之前&#xff0c;一切具有诱惑力的事物都显得那么不堪一击 文章目录一、unordered系列关联式容器二、哈希函数和哈希冲突三、闭散列&#xff08;你抢我的位置&#xff0c;我抢他的位置&#xff09;1.哈希表结构2.Insert()3.Erase()&#xff08;标记的伪删除法&…
阅读更多...
归并排序介绍、详解、案例

归并排序介绍、详解、案例

排序 计数排序介绍、详解、案例快速排序介绍、详解、案例归并排序介绍、详解、案例 归并排序也是基于分治法的排序算法&#xff0c;为了排序长度为n的数组&#xff0c;需要先排序长度为n/2的字数组&#xff0c;然后合并这两个排序字数组于是整个数组也就排序完毕。 排序过程 以…
阅读更多...
浅谈JVM(五)：虚拟机栈帧结构

浅谈JVM(五)：虚拟机栈帧结构

上一篇&#xff1a; 浅谈JVM(一)&#xff1a;Class文件解析 浅谈JVM(二)&#xff1a;类加载机制 浅谈JVM(三)&#xff1a;类加载器和双亲委派 浅谈JVM(四)&#xff1a;运行时数据区 5.虚拟机栈帧结构 ​ 方法是程序执行的最小单元&#xff0c;每个方法被执行时都会创建一个栈帧…
阅读更多...
驱动开发：内核使用IO/DPC定时器

驱动开发：内核使用IO/DPC定时器

本章将继续探索驱动开发中的基础部分&#xff0c;定时器在内核中同样很常用&#xff0c;在内核中定时器可以使用两种&#xff0c;即IO定时器&#xff0c;以及DPC定时器&#xff0c;一般来说IO定时器是DDK中提供的一种&#xff0c;该定时器可以为间隔为N秒做定时&#xff0c;但如…
阅读更多...
内卷？焦虑？35岁？找不到工作？端正态度激励一下正在挣扎的Android程序员

内卷？焦虑？35岁？找不到工作？端正态度激励一下正在挣扎的Android程序员

前言 亲爱的各位Android程序员&#xff0c;您们好&#xff1a; 我理解您们的焦虑和困惑&#xff0c;但我想告诉您的是&#xff1a;作为一名Android程序员&#xff0c;您依然是非常有前途和市场需求的职业人才。 首先&#xff0c;您要知道&#xff0c;移动互联网时代的普及率…
阅读更多...
【数据结构】时间复杂度和空间复杂度

【数据结构】时间复杂度和空间复杂度

&#x1f466;个人主页&#xff1a;Weraphael ✍&#x1f3fb;作者简介&#xff1a;目前学习C和算法ing ✈️专栏&#xff1a;【数据结构】 &#x1f40b; 希望大家多多支持&#xff0c;咱一起进步&#xff01;&#x1f601; 如果文章对你有帮助的话 欢迎 评论&#x1f4ac; 点…
阅读更多...
1662_MIT 6.828 JOS check_page_free_list实现分析以及boot_alloc问题修复

1662_MIT 6.828 JOS check_page_free_list实现分析以及boot_alloc问题修复

全部学习汇总&#xff1a; GreyZhang/g_unix: some basic learning about unix operating system. (github.com) 继续尝试完善分析JOS的代码中存储管理的部分。 上次看到了这里&#xff0c;本来想先去看看这两个函数实现。但是缺失了调用场景&#xff0c;感觉理解也不一定准确。…
阅读更多...
对拍程序 并查集专题 （C++ | 洛谷 | acwing | 蓝桥）

对拍程序 并查集专题 （C++ | 洛谷 | acwing | 蓝桥）

文章目录【蓝桥杯专题】 &#xff08;C | 洛谷 | acwing | 蓝桥&#xff09;1249. 亲戚836. 合并集合837. 连通块中点的数量238. 银河英雄传说 【带权并查集】145. 超市 【并查集 贪心】4793. 危险程度 (连通块并查集 &#xff09;普通oi 读文件对拍程序【蓝桥杯专题】 &#…
阅读更多...
树和二叉树相关的练习（选择题）

树和二叉树相关的练习（选择题）

目录 一、二叉树 二、堆 三、遍历二叉树 一、二叉树 某二叉树共有 399 个结点&#xff0c;其中有 199 个度为 2 的结点&#xff0c;则该二叉树中的叶子结点数为&#xff08; &#xff09;。 A. 不存在这样的二叉树 B. 200 C. 198 D. 199 下列数据结构中&#xff0c;不适合…
阅读更多...
C++ Primer Plus 学习笔记（八）——输入、输出和文件

C++ Primer Plus 学习笔记（八）——输入、输出和文件

1 流和缓冲区 C程序把输入和输出看作字节流。输入时&#xff0c;程序从输入流中抽取字节&#xff1b;输出时&#xff0c;程序将字节插入到输出流中。 缓冲区是用作中介的内存块&#xff0c;它是将信息从设备传输到程序或从程序传输给设备的临时存储工具&#xff0c;通过使用缓…
阅读更多...
HTTP协议：当下最主流的应用层协议之一，你确定不了解一下吗？

HTTP协议：当下最主流的应用层协议之一，你确定不了解一下吗？

一.HTTP协议的含义http是什么&#xff1f;超文本传输协议&#xff08;Hyper Text Transfer Protocol&#xff0c;HTTP&#xff09;是一个简单的请求-响应协议&#xff0c;它通常运行在TCP之上。‘超’可以理解为除了文本之外的图片&#xff0c;音频和视频&#xff0c;和一些其他…
阅读更多...
最新文章

Copyright @ 2022~2023