当前位置: 首页 > news >正文

【Java数据结构】树】

【Java数据结构】树

  • 一、树型结构
      • 1.1 概念
      • 1.2 特点
      • 1.3 树的类型
      • 1.4 树的遍历方式
      • 1.5 树的表示形式
        • 1.5.1 双亲表示法
        • 1.5.2 孩子表示法
        • 1.5.3 孩子双亲表示法
        • 1.5.4 孩子兄弟表示法
  • 二、树型概念(重点)

此篇博客希望对你有所帮助(帮助你了解树(为下篇博客二叉树奠定基础)),不懂的或有错误的也可在评论区留言,错误必改评论必回!!!持续关注,下一篇博客是二叉树!!!

一、树型结构

1.1 概念

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

在这里插入图片描述

1.2 特点

  • 有一个特殊的结点,称为根结点,根节点是没有前驱。(没有父结点)。
  • 除了结点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、…、Tm,其中每个集合又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱(父结点),可以有0或多个后继(子结点)。
  • 树是递归定义。
  • 树型结构中,子树之间不能有交集,否则就不是树型结构。

在这里插入图片描述

1.3 树的类型

  1. 二叉树(Binary Tree):每个节点最多有两个子节点,通常称为左子节点和右子节点。
  • 满二叉树(Full Binary Tree):除了叶子节点外,每个节点都有两个子节点。
  • 完全二叉树(Complete Binary Tree):所有层(除了最后一层)都是满的,并且最后一层的节点从左到右连续填充。
  • 平衡二叉树(Balanced Binary Tree):每个节点的两个子树的高度差不超过1。
  1. 二叉搜索树(Binary Search Tree, BST):满足以下性质的二叉树:对于每个节点,其左子树中所有节点的值都小于该节点的值,其右子树中所有节点的值都大于该节点的值。
  2. B树(B-Tree):一种自平衡的树,广泛用于数据库和文件系统中,可以容纳多个值的节点。
  3. List item红黑树(Red-Black Tree):一种自平衡的二叉搜索树,具有严格的平衡要求,每个节点都有一个表示颜色的位(红或黑)。
  4. Trie树(Trie 或 Prefix Tree):一种用于存储字符串集合的树结构,主要用于字典和前缀匹配。

1.4 树的遍历方式

遍历是访问树中所有节点的过程,主要有以下几种方式:

  • 前序遍历(Preorder Traversal):根节点 -> 左子树 -> 右子树
  • 中序遍历(Inorder Traversal):左子树 -> 根节点 -> 右子树(对于二叉搜索树,这是升序访问所有节点的方式)
  • 后序遍历(Postorder Traversal):左子树 -> 右子树 -> 根节点
  • 层次遍历(Level Order Traversal):按层次从上到下、从左到右访问节点(通常使用队列实现)。

举例:
在这里插入图片描述
前序遍历:A B C D E F
中序遍历:C B D A E F
后序遍历 :C D B F E A
层次遍历 :A B E C D F

1.5 树的表示形式

表示形式:双亲表示法孩子表示法孩子双亲表示法孩子兄弟表示法等等。

1.5.1 双亲表示法

双亲表示法使用一个数组来存储树的节点,其中每个节点包含一个数据域和一个指向其父节点的指针(或索引)。

class TreeNodeParent {  int data; // 节点数据  int parent; // 父节点索引TreeNodeParent(int data, int parent) {  this.data = data;  this.parent = parent;  }  
} 
1.5.2 孩子表示法

孩子表示法使用一个数组来存储树的节点,并为每个节点维护一个链表,链表中的元素是该节点的所有孩子节点。

class TreeNodeChild {  int data; // 节点数据  List<TreeNodeChild> children; // 孩子节点列表  TreeNodeChild(int data) {  this.data = data;  this.children = new LinkedList<>();  }  
}  
1.5.3 孩子双亲表示法

孩子双亲表示法结合了双亲表示法和孩子表示法,每个节点既包含指向其父节点的指针(或索引),又包含指向其孩子节点的链表。

class TreeNodeChildParent {  int data; // 节点数据  int parent; // 父节点索引(若为-1,则表示该节点为根节点)  List<TreeNodeChildParent> children; // 孩子节点列表  TreeNodeChildParent(int data, int parent) {  this.data = data;  this.parent = parent;  this.children = new LinkedList<>();  }  
}  
1.5.4 孩子兄弟表示法

孩子兄弟表示法使用两个指针(或索引),分别指向节点的第一个孩子节点和右兄弟节点。这种方法可以方便地表示任意树结构。

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

二、树型概念(重点)

  • 结点的度:一个结点含有子树的个数称为该结点的度;
  • 树的度:一棵树中,所有结点度的最大值称为树的度;
  • 叶子结点或终端结点:度为0的结点称为叶结点;
  • 双亲结点或父结点:若一个结点含有子结点,则这个结点称为其子结点的父结点;
  • 孩子结点或子结点:一个结点含有的子树的根结点称为该结点的子结点;
  • 根结点:一棵树中,没有双亲结点的结点;
  • 结点的层次:从根开始定义起,根为第1层,根的子结点为第2层,以此类推;
  • 树的高度或深度:树中结点的最大层次;
  • 非终端结点或分支结点:度不为0的结点;
  • 兄弟结点:具有相同父结点的结点互称为兄弟结点;
  • 堂兄弟结点:双亲在同一层的结点互为堂兄弟;
  • 结点的祖先:从根到该结点所经分支上的所有结点;
  • 子孙:以某结点为根的子树中任一结点都称为该结点的子孙;
  • 森林:由m(m>=0)棵互不相交的树组成的集合称为森林。

http://www.mrgr.cn/news/61529.html

相关文章:

  • Linux基础—基础命令及相关知识5(ubuntu网络配置)
  • docker中使用ros2humble的rviz2不显示问题
  • 【JavaEE】【多线程】定时器
  • 基于边缘计算的智能门禁系统架构设计分析
  • 【小脚本】合并两个pdf
  • Jmeter实际应用
  • 基于SSM积分商城管理系统的设计与实现(源码+lw+部署文档+讲解等)
  • 小红书图文无水印下载
  • 进一步认识ICMP协议
  • MySQL用户权限管理属于SQL语句中的DCL语句
  • 深入理解阻塞队列
  • 鸿蒙生态崛起:开发者的机遇与挑战
  • 数据结构————map,set详解
  • Rust实现Kafka - 前言
  • 18 Docker容器集群网络架构:一、etcd 概述
  • windows 驱动实例分析系列: NDIS 6.0的Filter 驱动改造(一)
  • Ubuntu下搭建自己的Docker镜像仓库
  • svg + canvas + 烟花 + 0.0
  • 记录一次更新idea
  • 记录工作上一次计算的优化
  • 基于JSP的篮球系列网上商城系统【附源码】
  • 图的最短路径算法-迪杰斯特拉(Dijkstra)算法与弗洛伊德(Frolyd)算法(更新中)
  • Git提交代码完整流程
  • 基于SSM+小程序的购物管理系统1
  • Redis-README官方入门文档
  • 深度学习数学基础之链式法则