二叉树的创建与存储,以及遍历

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

树的定义

  • 树是n个节点的集合,在任何一棵非空树中有且仅有一个被称为根的结点,当n>1时,其余结点可以被分为m个互不相交的子集,其中每个子集又是一棵树,称其为根的子树

树的基本术语 

  • 结点:一个数据元素以及若干指向其子树的分支
  • 结点的度:结点所拥有的子树的棵树
  • 树的度:树中各个结点度的最大值
  • 叶子:度为0的结点称为叶子结点,又称为终端结点
  • 分支结点:度不为0的结点,又称为非终端结点
  • 结点的孩子:结点的子树的根称为该结点的孩子,该结点称为孩子结点的双亲
  • 根:没有双亲的结点
  • 结点的层次:从根开始定义,根为第一层,根的孩子所在的层为第二层,根的孩子的孩子所在的层为第三层,以此类推
  • 树的深度:树的叶子结点所在的最大层次
  • 兄弟结点:双亲一样的结点
  • 堂兄弟:双亲位于同一层的结点
  • 结点祖先:从根到该结点所经过的分支上的所有结点均称为该结点的祖先
  • 子孙:某个结点的子树上的所有结点都称为该节点的子孙
  • 有序树:若将树中各结点的各子树看成从左至右是有顺序的不能任意交换位置,则称该树为有序树,否则为无序树
  • 森林:m(m>=0)棵互不相交的树的集合,所以任意一棵树都可以看成是由根和其子树森林所构成的

二叉树的定义

  • 二叉树是n个节点的集合 ,在任何一棵非空二叉树中有且仅有一个被叫做根的节点,若n>1,则其余节点被分成两个互不相交的子集,其中每一个子集又是一棵二叉树,分别称为左子树和右子树,所以二叉树的定义是递归的可以用递归算法来创建一棵二叉树。
  • 满二叉树:除了叶子结点以外其余结点的度全为2的二叉树
  • 完全二叉树:在满二叉树的最后一层上从右至左连续去除若干个叶子结点便得到了一棵完全二叉树。

二叉树的特点

  1. 二叉树中各结点的度小于等于2
  2. 二叉树是有序树
  3. 二叉树的每一层至多有pow(2,n-1)个结点
  4. 深度为k的二叉树至多有pow(2,k)-1个结点
  5.  若二叉树中叶子结点即度为0的结点的个数为n0,度为2的结点的个数为n2,则n0=n2+1
  6. 对于一棵有n个节点的完全二叉树其深度为([log2(n)]+1)
  7. 将完全二叉树从左至右从上至下按层次编号1,2.....则对任意节点i,满足若i=1,则该结点为根节点无双亲,若i>1则i的双亲为[i/2];若2i>n则结点i无左孩子反之结点i的左孩子为2i,若(2i+1 )大于n,则结点i无右孩子反之结点i的右孩子为(2i+1)

二叉树的存储结构

  • 二叉树的顺序存储表示 

对于完全二叉树而言,我们用一组地址连续的存储单元即一维数组依次从上至下从左至右的存储该完全二叉树 中的节点元素,对于普通的二叉树我们将其结点与其对应的完全二叉树相对照,存储在一维数组中,例如:

二叉树的二叉链表的创建,C语言学习历程,数据结构,c语言,算法,程序人生

二叉树的顺序存储的特点

  1. 结点间的关系蕴含在其存储位置中
  2. 浪费空间,适用于存储满二叉树或者完全二叉树 

说明:鉴于顺序存储的二叉树比较简单,读者可以自己尝试定义二叉树的结点,然后将结点存储在一维数组中即可。

 文章来源地址https://www.toymoban.com/news/detail-752790.html

  •  二叉树的链式存储表示

二叉树的结点可以用结构体类型来表示,定义不同的结点结构,可以构成不同的链式存储结构。

二叉链表:存储该二叉树的链表的结点的指针域有两个,分别指向该节点的左右孩子结点

三叉链表: 存储该二叉树的链表的结点的指针域有三个,分别指向左孩子结点,双亲结点,以及右孩子结点

  • 二叉树的三种遍历方法
  1. 先序遍历:先访问根节点,再访问左子树和右子树,对左子树和右子树的访问也遵循根左右的原则
  2. 中序遍历:先访问左子树,再访问根节点,最后访问右子树,对左子树和右子树的访问也遵循左根右的原则
  3. 后序遍历:先访问左子树,再访问右子树,最后访问根节点,对左子树和右子树的访问也遵循左右根的顺序 

由以上定义可知对二叉树的三种遍历方法都是递归的所以设计遍历方法时需要用到递归 

下面演示用二叉链表来表示如图所示的二叉树,以及采用三种遍历方法遍历该二叉树的过程,在程序代码中给出了完整的注释:

二叉树的二叉链表的创建,C语言学习历程,数据结构,c语言,算法,程序人生

 

  1. 第一步定义二叉树的结点,用结构体类型来定义节点结构
    typedef struct BitNode
    {
    	char value;                                              //数据域,用于存放该节点的值
    	struct BitNode* lchild, * rchild;                              //二叉链表的节点中有两个指针与分别指向该节点的左右孩子节点
    	
    
    }BitNode,*Bitree;       //为定义的结构体类型起别名为BitNode,以及为该结构体类型的指针起别名为Bitree,此时执行语句"BitNode a"相当于执行语句"struct BitNode a",执行语句"Bitree a"相当于执行语句"BitNode *a"
  2.  第二步创建该二叉树

    Bitree CreateTree(Bitree head)
    {
    	char value;
    	Bitree p;
    	//p = head = NULL;           //相当于每次调用该函数都会把头指针设置为空指针;这显然是错误的
    
    	printf("请输入节点的值\n");
    	scanf("%c", &value);
    	getchar();
    
    	if (value == '#')
    		return NULL;                         //创建二叉树,当输入#号时表示不再继续输入返回空指针给上一级调用对象,即将上一级节点没有左孩子或者没有右孩子,理解这一点很重要,函数的返回值是所定义的结构体类型的指针
    	else
    	{
    
    		p = (Bitree)malloc(sizeof(BitNode));
    		p->value = value;
    		if (!head)
    			head = p;          //创建头指针;
    
    		printf("请输入%c的左子树的根节点\n", value);
    		p->lchild = CreateTree(head);           //递归创建左子树;
    		printf("请输入%c的右子树的根节点\n", value);
    		p->rchild = CreateTree(head);           //递归创建右子树;
    
    		return p;              //函数出口返回的是指向创建的二叉树的第一个结点的指针;
    
    	}
    }
  3. 先序遍历该二叉树

    void FirstOrderTraverse(Bitree p)
    {
    	if (p == NULL)
    		return;
    	printf("%c\t", p->value);
    	FirstOrderTraverse(p->lchild);
    	FirstOrderTraverse(p->rchild);
    
    
    }
  4. 中序遍历该二叉树

    void MiddleOrderTraverse(Bitree p)
    {
    	if (p == NULL)
    		return;
    	MiddleOrderTraverse(p->lchild);
    	printf("%c\t", p->value);
    	MiddleOrderTraverse(p->rchild);
    
    
    }
    
  5. 后序遍历该二叉树

    void PostOrderTraverse(Bitree p)                        //后序遍历二叉树即最后访问根节点
    {
    	if (p == NULL)
    		return;
    
    	PostOrderTraverse(p->lchild);                         //此递归函数都没有递归结束条件,怎么从递归中出来呢?递归结束条件怎么能不写
    	PostOrderTraverse(p->rchild);
    	printf("%c\t", p->value);
    }
    
    
    

程序完整代码以及运行结果截图:

代码:

//二叉树的定义与储存,用二叉链表存储二叉树


#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>            //该头文件包含了malloc函数的声明;

//定义二叉树的节点结构,采用二叉链表存储该二叉树
typedef struct BitNode
{
	char value;                                              //数据域,用于存放该节点的值
	struct BitNode* lchild, * rchild;                              //二叉链表的节点中有两个指针与分别指向该节点的左右孩子节点


}BitNode, * Bitree;//为定义的结构体类型起别名为BitNode,
//以及为该结构体类型的指针起别名为Bitree,此时执行语句"BitNode a"相当于执行语句"struct BitNode a",执行语句"Bitree a"相当于执行语句"BitNode *a"


//创建一棵不带头节点的二叉树的函数
Bitree CreateTree(Bitree head);
//后序遍历一棵树 
void FirstOrderTraverse(Bitree p);
void MiddleOrderTraverse(Bitree p);
void PostOrderTraverse(Bitree p);



int main()
{
	Bitree head = NULL,p;
	head = CreateTree(head);
	if (head)
		printf("树创建成功\n");
	else
		printf("树创建失败\n\n\n");

	printf("先序遍历该树的结果\n");
	FirstOrderTraverse(head);
	printf("\n");

	printf("中序遍历该树的结果\n");
	MiddleOrderTraverse(head);
	printf("\n");

	printf("后序遍历该树的结果\n");
	PostOrderTraverse(head);
	printf("\n");


	return 0;

}

//函数实现,按照中序遍历的思想创建该二叉树,即先创建根节点再创建根节点的左子树和右子树,根据此思想创建二叉树可以用到递归算法
Bitree CreateTree(Bitree head)
{
	char value;
	Bitree p;
	//p = head = NULL;           //相当于每次调用该函数都会把头指针设置为空指针;这显然是错误的

	printf("请输入节点的值\n");
	scanf("%c", &value);
	getchar();

	if (value == '#')
		return NULL;                         //创建二叉树,当输入#号时表示不再继续输入返回空指针给上一级调用对象,即将上一级节点没有左孩子或者没有右孩子,理解这一点很重要,函数的返回值是所定义的结构体类型的指针
	else
	{

		p = (Bitree)malloc(sizeof(BitNode));
		p->value = value;
		if (!head)
			head = p;          //创建头指针;

		printf("请输入%c的左子树的根节点\n", value);
		p->lchild = CreateTree(head);           //递归创建左子树;
		printf("请输入%c的右子树的根节点\n", value);
		p->rchild = CreateTree(head);           //递归创建右子树;

		return p;              //函数出口返回的是指向创建的二叉树的第一个结点的指针;

	}
}


void FirstOrderTraverse(Bitree p)
{
	if (p == NULL)
		return;
	printf("%c\t", p->value);
	FirstOrderTraverse(p->lchild);
	FirstOrderTraverse(p->rchild);


}


void MiddleOrderTraverse(Bitree p)
{
	if (p == NULL)
		return;
	MiddleOrderTraverse(p->lchild);
	printf("%c\t", p->value);
	MiddleOrderTraverse(p->rchild);


}




void PostOrderTraverse(Bitree p)                        //后序遍历二叉树即最后访问根节点
{
	if (p == NULL)
		return;

	PostOrderTraverse(p->lchild);                         //此递归函数都没有递归结束条件,怎么从递归中出来呢?递归结束条件怎么能不写
	PostOrderTraverse(p->rchild);
	printf("%c\t", p->value);
}


运行结果截图

二叉树的二叉链表的创建,C语言学习历程,数据结构,c语言,算法,程序人生

 

 

 

 

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

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

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

相关文章

  • 【数据结构】16 二叉树的定义,性质,存储结构(以及先序、后序、中序遍历)

    一个二叉树是一个有穷的结点集合。 它是由根节点和称为其左子树和右子树的两个不相交的二叉树组成的。 二叉树可具有以下5种形态。 一个二叉树第i层的最大结点数为 2 i − 1 2^{i-1} 2 i − 1 , i ≥ 1 i geq 1 i ≥ 1 每层最大结点可以对应完美二叉树(满二叉树),其所有分支结

    2024年02月20日
    浏览(45)
  • 14-数据结构-二叉树的创建以及前中后遍历,以及结点和叶子节点的计算(C语言)

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

    2024年02月11日
    浏览(45)
  • 树与二叉树的存储与遍历

    如前面的顺序表,链表,栈和队列都是线性的数据结构,树是非线性的结构。树可以有n个结点,n=0,当n=0是就表示树为空 n0,代表树不为空,不为空的树,它只有一个根结点,然后其余的结点又是构成互不相交的树,然后这些树本身又是一棵树,这些树且为根节点的子树。 任何

    2023年04月16日
    浏览(37)
  • 二叉树的存储方式、遍历、构建、判定

    目录 树的定义 二叉树的定义 二叉树的存储表示 二叉树的创建和前中后序遍历 通过中序遍历和先序遍历来构建树 通过后序遍历加先序遍历构建树 链式存储的树 将其中序遍历 非递归后序遍历 非递归后序遍历第二种方法 非递归中序遍历 非递归前序遍历 层次遍历 求二叉树节

    2024年02月05日
    浏览(38)
  • 二叉树的创建和遍历

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

    2024年02月06日
    浏览(47)
  • 二叉树的创建与遍历

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

    2023年04月24日
    浏览(40)
  • 二叉树的创建及遍历方法

    目录 1、二叉树的定义及特点 2、满二叉树和完全二叉树的概念 3、二叉树的存储结构 4、创建二叉树 5、树的四种遍历方法 6、结果及其分析         二叉树是指树中节点的度不大于2的有序树,它是一种最简单且最重要的树。二叉树的递归定义为:二叉树是一棵空树,或者

    2024年02月02日
    浏览(44)
  • 二叉树OJ题进阶(二叉树层序遍历、根据二叉树创建字符串、判断完全二叉树、二叉树的构建及遍历、二叉树的最近公共祖先(2种))

    1.思路 用队列写: 1.从上到下,从左到右的顺序 2.非递归的方法:使用队列来完成 3.cur充当根结点,当cur不为空的时候,cur进入队列,队列不为空,cur弹出队列打印 4.如果cur的左边不为空,左边进队,右边不为空,右边进队 5.此时队列不为空,弹出队头(也就是cur的左边)打

    2024年02月05日
    浏览(39)
  • 数据结构:图文详解 树与二叉树(树与二叉树的概念和性质,存储,遍历)

    目录 一.树的概念 二.树中重要的概念 三.二叉树的概念 满二叉树 完全二叉树 四.二叉树的性质 五.二叉树的存储 六.二叉树的遍历 前序遍历 中序遍历  后序遍历  树是一种 非线性数据结构 ,它由节点和边组成。树的每个节点可以有零个或多个子节点,其中一个节点被指定为

    2024年02月04日
    浏览(49)
  • C语言二叉树的创建与遍历

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

    2024年02月05日
    浏览(38)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包