java 实现二叉树

复习二叉树,实现树的一系列的操作。

参考:http://www.bilibili.com/video/av10472353/

 

一、实现最简单粗暴的二叉树

首先实现一个节点类Node,然后在main方法中手工将二叉树拼凑起来,再通过findNode方法遍历该二叉树中的所有节点。

MyBinaryTree1.java

运行结果为:

二、实现三种遍历方式

实现三种遍历方式。

MyBinaryTree2.java

运行结果为(syso纵向显示太浪费文章空间,所以我后期加工弄成横向显示了):

在这里要注意的是三种遍历的顺序,先序遍历是根->左->右,中序遍历是左->根->右,后序遍历是左->右->根。

三种遍历的难点是递归的用法。个人认为递归的关键在于局部思考问题,不要被绕进递归的过程中,不需要全局地看问题,否则容易被复杂的过程搞晕。我们只需要找到正确的入口、结果两个要素就可以写出正确的递归。

举个例子:我们应该如何写一个先序遍历的方法?

首先要注意方法的返回值。因为我只想输出各节点的数据,所以只需要void就行了。

接着我们要确定遍历的节点是否null。如果是null,就不存在数据和下面的节点,不需要继续往下遍历,直接结束方法。

因为先序遍历的顺序是根->左->右,获得一个节点之后应该马上将其数据输出,所以直接syso。

获取了根的数据后,就轮到左节点->右节点。如何获取左节点的数据?当然再次调用先序遍历的方法了(递归),右节点也是同理。

总之,递归的难点在于如何正确地调用自身。只要把一个流程写好,递归就不会出现问题。

三、改进构造二叉树的方式,实现更多方法

Tree.java

我们详细分析二叉树的实现思路。

(1)二叉排序树的构造

在前面一、二章的例子中,我们都是使用“简单粗暴”的方式,一个一个建立节点,然后组成二叉树。那么问题来了,如果要构成拥有很多节点的二叉树,就要建立一大堆节点,此过程全部需要手工实现(而且结构很复杂),代码量很大。

所以,我们应该写一个构造方法,按照一定的规律(根>左,根<右,没有重复节点)构造一棵二叉排序树(Binary Sort Tree,简称BST)。

这里提一下,二叉排序树也被成为二叉搜索树(Binary Search Tree),实际上就是一回事。二叉排序树只是二叉树中的基础,基本上不会用于生产(生产中使用的都是优化版本,比如AVL、红黑树)。

如果新插入的节点值比“根节点”(不一定是最开始的根节点)的值要小,那么肯定要放在“根节点”的左边。如果“根节点”左节点为空,那么直接插入。如果左节点不为空,那么继续和左节点进行比较,循环此过程。

如果新插入的节点值比“根节点”(不一定是最开始的根节点)的值要大,那么肯定要放在“根节点”的右边。如果“根节点”右节点为空,那么直接插入。如果右节点不为空,那么继续和右节点进行比较,循环此过程。

(2)二叉树的根节点

我们分析二叉树,一定要找到二叉树的入口,也就是根节点。获取根节点之后,才能对整棵二叉树进行各种操作。所以我们需要在Tree类中定义一个Node作为根节点:

在构造二叉树时,必须先设置根节点:

之后各种方法(一般情况下)都需要使用根节点作为参数(获取二叉树的起始位置)。

(3)获取二叉树的高度

想要获取二叉树的高度,只需要获取、比较“根节点”的左右子树的高度,选取最大值,最后+1即可。这里需要用到递归的思想:

(4)获取二叉树中的最大值

想要获取二叉树中的最大值,需要同时比较根节点、左节点、右节点的值。需要用到递归的思想。

我们着眼于局部。每次只需要比较三个节点的大小,获取Max值,递归此过程即可。

(5)二叉排序树的中序遍历

只要是二叉排序树,中序遍历出来的数据一定是按照从小到大的顺序排列。所以二叉排序树常用来排序(废话)。

四、总结

二叉树可以分出很多种类,比如B+、B、B-树,红黑树…均有其独立的实现方法,但是万变不离其宗,只要分析树的操作流程,再逐一实现即可。

发表评论

电子邮件地址不会被公开。 必填项已用*标注