首页 > 其他分享 >[数据结构]二叉树的建立与遍历(递归)

[数据结构]二叉树的建立与遍历(递归)

时间:2024-03-24 19:30:54浏览次数:22  
标签:遍历 NULL BTNode 二叉树 printf 数据结构 root left

一、二叉树的遍历与建立

首先我们拥有如下二叉树:

要了解二叉树遍历,我们得先了解二叉树的三种遍历方式:前序遍历,中序遍历,后序遍历

1.前序遍历

前序遍历:根,左子树,右子树

遍历的结果就是:1 2 4 8 N N 9 N N 5 10 N N 11 N N 3 6 N N 7 N N

2.中序遍历

中序遍历:左子树 根 右子树

遍历的结果:N 8 N 4 N 9 N 2 N 10 N 5 N 11 N N 6 N 5 N 7 N

3.后序遍历

后续遍历:左子树 右子树 根

遍历的结果:N N 8 N N 9 4 N N 10 N N 11 5 2 N N 6 N N 7 3 1

注意:N是NULL(即不存在次节点)

4.手撕一棵二叉树

那么我们如何用代码实现这样的遍历并打印,我们先可以写一个二叉树

typedef struct BinTreeNode
{
	struct BinTreeNode* left;
	struct BinTreeNode* right;
	int val;
}BTNode;

然后我们创建相应的节点:

BTNode* BuyBTNode(int val)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->val = val;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}

然后我们手撕一棵二叉树

BTNode* CreateTree()
{
	BTNode* n1 = BuyBTNode(1);
	BTNode* n2 = BuyBTNode(2);
	BTNode* n3 = BuyBTNode(3);
	BTNode* n4 = BuyBTNode(4);
	BTNode* n5 = BuyBTNode(5);
	BTNode* n6 = BuyBTNode(6);

	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n4->left = n5;
	n4->right = n6;

	return n1;
}

这样们就创建好一个二叉树了,接下来我们来写如何遍历吧!

5.用函数来完成遍历

1)前序遍历:

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

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

按照 根 左子树 右子树 打印如果不为空就继续递归 打印根数据 然后 左子树 最后 右子树 如果为空就打印N然后返回

2)中序遍历

按照 左子树 根 右子树 大体思路如上

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

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

3)后序遍历

按照:左子树 右子树 根

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

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}

下面我们来进行一下测试:

首先二叉树如图,我们不然得到

前序遍历:1 2 3 N N N 4 5 N N 6 N N

中序遍历:N 3 N 2 N 1 N 5 N 4 N 6 N

后序遍历:N N 3 N 2 N N 5 N N 6 4 2

我们把上面的代码整合一下

#include<stdio.h>
#include<stdlib.h>
typedef struct BinTreeNode
{
	struct BinTreeNode* left;
	struct BinTreeNode* right;
	int val;
}BTNode;
BTNode* BuyBTNode(int val)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->val = val;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}
BTNode* CreateTree()
{
	BTNode* n1 = BuyBTNode(1);
	BTNode* n2 = BuyBTNode(2);
	BTNode* n3 = BuyBTNode(3);
	BTNode* n4 = BuyBTNode(4);
	BTNode* n5 = BuyBTNode(5);
	BTNode* n6 = BuyBTNode(6);

	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n4->left = n5;
	n4->right = n6;

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

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

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

	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}



int main()
{
	BTNode* root = CreateTree();
	printf("前序遍历:");
	PreOrder(root);
	printf("\n");

	printf("中序遍历:");
	InOrder(root);
	printf("\n");

	printf("后序遍历:");
	PostOrder(root);
	printf("\n");

	return 0;
}

运行结果:

我们发现结果与我们预期的一致,所以我们完成了二叉树的遍历

标签:遍历,NULL,BTNode,二叉树,printf,数据结构,root,left
From: https://blog.csdn.net/2301_80017277/article/details/136974841

相关文章

  • 数据结构----认识树和二叉树
    数据结构----认识树和二叉树树和二叉树是计算机科学中重要的数据结构,它们提供了一种分层的组织方式,并被广泛应用于各个领域。本篇博客将介绍树的概念、结构,以及二叉树的特殊形式,以帮助读者对树和二叉树有更深入的理解。1.什么是树?树是一种非线性的数据结构,由节点组成,呈......
  • 树和二叉树知识总结
    文章目录树树的定义树的其他表示方法树的基本术语树结构和线性结构的比较二叉树二叉树的定义二叉树的抽象数据类型定义二叉树的性质满二叉树完全二叉树完全二叉树的性质完满二叉树二叉树的存储结构顺序存储结构链式存储结构二叉树的遍历三种遍历方式递归实现非递归实......
  • 在Java项目中使用Redis的五大数据结构应用场景与代码实现
    在Java项目中使用Redis的五大数据结构可以应用于以下场景:1、字符串(String):1、缓存数据:将经常访问的数据存储在Redis中,以减轻数据库的负载。2、计数器:记录用户的访问次数、点赞数等。3、分布式锁:在分布式环境下实现互斥访问,防止并发问题。2、列表(List):1、消息队列:将生产......
  • 深入了解:二叉树(最详细,约10000字)
    目录1.树概念及结构1.1树概念1.2树的表示2.二叉树概念及结构2.1概念2.2数据结构中的二叉树2.3特殊的二叉树2.4二叉树的存储结构2.4.1顺序存储2.4.2链式存储2.5二叉树的性质3.二叉树顺序结构及概念3.1二叉树的顺序结构3.2堆的概念及结构3.3堆的实现4.二叉树......
  • arguments 这种类数组如何遍历
    类数组对象所谓的类数组对象:拥有一个length属性和若干索引属性的对象举个例子:vararray=['name','age','sex'];vararrayLike={0:'name',1:'age',2:'sex',length:3}即便如此,为什么叫做类数组对象呢?那让我们从读写、获取长度、遍......
  • 数据结构/C++:位图 & 布隆过滤器
    数据结构/C++:位图&布隆过滤器位图实现应用布隆过滤器实现应用哈希表通过映射关系,实现了O(1)的复杂度来查找数据。相比于其它数据结构,哈希在实践中是一个非常重要的思想,本博客将介绍哈希思想的两大应用,位图与布隆过滤器。位图看到以下题目:给40亿个无序不重......
  • 数据结构预备知识3--typedef、结构体
    typedef:typedef用来干什么:我们常用typedef来赋予数据类型一个新的名字,来方便我们的使用typedef的用法:typedef 数据类型  新的名字;举例说明: 代码:#include<iostream>usingnamespacestd;intmain(){ typedefintzheng_shu; zheng_shua=1; intb=1;......
  • 数据结构课程设计,用线性表做一个通讯录管理系统
    求一个注释,帮忙解析以下代码#include<iostream>#include<string>#include<cstdlib>#defineMAX2000usingnamespacestd;//通讯录管理系统//设计联系人结构体structPerson{ stringm_Name; intm_Sex; intm_Age; stringm_Phone; stringm_Addr;};//设计......
  • Java 学习路线:基础知识、数据类型、条件语句、函数、循环、异常处理、数据结构、面向
    Java基础什么是JavaJava是一种由SunMicrosystems于1995年首次发布的编程语言和计算平台。Java是一种通用的、基于类的、面向对象的编程语言,旨在减少实现依赖性。它是一个应用程序开发的计算平台。Java快速、安全、可靠,因此在笔记本电脑、数据中心、游戏机、科学超级计......
  • 数据结构(十)哈希表---以题为例
    模拟散列表维护一个集合,支持如下几种操作:Ix,插入一个整数 x;Qx,询问整数 x是否在集合中出现过;现在要进行 N 次操作,对于每个询问操作输出对应的结果。输入格式第一行包含整数 N,表示操作数量。接下来 N 行,每行包含一个操作指令,操作指令为 Ix,Qx 中的一种。输出格......