二叉树的遍历+基础练习

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

前面完全二叉树适合存放数据,又因为它在内存中连续存储,因此用顺序表来实现它,并介绍了堆排序及TOP-K问题。

今天我们了解一下二叉树的遍历问题,并完成几道二叉树基础练习


目录

二叉树的遍历

先序

访问顺序:

图示:

 中序

访问顺序:

图示:

后序

访问顺序:

图示:

手动构建链式二叉树 

定义

 创建节点

创建二叉树 

前序遍历

中序遍历

 后序遍历

练习

求二叉树节点树

求二叉树叶子节点个数 

第k层节点数 

二叉树深度

二叉树查找值为x的节点


二叉树的遍历

二叉树的遍历有:前序/中序/后序的递归结构遍历:

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之间。
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

以下面二叉树为例,进行先序,中序,后序遍历:

二叉树的遍历+基础练习

先序

分析:从根节点开始,先访问根,再访问左子树(左子树中先访问根节点,在访问左子树和右子 树),最后访问右子树(先访问根节点,在访问左子树和右子树)

访问顺序:

先访问树tree根1,再访问tree左子树L1:

访问L1根2,再访问其左子树Ll2:

访问Ll2根3,再访问其左子树:左子树为空,访问其右子树,右子树为空,返回上一个子树L1;

此时L1左子树访问完毕,访问L1右子树NULL,为空返回上一个树tree;

此时tree根和左子树访问完毕,访问tree右子树R1:

访问R1根4,再访问R1左子树Rl1:

访问Rl1根5,再访问Rl1左子树和右子树NULL,返回上一个树R1;

此时,R1左子树Rl1访问完毕,接着访问R1右子树Rr1:

访问Rr1根6,再访问Rr1左右子树NULL,返回上一个树R1;

此时R1根和左右子树访问完毕,返回上一个树tree;

此时tree的根和左子树访问完毕,及整个树访问完毕。

图示:

二叉树的遍历+基础练习

二叉树的遍历+基础练习

 中序

分析:即先访问左子树,左子树访问完毕后再访问根节点,根节点访问完后,最后访问右子树。左子树和右子树中也是先访问左子树,再根,最后右子树

访问顺序:

从tree根开始,先访问其左子树L1:

左子树L1不为空,访问L1左子树Ll2:

左子树Ll2不为空,访问Ll2左子树:

左子树为空,访问Ll2根3,再访问Ll2的右节点,右节点为空,返回子树L1;

子树L1的左子树访问完毕,访问L1的根2,再访问L1的右子树,为空,返回树tree;

tree的左子树访问完毕,访问tree根1,接着访问tree右子树R1:

右子树R1不为空,访问R1左子树Rl1:

Rl1不为空,访问Rl1左子树,左子树为空,访问Rl1根5,再访问其右子树:

右子树为空,返回上一个树R1;

R1左子树访问完毕,访问其根4,接着访问其右子树Rr1:

Rr1不为空,访问其左子树,左子树为空,访问Rr1根6,再访问其右子树为空,返回R1;

此时tree的左子树,根,和右子树都访问完毕。

图示:

二叉树的遍历+基础练习二叉树的遍历+基础练习

后序

分析:先访问左子树(左子树中也是左子树,右子树,根),再访问右子树(右子树中也是左子树,右子树,根),最后访问根节点。

访问顺序:

先访问tree,不为空,访问其左子树L1,L1不为空,访问其左子树Ll2;

Ll2不为空,访问其左子树,为空;访问其右子树,为空;访问其根3,返回上一个树L1;

L1左子树访问完毕,访问其右子树,为空;访问其根2,返回上一个树tree;

tree的左子树访问完毕,访问其右子树R1,R1不为空,访问其左子树Rl1;

Rl1不为空,访问其左子树,为空;访问其右子树,为空,访问其根5,返回上一个树R1;

R1左子树访问完毕,访问其右子树Rr1,Rr1不为空,访问其左子树;

Rr1左子树为空,访问其右子树,为空,访问其根6,返回上一个树R1;

此时R1左子树右子树访问完毕,访问其根4,放回上一个树tree;

此时tree的左右子树访问完毕,访问其根1;整个树访问完毕。

图示:

二叉树的遍历+基础练习

二叉树的遍历+基础练习

手动构建链式二叉树 

不难发现,上述遍历时中途总会返回上一层树,已经用到了递归思想,这里我们手动实现一个简单的链式二叉树,完成我们的前序,中序,后序的遍历。

定义

定义每个节点由数据,左子树地址和右子树地址组成

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;  //数据
	struct BinaryTreeNode* left;   //左子树地址
	struct BinaryTreeNode* right;  //右子树地址
}BTNode;

 创建节点

将固定的数据放入创建的节点中,左右子树指针置空

BTNode* BuyNode(BTDataType x)
{
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	root->data = x;
	root->left = NULL;
	root->right = NULL;
	return root;
}

创建二叉树 

手动创建节点,并将左右子树指针指向固定的位置,以上述二叉树为例:

//手动创建
BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	return node1;
}

前序遍历

依照我们对前序遍历的顺序分析:根,左子树,右子树,编写前序代码:

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

中序遍历

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

 后序遍历

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

练习

求二叉树节点树

方法一:前序中序后序时添加一个计数变量(变量为全局或者静态,防止递归时计数重置)

缺点:重复调用时计数会累加,每次调用时须将count重新置0;

//定义全局或者静态变量
//多次调用会累加
int count = 0;
int BTreeSize(BTNode* root)
{
	if (root == NULL)
		return;
	++count;
	BTreeSize(root->left);
	BTreeSize(root->right);
	return  count;
}

方法二:遍历+计数(遍历时将遍历地址传过去)

//遍历+计数
//将变量地址传过去,计数---思想最优
void BTreeSize(BTNode* root,int* count)
{
	if (root == NULL)
		return;
	++(*count);
	BTreeSize(root->left,count);
	BTreeSize(root->right,count);
}

方法三:递归--分治思想

当根为空时,返回0,左子树节点个数+右子树节点个数+1(根节点本身)

//递归--分治思想--节点个数
int BTreeSize(BTNode* root)
{
	return root == NULL ? 0 : BTreeSize(root->left) + BTreeSize(root->right) + 1;
}

求二叉树叶子节点个数 

二叉树叶子节点数 = 左子树叶子节点数 + 右子树节点数

叶子节点:左子树和右子树为空的节点

//叶子节点个数
int BTreeLeafSize(BTNode* root)
{
	if (root==NULL)
	{
		return 0;
	}
	if (root->left == NULL&&root->right==NULL)
	{
		return 1;
	}
	return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}

第k层节点数 

 求tree的第三层节点数

即L1和R1的第二层节点数之和

即Ll1、Rl1和Rr1第一层节点数之和

当k=1时,返回1即可

二叉树的遍历+基础练习

//第k层节点个数
int BTreeLeveSize(BTNode* root,int k)
{
	assert(k>=1);
	if (root==NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BTreeLeveSize(root->left, k - 1) + BTreeLeveSize(root->right, k - 1);

二叉树深度

二叉树的深度 = 左子树和右子树中最大深度度+1

需要比较左右子树高度,判断返回哪一个

二叉树的遍历+基础练习

//二叉树深度
int BTreeDepth(BTNode* root)
{
	if (root==NULL)
	{
		return 0;
	}
	int leftdepth = BTreeDepth(root->left);
	int rightdepth = BTreeDepth(root->right);
	return leftdepth >rightdepth ? leftdepth + 1 : rightdepth + 1;
}

二叉树查找值为x的节点

判断根是否为要找的节点,是则返回节点地址

不是则进左子树中去找,找到返回节点地址,找不到返回空

再进右子树取找,找到返回节点地址,找不到返回空

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root==NULL)
	{
		return NULL;
	}
	if (root->data == x)
		return root;
	if (BinaryTreeFind(root->left, x))
		return BinaryTreeFind(root->left,x);
	if (BinaryTreeFind(root->right, x))
		return BinaryTreeFind(root->right, x);
	return NULL;
}

二叉树的遍历+基础练习文章来源地址https://www.toymoban.com/news/detail-488384.html

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

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

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

相关文章

  • 二叉树的基础概念及遍历

    1、树的概念 树是一种非线性的数据结构,是由n(n=0)个有限结点组成一个具有层次关系的集合,将它称为树,是因为在形状上像一颗倒着的树,如下图所示就是一颗二叉树。 可以发现,对于树中的根节点,没有前驱节点,有多个后驱节点;对于其他节点,有一个前驱节点,

    2024年01月20日
    浏览(38)
  • 数据结构—基础知识(11):二叉树的遍历

    二叉树的遍历 是指按某条搜索路径访问树中每个结点,使得每个结点均被访问一次,而且仅被访问一次。由于二叉树是一种非线性结构,每个结点都可能有两棵子树,因而需要寻找一种规律,以便使二叉树上的结点能排列在一个线性队列上,进而便于遍历。 由二叉树的递归

    2024年02月19日
    浏览(44)
  • 【二叉树part01】| 二叉树的递归遍历、二叉树的迭代遍历、二叉树的统一迭代遍历

    目录 ✿二叉树的递归遍历❀ ☞LeetCode144.前序遍历 ☞LeetCode145.二叉树的后序遍历  ☞LeetCode94.二叉树的中序遍历  ✿二叉树的迭代遍历❀  ☞LeetCode144.前序遍历  ☞LeetCode145.二叉树的后序遍历   ☞LeetCode94.二叉树的中序遍历  ✿二叉树的统一迭代遍历❀   ☞LeetCode144.前序遍

    2024年02月09日
    浏览(37)
  • 力扣(144. 二叉树的前序遍历&&94.二叉树的中序遍历&&145. 二叉树的后序遍历)

    题目链接 题目1: 思路:较简单的思路,就是先将左孩子全部入栈,然后出栈访问右孩子,右孩子为空,再出栈,不为空,右孩子入栈,然后再次循环访问左孩子。 题目链接 题目2: 思路:同前序遍历一样,只不过访问结点,改为出栈时访问。 题目3链接 题目3: 思路1:同样

    2024年01月19日
    浏览(50)
  • 算法D14 | 二叉树1 | 144. 二叉树的前序遍历 145. 二叉树的后序遍历 94. 二叉树的中序遍历

    理论基础  需要了解 二叉树的种类,存储方式,遍历方式 以及二叉树的定义  文章讲解: 二叉树既可以链式存储(利用指针,类似栈和队列),也可以用数组表示。 深度优先遍历 前序遍历(递归法,迭代法) 中序遍历(递归法,迭代法) 后序遍历(递归法,迭代法)

    2024年02月20日
    浏览(38)
  • 【Leetcode60天带刷】day14二叉树——144.二叉树的前序遍历,145.二叉树的后序遍历,94.二叉树的中序遍历

    144. 二叉树的前序遍历 给你二叉树的根节点  root  ,返回它节点值的  前序   遍历。 示例 1: 示例 2: 示例 3: 示例 4: 示例 5: 提示: 树中节点数目在范围  [0, 100]  内 -100 = Node.val = 100 145. 二叉树的后序遍历 给你一棵二叉树的根节点  root  ,返回其节点值的  后序遍历

    2024年02月10日
    浏览(50)
  • 二叉树的概念|满二叉树与完全二叉树|二叉树的性质|二叉树的存储结构

    在数据结构中树的用途其实并不大,用得更多的其实是二叉树。所以在本章我们将详细讲解二叉树。 一颗二叉树是结点的一个 有限集合 ,该集合: 或者为空 或者由一个根节点加上两颗(互不相交)别称为左子树和右子树的二叉树组成 如图我们可知, 二叉树的特点: 二叉

    2024年01月21日
    浏览(41)
  • 完全二叉树、完美二叉树、完满二叉树、计算完全二叉树的结点

    对于完美二叉树,我们常用的是另一个名称:满二叉树 完美二叉树的定义: 完美二叉树是一种特殊的完全二叉树,每层都是满的,像一个稳定的三角形 完全二叉树的定义: 全二叉树从根结点到倒数第二层满足完美二叉树,最后一层可以不完全填充,其叶子结点都靠左对齐。

    2023年04月08日
    浏览(79)
  • 【LeetCode】102. 二叉树的层序遍历、107. 二叉树的层序遍历 II

     作者:小卢 专栏:《Leetcode》 喜欢的话:世间因为少年的挺身而出,而更加瑰丽。                                  ——《人民日报》 102. 二叉树的层序遍历 给你二叉树的根节点  root  ,返回其节点值的  层序遍历  。 (即逐层地,从左到右访问所有节点)  示例:

    2024年02月13日
    浏览(39)
  • 【数据结构】树,二叉树,满二叉树,完全二叉树的定义和二叉树的基本操作

    🎊专栏【数据结构】 🍔喜欢的诗句:更喜岷山千里雪 三军过后尽开颜。 🎆音乐分享【勋章】 大一同学小吉,欢迎并且感谢大家指出我的问题🥰 目录 ⭐树 🏳️‍🌈定义  🏳️‍🌈注意 🍔树的基本术语 ⭐二叉树 🏳️‍🌈定义 🎆二叉树和树的区别 🏳️‍🌈二叉树

    2024年02月05日
    浏览(66)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包