深入理解树和二叉树的基本概念及其构造(上)
前言:
????????个人主页:Dream_Chaser~ ????????
✨✨专栏:http://t.****.cn/oXkBa
⛳⛳本篇内容:c语言数据结构--树以及二叉树的概念与结构
一.树概念及结构
1.树的概念
树是一种 非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
1.1树与非树
树的特点:
空树 -- 结点数为0的树
非空树:
- 有一个特殊的结点,称为根结点,根节点没有前驱结点(没有父节点)
下面的两点一起理解:
- 除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继
- 因此,树是递归定义的。
可以理解为:
由根节点指向了各子树,子树的双亲节点又可以作为根节点,指向它们的孩子节点
网络异常,图片无法展示|
非树(图)的特点:
1.除了根结点外,每个结点有且仅有一个父结点;
2.子树是不相交的
以下的这个结构是图(允许相交),不是树
注意:树形结构中,子树之间不能有交集,否则就不是树形结构
3.一棵N个结点的树有N-1条边
1.2 关于树的细致概念
下面有个✅的是比较重要的知识点
✅节点的度:一个节点含有的子树的个数称为该节点的度; 如上图:A的为6
✅叶节点或终端节点:度为0的节点称为叶节点; 如上图:B、C、H、I...等节点为叶节点
✅非终端节点或分支节点:度不为0的节点; 如上图:D、E、F、G...等节点为分支节点
✅双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A是B的父节点
✅孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节点
✅兄弟节点:具有相同父节点的节点互称为兄弟节点; 如上图:B、C是兄弟节点
树的度:一棵树中,最大的节点的度称为树的度; 如上图:树的度为6
节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
✅树的高度或深度:树中节点的最大层次; 如上图:树的高度为4
堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:H、I互为兄弟节点
✅节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先
✅子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙
森林:由m(m>0)棵互不相交的树的集合称为森林
对各知识点的进一步画图解析:
- 节点的度:与该节点直接相连的边的数量
- 叶节点(终端节点):度为0的节点
- 分支节点(非终端节点):度不为0的节点
- 父节点(双亲节点):一个节点的直接前驱就是它的父节点
- 子节点(孩子节点):一个节点的直接后继就是它的子节点
- 兄弟节点:由同一个父节点生出来的都是互为兄弟节点
- 树的度:一棵树中,最大的节点的度称为树的度
- 节点的层次:从上往下数,从根开始定义起,根为第1层,根的子节点为第2层,以此类推;(默认是从1开始)
- 树的高度(深度):树中节点的最大层次,下图的高度就是4
- 节点的高度:从下往上数
- 堂兄弟节点:双亲在同一层的节点互为堂兄弟
- 节点的祖先:指从该节点向上追溯到根节点的路径上的所有节点,包括该节点的父节点、父节点的父节点,以此类推,直到达到根节点为止。
- 子孙:从该节点向下追溯到所有末端节点的路径上的所有节点,包括该节点的直接子节点、子节点的子节点,以此类推,直到达到叶子节点为止。
-
森林:是由多个不相交的树组成的集合(并查集)
上一篇: 用Java实现的二叉树详解
推荐阅读
-
Java 类加载器的作用 - 简介:类加载器是 Java™ 中一个非常重要的概念。类加载器负责将 Java 类的字节码加载到 Java 虚拟机中。本文首先详细介绍了 Java 类加载器的基本概念,包括代理模型、加载类的具体过程和线程上下文类加载器等。然后介绍了如何开发自己的类加载器,最后介绍了类加载器在 Web 容器和 OSGi™ 中的应用。 类加载器是 Java 语言的一项创新,也是 Java 语言广受欢迎的重要原因之一。它允许将 Java 类动态加载到 Java 虚拟机中并执行。类加载器从 JDK 1.0 开始出现,最初是为了满足 Java Applets 的需求而开发的,Java Applets 需要从远程位置下载 Java 类文件并在浏览器中执行。现在,类加载器已广泛应用于网络容器和 OSGi。一般来说,Java 应用程序的开发人员不需要直接与类加载器交互;Java 虚拟机的默认行为足以应对大多数情况。但是,如果遇到需要与类加载器交互的情况,而您又不太了解类加载器的机制,就很容易花费大量时间调试异常,如 ClassNotFoundException 和 NoClassDefFoundError。本文将详细介绍 Java 的类加载器,帮助读者深入理解 Java 语言中的这一重要概念。下面先介绍一些基本概念。 类加载器的基本概念 顾名思义,类加载器用于将 Java 类加载到 Java 虚拟机中。一般来说,Java 虚拟机以如下方式使用 Java 类:Java 源程序(.java 文件)经 Java 编译器编译后转换为 Java 字节代码(.class 文件)。类加载器负责读取 Java 字节代码并将其转换为 java.lang 实例。每个实例都用来表示一个 Java 类。通过该实例的 newInstance 方法创建该类的对象。实际情况可能更加复杂,例如,Java 字节代码可能是由工具动态生成或通过网络下载的。 基本上,所有类加载器都是 java.lang.ClassLoader 类的实例。下面将详细介绍这个 Java 类。 java.lang.ClassLoader 类简介 java.lang.ClassLoader 类的基本职责是根据给定类的名称为其查找或生成相应的字节码,然后根据这些字节码定义一个 Java 类,即 java.lang.Class 类的实例。除此之外,ClassLoader 还负责加载 Java 应用程序所需的资源,如图像文件和配置文件。不过,本文只讨论它加载类的功能。为了履行加载类的职责,ClassLoader 提供了许多方法,其中比较重要的方法如表 1 所示。下文将详细介绍这些方法。 表 1.与加载类相关的 ClassLoader 方法
-
理解基础数据库知识:IDEFO模型入门,详解实体、实体型和实体集差异,深入剖析各种函数依赖类型(全、部分、传递、平凡与非平凡),以及关键码(超码、主码、候选码)的基本概念及其区别
-
深入理解数据结构:探索树和二叉树的奥秘
-
深入理解树和二叉树的基本概念及其构造(上)