二叉树的创建及遍历方法

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

目录

1、二叉树的定义及特点

2、满二叉树和完全二叉树的概念

3、二叉树的存储结构

4、创建二叉树

5、树的四种遍历方法

6、结果及其分析


1、二叉树的定义及特点

        二叉树是指树中节点的度不大于2的有序树,它是一种最简单且最重要的树。二叉树的递归定义为:二叉树是一棵空树,或者是一棵由一个根节点和两棵互不相交的,分别称作根的左孩子树和右孩子树组成的非空树;左子树和右孩子树又同样都是二叉树 。    

        二叉树是由m(m>=0)个节点组成的有限集合,二叉树一个节点的子节点应该为n(n<=2),并且二叉树严格区分左孩子和右孩子。        

        二叉树的特点:
                在k层中的最大节点个数为 2^(k-1);
                层数为k的树的最大节点个数为 2^k -1;
                叶节点的个数比度数为2的节点的个数要多1个: n0 = n2+1               

                总节点数为各类节点之和:n=no+n1+n2
                总节点数为所有子节点数加一: n= n + 2*n2+ 1      故得: no=n2+1

二叉树的创建与遍历,链表,数据结构,C++,数据库,前端,算法,链表,数据结构

2、满二叉树和完全二叉树的概念

要实现二叉树的遍历,我们还需要了解什么是满二叉树和完全二叉树:

满二叉树:深度为k (k≥1)时有2k-1个节点的二叉树。


完全二叉树:只有最下面两层有度数小于2的节点,且最下面一层的叶节点集中在最左边的若干位置上。具有n个节点的完全二叉树的深度为
                                        (log2n)+1  或  log2(n+1)

3、二叉树的存储结构

        二叉树的存储方式即可以选择顺序存储,也可以选择链式存储,但考虑到内存占用的问题,大多数情况下我们都采用链式存储,此处我们也采用链式存储进行树的遍历。

二叉树的创建与遍历,链表,数据结构,C++,数据库,前端,算法,链表,数据结构

         如图所示,要实现二叉树的链式存储,我们需要在结构体定义环节对每个节点的左孩子节点和右孩子节点的地址进行保存;因此结构体定义应该如下所示:

typedef char data_t;

typedef struct tree
{
	data_t data;//存放本节点数据
	struct tree *l_child;//存放左孩子节点地址
	struct tree *r_child;//存放右孩子节点地址
}Tree;

4、创建二叉树

        结构体定义完成,接下来我们创建二叉树:

Tree *Create_Tree()
{
	Tree *root;

	char ch;
	scanf("%c", &ch);//通过输入的ch是否为特殊符号来判断该节点是否有孩子节点
	
	if(ch == '#'){	//不存在孩子节点
		return NULL;
	}
	else{
		root = (Tree *)malloc(sizeof(Tree));
		if(NULL == root){
			printf("创建失败\n");
			return NULL;
		}
		
		root->data = ch;
		root->l_child = Create_Tree();//存在左孩子节点,递归调用本函数,使得左孩子节点先被赋值

		root->r_child = Create_Tree();
		
			
		return root;
	}
}

        在这段代码中我们需要来看一下二叉树创建的原理:

        按照一般的存储逻辑,我们一般存储都是按照如下编号逐个存储,但是这样的存储方式不太适用于我们的链式存储,因此,这里我们需要使用到递归存储。

二叉树的创建与遍历,链表,数据结构,C++,数据库,前端,算法,链表,数据结构

 接下来,我们构思一下递归思路:

        要实现递归,首先我们需要思考哪些步骤是重复多次进行的?在这里我们发现,我们每次存储时,基本上都是按照从上到下,从左到右的方式进行存储的,所以,我们此处存储数据时,可以先把根节点下面的左子树先存放完成,再存放右子树即可实现数据存储,并且,我们存放玩上一个数据之后的每一个节点都可以看做是一个根节点。这样,我们的递归思路大致就为:

        1、判断一个根节点是否有孩子,如果有执行下一步,没有返回NULL

        2、创建一个新的节点保存数据

        3、存在左孩子节点,将左孩子节点作为下一个根节点进行操作(递归调用本函数)

        4、左孩子数据存放玩,存在右孩子,将左孩子节点作为下一个根节点进行操作(递归调用本函数)

        通过以上步骤之后,我们的树就建起来啦!!!

5、树的四种遍历方法

        接下来,我们通过三种递归遍历输出我们的结果检查一下:

1、先序遍历(即按照根节点,左孩子树,右孩子树的顺序遍历)

void Preorder_Tree(Tree *root)
{
	if(NULL == root){
		return;
	}
	
	printf("%c ", root->data);//输出当前节点的数据
	Preorder_Tree(root->l_child);//将子节点作为下一个根节点遍历左孩子数
	Preorder_Tree(root->r_child);//将子节点作为下一个根节点遍历左孩子数
}

2、中序遍历(即按照左孩子树,根节点,右孩子树的顺序遍历)

void Mediate_Tree(Tree *root)
{
	if(NULL == root){
		return;
	}
	
	Mediate_Tree(root->l_child);
	printf("%c ", root->data);
	Mediate_Tree(root->r_child);
}

3、后续遍历(即按照左孩子树,右孩子树,根节点的顺序遍历)

void Post_Tree(Tree *root)
{
	if(NULL == root){
		return;
	}
	
	Post_Tree(root->l_child);
	Post_Tree(root->r_child);
	printf("%c ", root->data);
}

4、层次遍历

void Level_Tree(Tree *tree)
{
	if(tree == NULL){
		return;
	}
	
	Tree *pos[N];
	int front, rear;//对头指针和对尾指针,用于出队和入队操作
	
	rear = N;
	while(rear--){
		pos[rear] = NULL;//全部置为空,方便后续判断
	}
	
	front = rear = 1;//此时为空队列,都指向第一个元素
	pos[front] = tree;
	rear++;//对尾指针偏移一位,用于存放新数据
	while(pos[front] != NULL){
		printf("%c ", pos[front]->data);
		if(pos[front]->l_child != NULL){
			pos[rear] = pos[front]->l_child;//左孩子节点入队
			rear++;
		}
		if(pos[front]->r_child != NULL){
			pos[rear] = pos[front]->r_child;//右孩子节点入队
			rear++;//尾指针偏移
		}
		front++;//头指针偏移一位判断下一个元素		
	}		
}

        由于层次遍历涉及队列,逻辑上比较复杂,所以本期暂时不详细解释这段代码,后期会专门出一期层次遍历二叉树的教程,有兴趣的同学可以关注以下。

       

6、结果及其分析

接下来运行结果:

二叉树的创建与遍历,链表,数据结构,C++,数据库,前端,算法,链表,数据结构

二叉树的创建与遍历,链表,数据结构,C++,数据库,前端,算法,链表,数据结构

         我们在输入树的内部数据时,需要使用特殊符号先将树补充为完全二叉树,即所有节点都必须有两个子节点,单个节点也需要补,如上图所示。

        输入数据时从上到下,从左到右,所以依次输入AB#CD###E#FGH##K###

        二叉树的创建与遍历,链表,数据结构,C++,数据库,前端,算法,链表,数据结构

         以上为前三种遍历方法的输出,层次输出的结果则是从最上面一层一直输出到最下面一层,输出结果正确。

        以上就是本期内容,欢迎参考指正,如有不懂,评论出下期!!!

二叉树的创建与遍历,链表,数据结构,C++,数据库,前端,算法,链表,数据结构文章来源地址https://www.toymoban.com/news/detail-782801.html

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

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

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

相关文章

  • 14-数据结构-二叉树的创建以及前中后遍历,以及结点和叶子节点的计算(C语言)

    概述:         二叉树,这里采用孩子链表存储法,即一个数据域和两个左右孩子指针域。随后递归进行遍历即可。在创建二叉树的时候,先创建各个二叉树结点(这里的结点采用动态分配,因此结点为指针变量),随后,再根据逻辑结构图,手动通过左右指针域,链接到对

    2024年02月11日
    浏览(42)
  • 探索树形数据结构,通识树、森林与二叉树的基础知识(专有名词),进一步利用顺序表和链表表示、遍历和线索树形结构

      结点之间有分支,具有层次关系 树的定义 : 树 (tree)是n(n≥0)个有限集。 若n = 0,则称为空树; 若n 0,则它满足如下两个条件: 有且仅有一个特定的称为根(Root)的结点; 其余结点可分为m(m≥0)个互不相交的有限集T1,T2,T3,.....,Tm,其中每一个集合本身又是一棵树,并称为根的

    2024年02月01日
    浏览(47)
  • 【数据结构】二叉树的遍历

      Yan-英杰的主页 悟已往之不谏 知来者之可追    C++程序员,2024届电子信息研究生 目录 前序、中序以及后序遍历 前序遍历 中序遍历 后序遍历                  学习二叉树结构,最简单的方式就是遍历。所谓 二叉树遍历 (Traversal) 是按照某种特定的规则,依次对二叉

    2023年04月23日
    浏览(42)
  • 二叉树的创建与遍历

    {用先序讲解举例,请自己联系中序和后序(在最后):} (在自己作为儿子的同时自己也是根) 注意:递归的形参不是你看到的形参,而是逻辑上的形参! 首先是创建的函数,如果我们要先序输入这样一个二叉树:那么我们在计算机内部其实是要先序输入:ab##c##的,【这里

    2023年04月24日
    浏览(36)
  • 二叉树的创建和遍历

    目录 一.二叉树的创建 1.顺序存储二叉树的创建 2.链式存储二叉树的创建 2.1先序和中序创建二叉树 2.2中序和后序创建二叉树 二.二叉树的递归遍历 1.二叉树的遍历原理 2.中序遍历 3.先序遍历 4.后序遍历 三.二叉树的非递归遍历 1.中序遍历 2.先序遍历 3.后序遍历 方法2:用出栈的

    2024年02月06日
    浏览(46)
  • 数据结构 | 二叉树的各种遍历

    我们本章来实现二叉树的这些功能 Tree.h 我们先来几个简单的 直接手动个创建即可,很简单~~ 这里也是很简单,也可以看做下图这样遍历,或者画一下递归展开图 我们这里看一下递归展开图 为空就返回0 不是空,是叶子,返回1 不是空,也不是叶子,就递归左子树和右子树

    2024年02月04日
    浏览(38)
  • 数据结构与算法-二叉树的遍历

    🌞 “少年没有乌托邦,心向远方自明朗!” 二叉树的遍历是按照一定次序访问二叉树中的所有结点,且每个结点仅被访问一次的过程。遍历线性结构是容易解决的,而二叉树的结构是非线性结构,需要寻找规律,使二叉树的结点排列在一个线性队列上,便于遍历。 由二叉树

    2024年02月08日
    浏览(44)
  • Java数据结构——二叉树的遍历

     作者:敲代码の流川枫 博客主页:流川枫的博客 专栏:和我一起学java 语录:Stay hungry stay foolish 工欲善其事必先利其器,给大家介绍一款超牛的斩获大厂offer利器——牛客网 点击注册和我一起刷题 文章目录 1.创建二叉树 2.二叉树的三种遍历方式 3.代码实现遍历 前序遍历

    2024年01月22日
    浏览(45)
  • go数据结构(二叉树的遍历)

      用数组来存储二叉树如何遍历的呢? 如果父节点的数组下表是i,那么它的左孩子就是i * 2 + 1,右孩子就是 i * 2 + 2。  二叉树的遍历方式: 二叉树有 三种基本遍历方式 ,分别是 前序遍历、中序遍历和后序遍历 。遍历的原理是从根节点开始,按照特定方式递归遍历左子树

    2023年04月15日
    浏览(37)
  • 【数据结构】二叉树的层序遍历

    当我们面对一个树结构时,常常需要对其进行遍历以获取其中的节点信息。其中一种常用的遍历方式是层序遍历,也称为广度优先搜索(BFS)。本篇博客将详细介绍层序遍历的原理和实现方法。 层序遍历以树的根节点开始,按照从上到下、从左到右的顺序逐层遍历树中的节点

    2024年02月03日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包