皇冠体育app:查找算法系列文(一)一文入门二叉树

admin 3个月前 (06-27) 科技 44 0

微信民众号:小超说

这是查找算法系列文章的第一篇,助你快速入门二叉树

什么是树(Tree)?

我们首先来看一些图片:

其中,第一、二、四个都是树,第三个不是。树的特点很明显吧!

其中每个元素叫做“节点”;用来毗邻相邻节点之间的关系,我们称之为“父子关系”。例如在图一中,A节点是B节点的父节点,B节点是A节点的子结点,同时,B节点和Q节点是同一个父节点A的子节点,以是它们之间相互成为兄弟节点。我们把没有父节点的节点称为根节点,也就是图一中的A节点。我们把没有子节点的节点称为叶子节点,好比图一中的D、E、F、G节点。这些观点都是显而易见,但却是最基本的器械。

二叉树

二叉树,自然就是每个节点最多有两个分支,即两个子节点的一种树,两个分支划分称为左子树右子树。照样那上面那张图举例,图一、图二和图四都是二叉树,由于它们每个节点都最多含有两个子节点。其中,图一又称为满二叉树,图四又称为完全二叉树。而之以是泛起完全二叉树的观点,其实是基于二叉树的物理存储方式。

二叉树的存储方式

  • 基于链表的链式存储法
  • 基于数组的顺序存储法

链式存储法:

我们为每个节点建立一个Node工具:

class Node{
		int data;
		Node left,right;
}

每个节点都是一个Node工具,它包罗我们所需要存储的数据,指向左子节点的引用,直向右子节点的引用,就像链表一样将整个树串起来。若是该节点没有左子节点,则Node.left==null或者Node.right==null.

顺序存储法

我们把根节点储存在下标为i=1的位置,那么左子节点储存在2*i=2的位置,右子节点储存在下标为2*i+1=2的位置。依此类推,完成树的存储。借助下标运算,我们可以很轻松的从父节点跳转到左子节点和右子节点或者从随便一个子节点找到它的父节点。若是X的位置为i,则它的两个子节点的下标划分为2i2i+1,它的父节点的位置为i/2(这里效果向下取整)。

详细如下图所示:可以发现,只有完全二叉树存储的效率才最高,最省内存

二叉树的遍历

二叉树的遍历操作主要有三种

  • 前序遍历
  • 中序遍历
  • 后序遍历

前序遍历是指,对于树中的随便节点来说,先打印这个节点,然后再打印它的左子树,最后打印它的右子树。

中序遍历是指,对于树中的随便节点来说,先打印它的左子树,然后再打印它自己,最后打印它的右子树。

后序遍历是指,对于树中的随便节点来说,先打印它的左子树,然后再打印它的右子树,最后打印这个节点自己。

注重,这其中有点递归的味道

照样以适才的图为例:

  • 前序遍历:A->B->D->E->C->F
  • 中序遍历:D->B->E->A->F->C
  • 后序遍历:D->E->B->F->C->A

详细的代码实现(写出递归即可):

public void preOrder(Node root){
	if(root==null) return;
	System.out.println(root.data);//打印root节点的值
    preOrder(root.left);
    preOrder(root.right);
}

public void inOrder(Node root){
	if(root==null) return;
	inOrder(root.left);
	Systrm.out.println(root.data);
	inOrder(root.right);
}

public void inOrder(Node root){
	if(root==null) return;
	inOrder(root.left)
	inOrder(root.right);
	Systrm.out.println(root.data);
}

二叉树遍历的时间复杂度是O(n),这是由于每个节点最多会被接见两次,(递归时函数进栈和出栈),以是遍历操作的接见次数跟节点的个数 n 成正比,也就是说二叉树遍历的时间复杂度是 O(n)。

展望

经由上面的先容,我们已经大致对二叉树有了一个基本的熟悉,那么,二叉树存在的意义是什么呢?我们可以基于这种数据结构设计出哪些高效的算法呢?下一次我们将先容二叉查找树(Binary Search Tree),我们将界说一种数据结构并维护它的性子。

题外话:对于算法初学者,推荐一本十分 nice 的书籍 《算法第四版》,内里种种配图十分详细。若是你需要电子版文件,后台回复算法4即可获得下载链接。后台回复 算法01 送你一份 算法与数据结构头脑导图。最后,希望我们一起提高,一起发展!

皇冠体育app:查找算法系列文(一)一文入门二叉树 第1张

,

欧博allbet注册

欢迎进入欧博allbet注册(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。

Allbet声明:该文看法仅代表作者自己,与本平台无关。转载请注明:皇冠体育app:查找算法系列文(一)一文入门二叉树

网友评论

  • (*)

最新评论

文章归档

站点信息

  • 文章总数:439
  • 页面总数:0
  • 分类总数:8
  • 标签总数:900
  • 评论总数:123
  • 浏览总数:3178