树,二叉树(完全二叉树,满二叉树)概念图解

目录
  • 1、树的定义
  • 2、树的概念
  • 3、二叉树
  • 4、二叉树遍历
  • 5、满二叉树
  • 6、完全二叉树
  • 总结

1、树的定义

树是n个结点的有限集合,有且仅有一个根结点,其余结点可分为m个根结点的子树

2、树的概念

  1. 结点的度:一个结点拥有子树的个数称为度。比如A的度为3,C的度为2,H的度为0。度为0的结点称为叶子节点(D,F,G,H)。树的度是树中所有结点的度的最大值,此树的度为3。
  2. 树中结点的最大层次成为树的深度或高度。此树的深度为4。
  3. 父节点A的子结点B,C,D;B,C,D也是兄弟节点
  4. 树的集合称为森林.树和森林之间有着密切的关系.删除一个树的根结点,其所有原来的子树都是树,构成森林.用一个结点连接到森林的所有树的根结点就构成树.

3、二叉树

二叉树是每个节点最多拥有两个子节点,左子树和右子树是有顺序的不能任意颠倒。

4、二叉树遍历

前序遍历(前根遍历):——>左——>右

中序遍历(中根遍历):左——>——>右

后序遍历(后根遍历):左——>右——>

已知前序和中序,求后序问题,  前序 ABDGCEFH    中序 DGBAECHF

解法:根据前序、中序综合判断画出树的节点图,然后再写后序遍历:DGBEHFCA

(前序和中序的子树也满足前序或中序的规则)

二叉树的深度优先遍历(DFS)与广度优先遍历(BFS)

DFS深度优先遍历:从根节点出发,沿着左子树方向进行纵向遍历,直到找到叶子节点为止。然后回溯到前一个节点,进行右子树节点的遍历,直到遍历完所有可达节点为止。利用数据结构“栈”,父节点入栈,父节点出栈,先右子节点入栈,后左子节点入栈。递归遍历全部节点。

DFS:ABDGCEFH

BFS广度优先遍历:从根节点出发,在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。利用数据结构“队列”,父节点入队,父节点出队列,先左子节点入队,后右子节点入队。递归遍历全部节点。

BFS:ABCDGEFH

5、满二叉树

高度为h,由2^h-1个节点构成的二叉树称为满二叉树。

6、完全二叉树

完全二叉树是由满二叉树而引出来的,若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数(即1~h-1层为一个满二叉树),第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

堆一般都是用完全二叉树来实现的。

总结

本篇文章就到这里了,希望可以给你带来一些帮助,也希望您能够多多关注我们的更多内容!

(0)

相关推荐

  • java栈实现二叉树的非递归遍历的示例代码

    一般来说遍历二叉树用到递归,但是用Stack进行遍历也是一个不错的方法. 二叉树设置 class Node{ public int val; public Node left; public Node right; public Node(int v) { val=v; left=null; right=null; } } public class Main { public static void main(String[] args) { Node head =new Node(0); No

  • JAVA二叉树的几种遍历(递归,非递归)实现

    首先二叉树是树形结构的一种特殊类型,它符合树形结构的所有特点.本篇博客会针对二叉树来介绍一些树的基本概念,二叉树的基本操作(存储,返回树的深度,节点个数,每一层的节点个数),二叉树的四种遍历(层次,先序,中序,后序) 一.基本概念 二叉树有5种基本形态: 注:二叉树有序树,就是说一个节点的左右节点是有大小之分的,我们通常设定为左孩子一定大于右孩子,下面的实现都是基于这个规则的.二叉树分为三种:满二叉树,完全二叉树,不完全二叉树 二叉树的四种遍历:层次,先序,中序,后序首先是非递归实现上图的满二叉

  • Java二叉树的四种遍历(递归和非递归)

    二叉树的遍历可以分为前序.中序.后序.层次遍历. 前中后是指何时访问中间节点,即前序遍历,遍历节点的顺序为:中->左->右: 中序遍历,遍历节点的顺序为:左->中->右: 后序遍历,遍历节点的顺序为:左->右->中. 前序遍历 递归实现 public void preorder_Traversal(TreeNode root) { if(root==null)return; //访问节点的逻辑代码块 System.out.print(root.val+" &q

  • 图解红黑树及Java进行红黑二叉树遍历的方法

    红黑树 红黑树是一种数据结构与算法课堂上常常提到但又不会细讲的树,也是技术面试中经常被问到的树,然而无论是书上还是网上的资料,通常都比较刻板难以理解,能不能一种比较直观的方式来理解红黑树呢?本文将以图形的方式来解释红黑树的插入与删除操作. 对树结构的学习是一个递进的过程,我们通常所接触的树都是二叉树,二叉树简单来说就是每个非叶子节点都有且只有两个孩子,分别叫做左孩子和右孩子.二叉树中有一类特殊的树叫二叉查找树,二叉查找树是一种有序的树,对于每个非叶子节点,其左子树的值都小于它,其右子树的值都大于

  • 图解二叉树的三种遍历方式及java实现代码

    二叉树(binary tree)是一颗树,其中每个节点都不能有多于两个的儿子. 1.二叉树节点 作为图的特殊形式,二叉树的基本组成单元是节点与边:作为数据结构,其基本的组成实体是二叉树节点(binary tree node),而边则对应于节点之间的相互引用. 如下,给出了二叉树节点的数据结构图示和相关代码: // 定义节点类: private static class BinNode { private Object element; private BinNode lChild;// 定义指向

  • 树,二叉树(完全二叉树,满二叉树)概念图解

    目录 1.树的定义 2.树的概念 3.二叉树 4.二叉树遍历 5.满二叉树 6.完全二叉树 总结 1.树的定义 树是n个结点的有限集合,有且仅有一个根结点,其余结点可分为m个根结点的子树. 2.树的概念 结点的度:一个结点拥有子树的个数称为度.比如A的度为3,C的度为2,H的度为0.度为0的结点称为叶子节点(D,F,G,H).树的度是树中所有结点的度的最大值,此树的度为3. 树中结点的最大层次成为树的深度或高度.此树的深度为4. 父节点A的子结点B,C,D:B,C,D也是兄弟节点 树的集合称为森

  • C语言二叉树与堆的概念与实现

    目录 引言-树的故事 树的基本性质和描述 树的基本特点 树的关键字解析 树的表示方法 二叉树的概念结构 特殊二叉树 二叉树的性质 二叉树的存储结构 二叉树与堆 堆的实现 堆排序 堆的功能实现 TOPK问题 二叉树的结构以及实现 二叉树的遍历 总结 引言-树的故事 在自然界中有很多树 它们是这样的 但是在我们的眼中 他是这样的 显而易见 树的特点就是一对多 ,我们利用这个一对多的特点,可以让我们更好的解决编程中的问题,在树中 ,最基础的二叉树是我们的重点研究对象. 在看一眼神奇的堆排序的动态图 做

  • C语言数据结构系列篇二叉树的概念及满二叉树与完全二叉树

    链接:C语言数据结构系列之树的概念结构和常见表示方法 0x00 概念 定义:二叉树既然叫二叉树,顾名思义即度最大为2的树称为二叉树. 它的度可以为 1 也可以为 0,但是度最大为 2 . 一颗二叉树是节点的一个有限集合,该集合: ① 由一个根节点加上两颗被称为左子树和右子树的二叉树组成 ② 或者为空 观察上图我们可以得出如下结论: ① 二叉树不存在度大于 2 的节点,换言之二叉树最多也只能有两个孩子. ② 二叉树的子树有左右之分,分别为左孩子和右孩子.次序不可颠倒,因此二叉树是有序树. 注意:对

  • C语言详解判断相同树案例分析

    目录 一.题目描述 二.解题思路 题目难度:简单 一.题目描述 给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同. 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的. LeetCode链接:相同的树 二.解题思路 核心思路: 先比较两颗二叉树的根节点 如果「都为空」,则返回 true,说明两树相同. 如果「一个为空一个不为空」,说明这两颗树不相同,则返回 false. 如果「都不为空,但节点值不相同」,说明这两颗树不相同,则返回 false. 经过 1 和

  • Java数据结构最清晰图解二叉树前 中 后序遍历

    目录 一,前言 二,树 ①概念 ②树的基础概念 三,二叉树 ①概念 ②两种特殊的二叉树 ③二叉树的性质 四,二叉树遍历 ①二叉树的遍历 ②前序遍历 ③中序遍历 ④后序遍历 五,完整代码 一,前言 二叉树是数据结构中重要的一部分,它的前中后序遍历始终贯穿我们学习二叉树的过程,所以掌握二叉树三种遍历是十分重要的.本篇主要是图解+代码Debug分析,概念的部分讲非常少,重中之重是图解和代码Debug分析,我可以保证你看完此篇博客对于二叉树的前中后序遍历有一个新的认识!!废话不多说,让我们学起来吧!!

  • 二叉树的概念案例详解

    二叉树简介 关于树的介绍,请参考:https://blog.csdn.net/weixin_43790276/article/details/104033482 一.二叉树简介 二叉树是每个节点最多有两个子树的树结构,是一种特殊的树,如下图,就是一棵二叉树. 二叉树是由n(n>=0)个节点组成的数据集合.当 n=0 时,二叉树中没有节点,称为空二叉树.当 n=1 时,二叉树只有根节点一个节点.当 n>1 时,二叉树的每个节点都最多只能有两个子树,递归地构建成一棵完整的二叉树. 二叉树的两个子树

  • C语言 超详细总结讲解二叉树的概念与使用

    目录 1.二叉树的概念及结构 2.二叉树链式结构的实现 1.二叉树的概念及结构 ①概念:一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成. ②二叉树的特点: 每个结点最多有两棵子树,即二叉树不存在度大于2的结点.(度最多为2) 二叉树的子树有左右之分,其子树的次序不能颠倒. ③现实中的二叉树: 当一名普通的人看到这样一颗树,可能会想:好标准的一棵树 当一个程序猿看到这样一棵树,可能会想:好像数据结构中的二叉树,并且还是颗满二叉树 ④数据结

  • Python 二叉树的概念案例详解

    二叉树简介 关于树的介绍,请参考:https://www.jb51.net/article/222488.htm 一.二叉树简介 二叉树是每个节点最多有两个子树的树结构,是一种特殊的树,如下图,就是一棵二叉树. 二叉树是由n(n>=0)个节点组成的数据集合.当 n=0 时,二叉树中没有节点,称为空二叉树.当 n=1 时,二叉树只有根节点一个节点.当 n>1 时,二叉树的每个节点都最多只能有两个子树,递归地构建成一棵完整的二叉树. 二叉树的两个子树被称为左子树(left subtree)和右子树

  • C语言树与二叉树基础全刨析

    目录 一.树的概念和结构 1.1 树的概念 1.2 树的结构 & 相关名词解释 1.3 树的表示 1.4 树的应用 二.二叉树的概念 & 存储结构(重要) 2.1 二叉树的概念 2.2 特殊的二叉树 2.3 二叉树的性质 2.4 二叉树的存储结构 一.树的概念和结构 1.1 树的概念 树是一种非线性的数据结构,它是由 n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的. 有一个特殊的结点,称为根结点,根节点没有前

  • C语言近万字为你讲透树与二叉树

    目录 一.树概念及结构 1.1 树的概念 1.2 树的相关概念 1.3 树的表示 二.二叉树概念及结构 2.1 概念 2.2 特殊的二叉树: 2.3 二叉树的性质 2.4 二叉树的存储结构 1. 顺序存储 2. 链式存储 三.实现完全二叉树堆并实现堆排序 3.1 堆的概念和结构 3.2 实现堆的难点 3.3 小堆的实现 3.4 堆的应用-堆排序 四.Top-k问题 总结 一.树概念及结构 1.1 树的概念 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫

随机推荐