二叉树的基础概念及遍历

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

二叉树(Binary Tree)的基础

1、树的概念

1、树的概念

树是一种非线性的数据结构,是由n(n>=0)个有限结点组成一个具有层次关系的集合,将它称为树,是因为在形状上像一颗倒着的树,如下图所示就是一颗二叉树。
二叉树的基础概念及遍历,数据结构,java
可以发现,对于树中的根节点,没有前驱节点,有多个后驱节点;对于其他节点,有一个前驱节点,有或没有后驱节点。这就是它属于非线性结构的原因,节点的对应关系是一对多并且子树之间不相交,可以用此特点来判断树与非树。

2、树元素的基本概念

结点的度:一个结点含有子树的个数称为该结点的度
树的度:一棵树中,所有结点度的最大值称为树的度
叶子结点或终端结点:度为0的结点称为叶结点
双亲结点或父结点:若一个结点含有子结点,则这个结点称为其子结点的父结点;
孩子结点或子结点:一个结点含有的子树的根结点称为该结点的子结点
根结点:一棵树中,没有双亲结点的结点
树的高度或深度:树中结点的最大层次

3、树的表示形式

我们可以发现,如果要构建出这个结点,必须要有三部分:结点的值、结点的左孩子引用、结点的右孩子引用。我们可以借助类来实现结点的实例化。

class TreeNode {
	public int val;//结点的值
	public TreeNode left;//结点的左孩子引用
	public TreeNode right;//结点的右孩子引用
}

2、二叉树

1、二叉树的概念

一棵二叉树是结点的一个有限集合,该集合:

  1. 或者为空
  2. 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成
    二叉树的基础概念及遍历,数据结构,java

从二叉树的概念中我们可以发现:

  1. 二叉树不存在度大于2的结点
  2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

2、特殊的二叉树

1、满二叉树:每层的结点数都达到最大值的二叉树,结点总数为2^k-1
2. 完全二叉树:从左到右,从上到下给二叉树的结点编号遍历,如果二叉树在遇到空结点之后的结点都为空,就是完全二叉树。满二叉树是完全二叉树的一种特例。
二叉树的基础概念及遍历,数据结构,java

3、二叉树的性质

  1. 若规定根结点的层数为1,则一棵非空二叉树的第i层上最多有 (i>0)个结点
  2. 若规定只有根结点的二叉树的深度为1,则深度为K的二叉树的最大结点数是 (k>=0)
  3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0=n2+1
  4. 具有n个结点的完全二叉树的深度k为 log2(n+1)上取整
  5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的顺序对所有节点从0开始编号,则对于序号为i的结点有:
    若i>0,双亲序号:(i-1)/2;i=0,i为根结点编号,无双亲结点
    若2i+1<n,左孩子序号:2i+1,否则无左孩子
    若2i+2<n,右孩子序号:2i+2,否则无右孩子

4、二叉树的遍历

二叉树的遍历常常采用递归解决,原因是每一个结点的结构相同,处理每一个结点的方式相同,因此可以使用递归来解决重复的子问题。

1、前序遍历

前序遍历的顺序为根节点-左孩子结点-右孩子结点。其中对于左孩子结点也使用相同的遍历顺序,直到遇见空结点为止。利用下图进行举例。
#表示空结点二叉树的基础概念及遍历,数据结构,java
A-B-D-#,遇到空结点,递进过程结束,回归开始。回到D向右树继续递进,D-#,遇到空结点,递进过程结束,回归开始。回到B向右树继续递进,B-#,遇到空结点,递进过程结束,回归开始。回到A向右树继续递进…
所以前序遍历的结果为:ABDCE

2、中序遍历

中序遍历的顺序为左孩子结点-根节点-右孩子结点二叉树的基础概念及遍历,数据结构,java
对于A,先遍历B,对于B先遍历D,D-B-A;对于C,先遍历E,A-E-C
所以中序遍历的结果为:DBAEC

3、后序遍历

后序遍历的顺序为左孩子结点-右孩子结点-根节点
二叉树的基础概念及遍历,数据结构,java
对于A,先遍历B,对于B,先遍历D,D-B;再遍历C,对于C,先遍历E,E-C
所以后序遍历的结果为:DBECA

三种遍历代码实现(递归)

//前序遍历
public void preOrder(TreeNode root) {
	if(root==null) {
		return;
	}
	System.out.print(root.val+" ");
	preOrder(root.left);
	preOrder(root.right);
}
//中序遍历
public void inOrder(TreeNode root) {
	if(root==null) {
		return;
	}
	inOrder(root.left);
	System.out.print(root.val+" ");
	inOrder(root.right);
}
//后序遍历
public void postOrder(TreeNode root) {
	if(root==null) {
		return;
	}
	postOrder(root.left);
	postOrder(root.right);
	System.out.print(root.val+" ");
}

三种递归方式实质上都是利用了子问题的思想,将左右孩子拆出来作为新的树,利用同样的方式处理,十分容易理解。文章来源地址https://www.toymoban.com/news/detail-807837.html

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

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

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

相关文章

  • 【数据结构】树和二叉树的概念及结构(一)

    目录 一,树的概念及结构         1,树的定义         2,树结点的分类及关系         3,树的表示 二,二叉树的概念及结构         1,二叉树的定义         2,特殊的二叉树         3,二叉树的性质         4,二叉树的存储结构 1,顺序存储

    2024年02月10日
    浏览(45)
  • 数据结构——二叉树的基本概念及顺序存储(堆)

    目录 一.前言 二.树概念及结构 2.1 树的概念 2.2 树的相关概念 2.3 树的表现 2.4 树在实际中的应用(表示文件系统的目录树结构) 三.二叉树的概念及结构 3.1 概念 3.2 特殊的二叉树 3.3 二叉树的性质 3.4 二叉树的存储结构 3.4.1 顺序存储 3.4.2 链式存储 四.二叉树顺序结构及实现

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

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

    2023年04月23日
    浏览(45)
  • 数据结构 | 二叉树的各种遍历

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

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

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

    2024年01月22日
    浏览(49)
  • 【数据结构】二叉树的三种遍历

    目录 一、数据结构 二、二叉树 三、如何遍历二叉树 数据结构是计算机科学中用于组织和存储数据的方式。它定义了数据元素之间的关系以及对数据元素的操作。常见的数据结构包括数组、链表、栈、队列、树、图等。 数组是一种线性数据结构,它使用连续的内存空间存储

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

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

    2024年02月08日
    浏览(46)
  • 数据结构——二叉树的遍历与应用

    目录 一.前言 二. 二叉树链式结构的实现 2.1 前置说明 2.2 二叉树的遍历 2.2.1 前序、中序以及后序遍历 前序遍历: 中序遍历递归图: 后序遍历: 2.3节点个数 2.4叶子节点个数 2.5第K层的节点个数 2.6 二叉树查找值为x的节点 2.7 二叉树的销毁 三.结语   大家好久不见,放寒假了咱

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

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

    2024年02月03日
    浏览(46)
  • go数据结构(二叉树的遍历)

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

    2023年04月15日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包