【数据结构】二叉树的遍历
二叉树的遍历
遍历是数据结构中的常见操作(访问数据结构中的所有元素)。
线性数据结构的遍历比较简单,正序遍历或逆序遍历。而对于二叉树来讲,根据节点访问顺序的不同,可以分为四种:
前序遍历(Preorder Traversal)
中序遍历(Inorder Traversal)
后序遍历(Postorder Traversal)
层序遍历(Level Order Traversal)
下面我们来看看他们的特点。
前序遍历(Pre-Order Traversal)
前序遍历二叉树,就是先访问根结点(中间节点),再前序遍历左子树,最后前序遍历右子树。
如上图:
我们再回想一下,前序遍历的访问顺序是什么?首先根节点肯定是最先被访问,然后是左子树,最后才是右子树。
因此在上图中,前序遍历的访问顺序如下:
访问根节点 F
访问左子树 B
访问左子节点 A
访问右子节点 D
访问左子节点 C
访问右子节点 E
访问右子树 G
访问右子节点 I
访问左子节点 H
前序遍历的顺序是 [F]->[B]->[A]->[D]->[C]->[E]-& ...
【工具类】打印二叉树
打印二叉树
介绍
二叉树是一种重要的数据结构,在编写程序时,经常需要以可读性较强的方式打印二叉树结构,以便更好地理解和调试代码。
本节将介绍一个简单而有效的二叉树打印工具,以及如何使用该工具。
使用效果
123456789101112131415public class Main { public static void main(String[] args) { BinarySerchTree<Integer> bst = new BinarySerchTree<>(); // 自己写的一个二叉搜索树 // 添加若干节点 bst.add(new Integer(15)); bst.add(new Integer(7)); bst.add(new Integer(26)); bst.add(new Integer(13)); bst.add(new Integer(40)); bst.add(new Integer(3)); bst.add(new Integer(19)); // 调用打印方法 bst.printTre ...
【设计模式】工厂方法模式(Factory Method)
上一节我们学了类间关系以及UML类图,现在我们来看看工厂方法模式。
工厂
在面向对象程序设计中,工厂是一个用来创建其他对象的对象。它提供了一种抽象的构造方法,用于实现不同的对象创建方案。工厂对象通常包含一个或多个方法,这些方法用于创建工厂所能生成的不同类别的对象。这些方法可能会接收参数,以指定对象创建的方式,并最终返回创建的对象。
当对象的创建涉及到复杂的控制过程、配置或其他操作时,工厂对象可以负责将这些细节封装起来,使客户端代码保持简洁,专注于业务逻辑。
不同的设计模式,如工厂方法模式、抽象工厂模式、生成器模式、单例模式等,都应用了工厂的概念。这些模式通过不同的方式组织和实现工厂,以满足不同的设计需求,提高代码的可维护性和可复用性。
工厂方法模式
工厂方法模式(Factory method pattern)是一种实现了 “工厂” 概念的面向对象设计模式,属于创建型模式。工厂方法模式用于处理在不指定对象具体类别的情况下创建对象的问题。
模式意图:定义一个创建对象的接口,但让实现这个接口的具体类来决定实例化哪些类。工厂方法让类的实例化推迟到子类中进行。
类图 | 结构与角色分析
先看 ...
【数据结构】树与二叉树
树
概述
树(tree)是一种抽象数据类型(ADT),或者说是一种用于模拟具有树状结构性质的非线性数据结构。
它是由n(n>0)个有限节点组成一个具有层次关系的集合,之所以称为树,是因为它看起来像“倒挂”的树,根在上,叶子朝下:
树的特点如下:
没有父节点的节点称为根节点(root);
每个节点都含有有限个子节点,或者没有子节点;
每一个非根节点有且只有一个父节点;
除了根节点外,每个子节点可以分为多个不相交的子树;
树里面没有环路(cycle)
树的术语
节点的度
子树的个数就是节点的度。
树的度
所有节点度中的最大值称为树的度。
叶子节点
叶子节点(leaf)也称为终端节点,度为0的节点就是叶子节点。
分支节点
也称为非终端节点,度不为0的节点就是分支节点。
层次(层数)
层数(level):根节点在第 1 层,根节点的子节点在第 2 层,以此类推
父节点
若一个节点含有子节点,则这个节点称为其子节点的父节点;
子节点
一个节点含有的子树的根节点,称为该节点的子节点;
兄弟节点
具有相同父节点的节点互称为兄弟节点;
节点的深度
节点的深度(dept ...
【Java集合框架】概述
Java集合框架
Java集合框架(Java collections framework)是包含一系列实现可重复使用集合的数据结构的类别和接口集合。
哈哈哈哈听起来有点杂,我们来捋一捋。
实际上就是Java提供了一个强大的集合框架,用于处理一系列对象。也就是说,集合是一种通用的容器,是对象的组合,集合框架提供了一种统一的方式来表示和操作各种集合,无需重复造轮子,减少了编程工作。提供了高性能的数据结构和算法实现,只需学习一组通用的集合API,减低学习难度。
集合框架的设计旨在使开发人员能够更轻松地管理和操作数据,同时提供了高性能和可扩展性。
集合接口
Java集合框架定义了一系列容器接口,主要分为两个层次,分别是Collection接口和Map接口,集合接口用于规范容器的行为以及提供统一的设计:
记录:
Collection :是大部分集合框架的根接口,表示一组对象。它定义了基本的集合操作,如添加、删除、遍历等。
Set:继承自Collection,表示不包含重复元素的集合。它没有提供额外的方法,只是保证不包含重复元素。
SortedSet:继承自Set,对元素进行排序存储。 ...
【数据结构】链表
概念
链表(Linked list)是一种线性表。由一系列节点对象组成,每个节点包含数据元素和一个指向下一个节点的引用,也就是说,各个节点通过“引用”相连接。
123456789// 链表节点类:class ListNode { int elem; // 节点的值 ListNode next; // 指向下一个节点的引用(也称为指针域) ListNode(int element) { // 构造器 elem = element; }}
“引用记录了下一个节点的内存地址,通过它可以从当前节点访问到下一个节点。因此,链表的设计使得各个节点可以分散存储在内存各处,它们的内存地址无须连续。”
链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理,同时,也失去了快速随机存取的优点(数组),同时增大了内存开销(存储下一个节点)。
链表类型
常见链表类型有三种,分别是单链表,环形链表和双向链表。对比如下:
特性
单向链表
环形链表
双向链表
简介
简称单链表,是一种常规链表,其节点包含值和 ...
【数据结构】数组
数组
数组(Array),由相同数据类型的元素(element)的集合组成的数据结构,分配一块连续的内存来存储。
初始化
初始化一个数组(不给定初始值):
12345678910// 创建一个名为arr的整数数组int[] arr = new int[5];// 上述语句分为两部分:// 1. int[]:声明一个整数数组// 2. new int[5]:使用new关键字创建一个包含5个整数元素的新数组// 注意:数组索引从0开始,因此这个数组的有效索引范围是0到4(总共5个元素)// 现在,arr是一个长度为5的整数数组,所有元素的初始值为0(基本数据类型的默认值)
初始化一个数组(给定初始值):
1234567891011121314151617// 创建一个名为nums的整数数组,并初始化数组元素int[] nums = { 1, 3, 2, 5, 4 };// 上述语句分为两部分:// 1. int[]:声明一个整数数组// 2. { 1, 3, 2, 5, 4 }:初始化数组元素,数组长度为5// 注意:这种初始化方式在声明数组的同时为 ...
【设计模式】类间关系
类图
类图是一种软件工程中的**统一建模语言(UML)**的静态结构图,用于描述系统的类集合、类的属性和类之间的关系。它主要用于概念建模,将系统的模型转化为代码。
类图的主要元素包括:
类的三个区域:
最上面是类的名称。
中间部分包含类的属性(字段)。
底部部分包含类的操作(方法)。
成员可见性:
+ 表示公共(public)成员。
- 表示私有(private)成员。
# 表示保护(protected)成员。
~ 表示包(package)成员,即对包内其他成员可见。
类图可进一步结合状态图或UML状态机来描述系统的行为。
类图是一种强大的工具,通过图形化的方式展示了系统中的类、它们之间的关系以及类的内部结构,帮助我们更好地理解和设计软件系统。
类间关系
类之间的关系指的是在面向对象编程中,不同类之间可能存在的连接和依赖关系。这些关系描述了类之间的交互方式和相互影响。
类之间的关系主要分为以下六种:
依赖关系(Dependency):一个类的实现依赖于另一个类的定义,但两者并没有强耦合。一个类的变化不会影响另一个类的实现,只是依赖关系较弱的一种关系。
关联关 ...