Java数据结构学习之二叉树

1 背景知识:树(Tree)

在之前的笔记中,我们介绍的链表、栈、队列、数组和字符串都是以线性结构来组织数据的。本篇笔记要介绍的采用的是树状结构,这是一种非线性的数据组织形式。

树结构由节点构成,且不存在。我们曾在线性表型的数据结构中介绍过循环链表和循环队列,这两种数据结构使得存储容器中的元素形成一个闭环,具体可参看“数据结构学习笔记”系列的相关博文,链接贴在下面:

链表:https://www.jb51.net/article/215278.htm

队列:https://www.jb51.net/article/211502.htm

树状结构与线性结构最重要的区别在于:树只能有分叉,不能有闭环。如下图所示:

树结构不允许有环其实是树的层级性决定的。树结构中最顶端的结点是根节点,根节点即整棵树的顶级父节点。除了根节点只有子节点,最底层的节点只有父节点,其余各层的节点都是上层节点的子节点、下层节点的父节点。也就是说,树中的数据只与其上下层的数据有关,同层数据间不能有直接联系,这也就是树结构不能有环的原因。

树层级的多少往往被描述为树的高度(height),由于我们是从上往下观察树结构的,因此也被描述为树的深度(depth)。上面图示中两颗树的深度都是3.

2 何为二叉树(Binray Tree)

2.1 二叉树的概念与结构

二叉树顾名思义,即每个父节点最多只有两个分叉的树,这是数据结构领域使用频率极高的一种树结构,这与我们常常用二元对立的观点认识世界的思维习惯有关。

二叉树的结构不仅具有层级性,还具有递归性,一个父节点连接左子节点右子节点,而左右子节点又可以作为父节点再各自连接两个子节点,以此类推。因此二叉树是一种层次嵌套的数据结构,除了根节点外,树中任意一个父节点都能作为一棵子树,位于上层父节点左侧的子树被称为左子树,位于右侧的子树被称为右子树

二叉树体现了人们用二元思维认识自然的方式。笔者的本行是语言学,语言学界主流的对句法结构的分析方法就是类似于二叉树的二分法。拿汉语的句法结构来说,有主谓、述宾、定中、状中、述补等基本的结构类型。句法结构具有层次嵌套递归的特点,同时也有对语序的要求,即句法二叉树中的左右节点的位置并不是任意的。这种分析方法语言学上被称为层次分析法,如果我们用该方法分析句子“文程同学热爱编程”,传统图示和句法树图示分别如下:

2.2 满二叉树与完全二叉树

二叉树中有两个特殊的结构类型:满二叉树完全二叉树。满二叉树的结构特点是除了最后一层外,所有层级的节点都有两个子节点;完全二叉树的结构特点是除了最后两层外,所有层级的节点都有两个子节点,倒数第二层的子节点(即最后一层节点)全部靠左排列。如下图所示:

由此可见,满二叉树一定是完全二叉树,完全二叉树可满可不满。这两种二叉树体现了我们采用树状结构存储数据时,对于空间利用率的追求。比如我们设计一个深度为n的二叉树,那么整个二叉树能容纳的最大节点数为2^n-1,满二叉树就是达到了最大节点数,用足了二叉树的容量。完全二叉树除了n层没有子节点,除n-1层外各层父节点都充分利用了自己拥有子节点的名额,也算是尽可能做到了对空间的充分利用。

为了更好地理解完全二叉树的空间利用率,我们看一个非完全二叉树的例子,如下图所示:

上图是一个深度为4的非完全二叉树,前3层的父节点都预留了左右两个子节点的位置,然而第二层的第2个结点只使用了右子节点的空间,浪费了左子节点的空间。如果二叉树的深度很深,其中很多层级的父节点都存在浪费子节点“名额”的现象,那么会造成相当大的空间资源的浪费,二叉树也失去了“二叉”的意义。但是完全二叉树最多浪费倒数第二层父节点的子节点名额,整体上能够保证较高的空间利用率。

2.3 二叉树的三种遍历方式

二叉树的形状整体上构成一个三角形,最小的二叉树由一个位于中间的父节点和位于左右两侧的子节点构成,这导致遍历访问一棵二叉树的所有节点有三种顺序:前序遍历(Preorder Traversal , VLR)、中序遍历(Inorder Traversal , LDR)和后序遍历(Inorder Traversal , LRD)。

无论哪种遍历方式,二叉树都是从上到下、从左到右遍历的,即从父节点层到子节点层、从左子树到右子树。2.1解释了二叉树的递归性,遍历二叉树时采用的也是递归(recursion)的方式。对于整棵树或某一子树,都是从根开始,先遍历其左子树,再遍历其右子树;分别遍历左右子树时,同样是从根开始,从左向右遍历;以此类推,直到遍历到最后一个右子节点。

如果我们以打印节点数据的方式来表示对节点的访问,那么前序、中序和后序的区别就在于打印节点的时机不同。前序遍历的操作顺序是打印节点在遍历左子树和遍历右子树之前中序遍历的操作顺序是打印节点在遍历左子树和遍历右子树之间后序遍历的操作顺序是打印节点在遍历左子树和遍历右子树之后。子树遍历的过程是递归实现的。

如果我们想遍历2.1演示的“文程同学热爱编程”的句法二叉树,那么用三种遍历方法得到的遍历结果分别如下:

3 二叉树及其遍历的简单实现(Java)

我们用Java语言实现“文程同学热爱编程”这个句子对应的句法二叉树,设计思路是:将同层级的父节点(二叉树及其各子树的根节点)存入数组中,数组中存入的是结点,包括数据左右指针,左右指针分别指向位于下一层节点的左右子节点,如果没有子节点则指针为空指针。

用数组的好处是,可以通过节点所在的索引建立上下层级父节点和子节点的指针联系。假设父节点在它所在的层级数组中的索引为i,那么左子节点在它所在层级数组中的索引为(i+1)*2-2,右子节点的索引为(i+1)*2-1,即左子节点的索引+1。

遍历默认从整棵二叉树的根节点开始,通过方法的重写实现默认参数的效果。

准备工作1:MyBinaryTree.java,创建一个二叉树的类

package com.notes.data_structure6;
 
import com.notes.data_structure6.NumberOfNodesException;
 
public class MyBinaryTree {
	// 树的根结点
	private Node[] root;
	// 树的深度(当前层级数)
	private int depth;
	// 将每一层所有的 结点 都存储在数组中,结点数是 2的 层数 次幂
	private Node[] currentLevel;
	
	
	public MyBinaryTree(String data) {
		Node[] rootArray = new Node[] {new Node(data)};
		this.root = rootArray;
		this.currentLevel = rootArray;
	}
 
	// 定义一个结点类
	private class Node{
		private String data; // 数据
		private Node leftNext; // 左指针
		private Node rightNext; // 右指针
		
		// 构造方法:Node实例化时传入数据
		public Node(String data) {
			this.data = data;
		}	
	}
	
	// 向树中增加一层结点
	public void add(String[] datas) throws NumberOfNodesException {
		// 层级数增加1
		depth++;
		// 新增 层级 的最大结点数
		int nodeNum = numberOfNextNodes();
		// 如果传入的 数据数 与 当前层级 最大结点数 不符,抛出异常
		if(datas.length != nodeNum) {
			throw new NumberOfNodesException("第"+depth+"层最大父节点数为"+nodeNum);
		}
		// 将传入的 数据数组 转换为 结点数组
		Node[] newLevel = new Node[nodeNum];
		// 当前 层级的 结点数量(新增层级的父)
		int nodeNum2 = (int) Math.pow(2, depth-1);
		// 让每一个结点都与上层 父结点 建立连接
		for(int i=0;i<nodeNum2;i++) {
			// 让父结点 的左指针 指向 左子结点
			int leftIndex = (i+1)*2-2; // 计算左子结点对应的新层级数组的索引
			currentLevel[i].leftNext = new Node(datas[leftIndex]); // 建立指针指向
			newLevel[leftIndex] = currentLevel[i].leftNext; // 将结点加入新层级结点数组
			// 让父结点 的右指针 指向 右子结点
			int rightIndex = leftIndex+1; // 计算右子结点对应的新层级数组的索引
			currentLevel[i].rightNext = new Node(datas[rightIndex]); // 建立指针指向
			newLevel[rightIndex] = currentLevel[i].rightNext; // 将结点加入新层级结点数组
		}
		// 让新增层级的数组成为当前层级的数组
		currentLevel =  newLevel;
	}
	
	// 前序遍历所有结点
	public void preTraversal(Node node) {
		if(node==null) {
			return;
		}
		System.out.print(node.data+" ");
		preTraversal(node.leftNext);
		preTraversal(node.rightNext);
	}
	
	// 重写 前序遍历 方法,让遍历从 根结点 开始
	public void preTraversal() {
		Node node = root[0];
		if(node==null) {
			return;
		}
		// 递归时调用带参数的方法
		System.out.print(node.data+" ");
		preTraversal(node.leftNext);
		preTraversal(node.rightNext);
	}
	
	// 中序遍历所有结点
	public void midTraversal(Node node) {
		if(node==null) {
			return;
		}
		midTraversal(node.leftNext);
		System.out.print(node.data+" ");
		midTraversal(node.rightNext);
	}
	
	// 重写中序遍历 方法,让遍历从 根结点 开始
	public void midTraversal() {
		Node node = root[0];
		if(node==null) {
			return;
		}
		// 递归时调用带参数的方法
		midTraversal(node.leftNext);
		System.out.print(node.data+" ");
		midTraversal(node.rightNext);
	}
	
	// 后序遍历所有结点
	public void posTraversal(Node node) {
		if(node==null) {
			return;
		}
		posTraversal(node.leftNext);
		posTraversal(node.rightNext);
		System.out.print(node.data+" ");
	}
	
	// 重写后序遍历 方法,让遍历从 根结点 开始
	public void posTraversal() {
		Node node = root[0];
		if(node==null) {
			return;
		}
		// 递归时调用带参数的方法
		posTraversal(node.leftNext);
		posTraversal(node.rightNext);
		System.out.print(node.data+" ");
	}
	
	// 查看 新增层级 的最大结点数
	public int numberOfNextNodes() {
		return (int) Math.pow(2,depth);
	}
	
	// 查看 树 的深度(层级数)
	public int getDepth() {
		return depth;
	}
	
	
}

准备工作2:NumberOfNodesException.java,为add()方法创建一个自定义异常,如果传入的数据数与当前层级最大结点数不符,则抛出该异常(如果二叉树不满,在数组的相应位置传入null)。

package com.notes.data_structure6;
 
public class NumberOfNodesException extends Exception{
	public NumberOfNodesException(String message) {
		super(message);
	}
}

句法二叉树的实现及其遍历:TreeDemo.java

package com.notes.data_structure6;
 
public class TreeDemo {
	public static void main(String[] args) throws NumberOfNodesException {
		// 实例化二叉树类,并且传入根节点的数据
		MyBinaryTree tree = new MyBinaryTree("句子");
		// 加入第一层节点的数据
		tree.add(new String[] {"主语","谓语"});
		// 加入第二层节点的数据
		tree.add(new String[] {"定语","中心语","述语","宾语"});
		
		// 前序遍历
		tree.preTraversal(); // 句子 主语 定语 中心语 谓语 述语 宾语 
		System.out.println();
		// 中序遍历
		tree.midTraversal(); // 定语 主语 中心语 句子 述语 谓语 宾语 
		System.out.println();
		// 后序遍历
		tree.posTraversal(); // 定语 中心语 主语 述语 宾语 谓语 句子 
	}
}

到此这篇关于Java数据结构学习之二叉树的文章就介绍到这了,更多相关Java二叉树内容请搜索179885.Com以前的文章或继续浏览下面的相关文章希望大家以后多多支持179885.Com!

猜你在找的Java数据结构学习之二叉树相关文章

代码生成器,可以有效减少编写重复代码,快速实现简单的业务逻辑,也能让我们的代码保持一致。那目前,我们看到的代码生成器,大部分是基于velocity引擎模板生成的,接下来我
今天给大家带来的是关于Java的相关知识总结,文章围绕着JAVA正则表达式及字符串的替换与分解展开,文中有非常详细的介绍及代码示例,需求的大佬可以参考下
今天给大家带来的是关于Java数据结构的相关知识,文章围绕着Java二叉树展开,文中有非常详细的介绍及代码示例,需求的大佬可以参考下
了SpringBoot与Postman实现REST模拟请求的操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教
我们知道Java是一个面相对象的编程语言,基本类型并不具有对象的性质,为了让基本类型也具有对象的特征,就出现了包装类型,它相当于将基本类型“包装起来”,使得它具有了
要实现自定义的xml配置,需要有两个默认spring配置文件来支持。一个是spring.schemas,一个是spring.handlers,前者是为了验证你自定义的xml配置文件是否符合你的格式
ArrayList基于动态数组实现,在添加和删除的时候存在扩容和缩容这样重新规划数组大小的机制。在ArrayList中,维护Object[] elementData数组来管理元素,但是ArrayList
该教程使用idea开发工具初始化javaweb项目,该运行在tomcat服务器上通过配置项目环境变量保证tomcat正常启动,具体操作配置教程参考下本文
SpringBoot 在项目启动的时候封装了创建对象的方法,无需我们手动配置,接下来通过本文给大家介绍SpringBoot 自动配置原理解析及源码展示,感兴趣的朋友一起看看吧
关于Java并发的通信机制是基于共享内存实现的,线程之间共享程序的公共状态,通过写-读内存中的公共状态进行隐式通信,这对程序员是透明的,我们需要理解其工作机制,以防
IDEA编译的时候乱码,Build Output提示信息乱码,本文就详细的介绍一下解决方法,有需要的同学可以了解一下
Cookies是 web站点放置到你的硬盘上的程序。它们驻留在你的计算机上收集关于你在因特网上所做的一切事情的信息,并且 web站点可以在任何时候读取到Cookies收集到的