【Java数据结构】二叉树到底是什么品种的树?以及二叉树有哪些基操(一)

简介: 笔记

树型结构


概念

1.png

树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:


有一个特殊的节点,称为根节点,根节点没有前驱节点

除根节点外,其余节点被分成M(M > 0)个互不相交的集合T1、T2、…、Tm,其中每一个集合 Ti (1 <= i

<= m) 又是一棵与树类似的子树。每棵子树的根节点有且只有一个前驱,可以有0个或多个后继

树是递归定义的。2.png3.png


节点的度: 一个节点含有的子树的个数称为该节点的度;


树的度: 一棵树中,最大的节点的度称为树的度;


叶子节点或终端节点: 度为0的节点称为叶节点;


双亲节点或父节点: 若一个节点含有子节点,则这个节点称为其子节点的父节点;


孩子节点或子节点: 一个节点含有的子树的根节点称为该节点的子节点;


根结点: 一棵树中,没有双亲结点的结点;


节点的层次: 从根开始定义起,根为第1层,根的子节点为第2层,以此类推;


4.png


树的高度或深度: 树中节点的最大层次;


非终端节点或分支节点: 度不为0的节点;


兄弟节点: 具有相同父节点的节点互称为兄弟节点;


堂兄弟节点: 双亲在同一层的节点互为堂兄弟;


节点的祖先: 从根到该节点所经分支上的所有节点;


子孙: 以某节点为根的子树中任一节点都称为该节点的子孙。


森林: 由m(m>=0)棵互不相交的树的集合称为森林


树的表示形式


树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,实际中树有很多种表示方式,如:双亲表示法,孩子表示法、孩子兄弟表示法等等

这里就简单的了解其中最常用的孩子兄弟表示法。

class Node {
 int value; // 树中存储的数据
 Node firstChild; // 第一个孩子引用
 Node nextBrother; // 下一个兄弟引用
}

5.png


树的应用


  • 文件系统管理(目录和文件)等

6.png


二叉树(重头戏)


概念

7.png


一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。


二叉树的特点:

  1. 每个结点最多有两棵子树,即二叉树不存在度大于 2 的结点
  2. 二叉树的子树有左右之分,其子树的次序不能颠倒,因此二叉树是有序树。


二叉树的基本形态

8.png


上图给出了几种特殊的二叉树形态,从左往右依次是:

空树、只有根节点的二叉树、节点只有左子树、节点只有右子树、节点的左右子树均存在

一般二叉树都是由上述基本形态结合而形成的。


两种特殊的二叉树:

满二叉树: 一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是2^k-1 ,则它就是满二叉树。

完全二叉树: 完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

9.png



二叉树的性质


若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2^(i-1) (i>0)个结点

若规定只有根节点的二叉树的深度为1,则深度为K的二叉树的最大结点数是2^k -1 (k>=0)

对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0=n2+1

具有n个结点的完全二叉树的深度k为log2(n+1) 向上取整

对于具有n个结点的完全二叉树,如果按照从上至下从左至右的顺序对所有节点从0开始编号,则对于序号为i的结点有:

①若i>0,双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点

②若2i+1<n,左孩子序号:2i+1,否则无左孩子

③若2i+2<n,右孩子序号:2i+2,否则无右孩子

比如一道例题: 假设一棵完全二叉树中总共有1000个节点,则该二叉树中__500__ 个叶子节点,__ 500___ 个非叶子节点 , __ 1 __ 个节点只有左孩子 ,__0__个只有右孩子。

问题解析:


总共有多少层?k=log2(1000+1) =10层

如果是10层,那么放满也就是满二叉树,总共2^10-1 = 1023个节点,但是现在只有1000个,那么说明当前这个树,不是满二叉树

第10层肯定是没放满的!!!

说明第9层肯定放满了

那前9层共有多少个节点呢?2^9-1 = 511个

所以第10层有1000-511=489个节点,都是叶子节点

现在就要考虑一个问题,第10层的节点是由多少个第9层节点产生的?489/2=244.5取245个

第9层这一层有多少个节点?2^(9-1) = 256个

所以第9层有245个节点是有孩子的,其中有1个节点只有一个左孩子,所以第9层的叶子节点有256-245=11个,第9层第10层的叶子节点共有11+489 =500个




相关文章
|
2月前
|
算法
数据结构之博弈树搜索(深度优先搜索)
本文介绍了使用深度优先搜索(DFS)算法在二叉树中执行遍历及构建链表的过程。首先定义了二叉树节点`TreeNode`和链表节点`ListNode`的结构体。通过递归函数`dfs`实现了二叉树的深度优先遍历,按预序(根、左、右)输出节点值。接着,通过`buildLinkedList`函数根据DFS遍历的顺序构建了一个单链表,展示了如何将树结构转换为线性结构。最后,讨论了此算法的优点,如实现简单和内存效率高,同时也指出了潜在的内存管理问题,并分析了算法的时间复杂度。
66 0
|
9天前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
45 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
9天前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
35 12
|
9天前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
33 10
|
9天前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
32 2
|
23天前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
1月前
|
存储 缓存 安全
Java 集合江湖:底层数据结构的大揭秘!
小米是一位热爱技术分享的程序员,本文详细解析了Java面试中常见的List、Set、Map的区别。不仅介绍了它们的基本特性和实现类,还深入探讨了各自的使用场景和面试技巧,帮助读者更好地理解和应对相关问题。
48 5
|
2月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
86 5
|
2月前
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法,包括先序、中序、后序的递归与非递归遍历方法。通过编程实践,加深对二叉树结构的理解,学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
111 4
|
2月前
|
算法
数据结构之文件系统模拟(树数据结构)
本文介绍了文件系统模拟及其核心概念,包括树状数据结构、节点结构、文件系统类和相关操作。通过构建虚拟环境,模拟文件的创建、删除、移动、搜索等操作,展示了文件系统的基本功能和性能。代码示例演示了这些操作的具体实现,包括文件和目录的创建、移动和删除。文章还讨论了该算法的优势和局限性,如灵活性高但节点移除效率低等问题。
73 0