首页 > 其他分享 >数据结构初阶 遍历二叉树问题(一)

数据结构初阶 遍历二叉树问题(一)

时间:2024-07-07 15:01:14浏览次数:18  
标签:遍历 BTNode 初阶 right 二叉树 root left

一. 链式二叉树的实现

1. 结构体代码

typedef int BTDateType;
typedef struct BinaryTreeNode
{
	BTDateType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

大概的图形是这样子

2. 增删查改

我们这里要明确的一点的 二叉树的增删查改是没有意义的

为什么呢?

我们来看下图

 

这颗二叉树的排列没有任何的规律 并且我们要插入也不知道往哪里插入

所以说 单纯的对二叉树curd操作是没有任何意义的

那么我们学习二叉树的意义在哪里呢?

这里就要引出我们后面的搜索二叉树 平衡二叉树 以及红黑二叉树

这些知识我们都会在后面的博客中学习到

二. 二叉树的遍历

1. 二叉树遍历的三种方式

前序遍历

前序遍历的大概解释: 先遍历根 再遍历左数 再遍历右数

还是一样 我们先来看图

如果我们要使用前面序遍历这个图

那么打印的顺序会是什么呢?

画图来看看

打印的顺序如下: 

 

中序遍历

中序遍历的大概解释 先遍历左子树 再遍历根 再遍历右子树

这里大家可以试着自己做一下

后序遍历

后序遍历的大概解释 先遍历左子树 再遍历根 再遍历右子树

这个大家可以自己试着做一做 这里就不过多赘述了

2. 二叉树遍历的递归实现

我们首先先自己实现如图的一个二叉树出来

 

要想自己实现一个二叉树其实也很简单

我们先设计一个BuyBTnode函数 用来创建二叉树的节点

之后给每一个节点赋上值 左右节点各自指向如图的位置就可以

代码表示如下

//初始化
BTNode* BuyNode(BTDateType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}
//造树
BTNode* CreatTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	BTNode* node7 = BuyNode(7);
	
	//连接
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	node3->right = node7;

	return node1;
}

 

接下来我们就开始写递归函数了

代码表示如下

//前序列
void PreOrder(BTNode* root)
{
	if(root==NULL)
	{
		printf("NULL");
		return;
	}

	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

我们可以发现 这里能够可以实现先序打印

那么我们试试看中序打印

(大家想想看 需要改变哪一行代码就可以实现中序打印)

//中序列
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

这个就需要我们理解每一行的功能

这一行代码的功能是实现遍历左子树

preorder(root->left);

这一行代码的功能是遍历右子树

preorder(root->right);

那么想要先遍历左子树 然后遍历根 然后遍历右子树 需要什么样的顺序呢?

没错 这样子的三行代码就可以了

preorder(root->left);
	printf("%c ", root->date);
	preorder(root->right);

那么后序打印呢?

preorder(root->left);
	preorder(root->right);
	printf("%c ", root->date);

很简单是吧

3 二叉树求节点个数

这里有两种实现方式

第一种我们可以传一个count的地址进去 然后再遍历内部结构 如果不是空值就加一

思路大概是这样子

我们来看看函数实现

void  Treesize(BTNode* root, int* psize)
{
	if (root == NULL)
	{
		return;
	}
	++(*psize);
	Treesize(root->left, psize);
	Treesize(root->right, psize);
}

这里还有另一种解法

我们使用递归实现

代码表示如下

int Treesize(BTNode* root)
{
	return root == NULL ? 0
		: Treesize(root->left)
		+ Treesize(root->right) + 1;
}

 我们发现也是可以完美实现

以上便是本文所有内容了,如有错误请各位大佬不吝赐教,感谢留言

标签:遍历,BTNode,初阶,right,二叉树,root,left
From: https://blog.csdn.net/Zbldx/article/details/140232262

相关文章

  • 二叉树的链式结构
    前言Hello,友友们,小编将继续重新开始数据结构的学习,前面讲解了堆的部分知识,今天将讲解二叉树的链式结构的部分内容。1.概念回顾与新增二叉树是一种数据结构,其中每个节点最多有两个子节点,分别是左子节点和右子节点。二叉树的链式结构表示是使用指针(或引用)来连接节点,形成......
  • LCR 156. 序列化与反序列化二叉树
    序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列/反序列化算法执行......
  • 数据结构——二叉树相关题目
    1.寻找二叉树中数值为x的节点//寻找二叉树中数值为x的节点BTNode*TreeFind(BTNode*root,BTDataTypex)//传过来二叉树的地址和根的地址,以及需要查找的数据{ if(root==Null) { returnNull; }//首先需要先判断这个树是否为空,如果为空直接返回空 if(root->data=......
  • leetcode 257. 二叉树的所有路径
    给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。 示例1:输入:root=[1,2,3,null,5]输出:["1->2->5","1->3"]示例2:输入:root=[1]输出:["1"]java解题思路及代码实现递归法packagecom.java......
  • leetcode 102. 二叉树的层序遍历
    给你二叉树的根节点 root ,返回其节点值的 层序遍历 。(即逐层地,从左到右访问所有节点)。示例1:输入:root=[3,9,20,null,null,15,7]输出:[[3],[9,20],[15,7]]示例2:输入:root=[1]输出:[[1]]示例3:输入:root=[]输出:[]提示:树中节点数目在范围 [0,2000] ......
  • 二叉树的顺序存储
    目录顺序存储:简介:节点的位置关系:优缺点:优点:缺点:二叉树顺序存储的模拟实现:向上调整算法:向下调整算法:二叉树的初始化:直接初始化:建堆初始化:二叉树的头删:二叉树的尾插:二叉树的取顶端元素:二叉树的判空:二叉树的销毁:完整代码:顺序存储:简介:顺序结构存储就是使......
  • 代码随想录day15 平衡二叉树 | 二叉树的所有路径 | 左叶子之和 | 完全二叉树的节点个
    平衡二叉树平衡二叉树解题思路二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数。二叉树节点的高度:指从该节点到叶子节点的最长简单路径边的条数。这道题由于需要求节点的高度差来进行判断,因此我们需要用后序遍历,先左右,后中间。推荐使用递归把每个节点的高度算出来......
  • 代码随想录算法训练营第十五天|110.平衡二叉树、257.二叉树的所有路径、404.左叶子之
    110平衡二叉树1classSolution{2public:3intGetHeight(TreeNode*root){4if(!root){5return0;6}7intleftHeight=GetHeight(root->left);8if(leftHeight==-1)ret......
  • python数据结构(树和二叉树)
    树非线性结构一对多根结点(无前驱)多个叶子结点(无后继)其他数据元素(一个前驱,多个后驱)树与二叉树转换树与二叉树均可用二叉链表作为存储结构,则以二叉链表为媒介可导出树之间的一个对应关系-----即给定一颗树,可以找到唯一一颗二叉树与之对应。把树转化为二叉树步骤一:加线......
  • 代码随想录算法训练营第十四天| 226.翻转二叉树 、101. 对称二叉树、104.二叉树的最大
    二叉树学习2226题翻转二叉树,改一下前序递归遍历,每次遍历的时候都调换一下左右结点即可。classSolution{public:voidpreorder(TreeNode*root){if(root==nullptr){return;}TreeNode*tmp;tmp=root->left;......