< 返回技术文档列表

如何理解Java中的树

发布时间:2021-11-07 02:22:57

这篇文章主要讲解了“如何理解Java中的树”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“如何理解Java中的树”吧!

1 树的定义

树实际上就是由许多个节点组成的集合,只不过每个节点的的组成是根据树状结构进行划分。一颗普通的树结构可以通过以下图来定义。

如何理解Java中的树

还是再来罗嗦一遍,树的结构就像是一颗倒挂的树,结点的组成是以层级往下。一棵树由若干子树构成,而子树又有更小的子树构成。

树的血缘关系

对于树中的某个结点,最多只和上一层的结点有直接的关系,而与其下一层的多个结点有直接关系。其上一层的结点称为双亲结点,下一层的结点称为孩子结点。所有位于树的最底部,没有孩子结点的结点被称之为叶子节点。具有相同双亲的结点互为兄弟节点。

树的家族等级

树是一个大家族,等级十分森严。树中某个结点的子树个数称为该结点的度。所以叶子结点也就是度为0的结点。而度不为0的结点被称之为内部结点。每一个结点都具有自己的层次,该层次由高往低递增,根结点为第一层,根的孩子结点为第二层,依次类推。一棵树最大的层数称之为树的高度(或深度)。

2 树的存储结构

由于普通的树结构并不像二叉树那么规则,可能是多叉树的组合,因此很难用常规的线性结构来存储。因此树结构的存储需要将树家族中的关系剥离出来进行存储,保存了每个结点之间的关系,整个树结构也就能依次进行恢复。

这就好比家族中的族谱一样,记录的是我们和双亲以及兄弟姐妹的关系。对于树而言,则根据存储关系的不同,可分为双亲表示、孩子表示以及孩子兄弟表示三种存储方法。

双亲表示法

树的双亲表示,显然就是通过记录每个结点的双亲结点来存储整颗树的层次关系。这里常用的一种存储结构就是数组。在连续的地址中存储树的结点,同时将之与其双亲结点在数组中的序号进行对应,这样一来就能够保存所有结点的双亲信息。

如何理解Java中的树

双亲表示法直接存储的是结点的双亲位置(对应于数组的下标),因此在求某个结点的双亲结点以及祖先结点时非常方便。但是却无法直接获得该结点的孩子结点的位置。

若需要查找指定结点的孩子以及后代结点,需要遍历整个数组并进行多次判断才行。

孩子表示法

树的双亲表示法的缺点显而易见,所以最直接的解决办法就是干脆存孩子结点算了。还别说,孩子表示法就是这样一种表示方法。但是相较于双亲结点的存储,存储孩子结点有一个需要考虑的问题,就是某个结点的双亲结点最多只有一个,但是其孩子结点可能有多个。如果每个孩子结点都存储在数组里,这样的方式不是一个明智的选择,并且也没有必要。

如何理解Java中的树

所以在使用孩子表示法来存储树的结构时,常使用数组+链表的结构。这种结构是不是很常见,跟解决哈希冲突的链地址法有异曲同工之意。在这样的链式结构中,用指针指示出结点的每个孩子,每个孩子的位置通过链表依次相连,这样就十分方便与查找每个结点的子孙。

只不过问题依旧,若要找出寻找某个结点的双亲则同样需要遍历所有链表。不过,既然双亲表示和孩子表示都有了,简单粗暴的合并一下不就可以相互补充,共同进退吗。

如何理解Java中的树

所谓的双亲孩子表示法,直接将双亲表示和孩子表示组合起来即可。这样即可满足双亲的查找,也可以满足孩子的查找。

孩子兄弟表示法

本来有了双亲孩子表示法就已经足够用来存储树中的数据信息了,为什么还要来一个孩子兄弟法呢?其实不然,孩子兄弟表示法反而是一种很有意思且很有价值的表示方式。

在孩子兄弟表示法中,我们约定只存储每个结点的第一个孩子结点和下一个兄弟结点。不仅如此,结点的存储是通过链表进行的。话说不太清,还是直接看图吧。

如何理解Java中的树

看起来似乎有些诡异的形状,每个结点都作为链表的一个节点,通过两个指针分别指向第一个孩子结点和下一个兄弟结点。为了防止大家看不懂,我举个例子。拿结点B来说,它的第一个孩子结点是E,而它的下一个兄弟是与它处于同一层级的C。因此结点B的两个指针分别指向了E和C。

孩子兄弟表示法这样看起来似乎很鸡肋,但是假如我们调整一下右边这个图,就能看出其中的蹊跷了。

如何理解Java中的树

看出来了吗,孩子兄弟表示法实际上就是将一颗普通的树转换成了二叉树的形式。所以说二叉树为什么这么重要,因为万变不离其中呀。看到这,其实也透露出树和二叉树之间的转换关系,许多二叉树上的性质和操作也可以借此运用在普通的树结构中。

3 树的遍历

学过二叉树的同学想必应该对前序遍历、中序遍历、后序遍历、中序遍历烂熟于心了吧,无论是迭代还是非迭代的写法,都是基础得不能再基础的东西了。而对于普通的树而言,由于每个结点子树的个数并不一定,因此不好规定前、中、后序的顺序。

所以一般而言对于树的遍历方式有两种,根据根结点被遍历的先后可分为先根遍历和后根遍历。

树的先根遍历是先访问树的根节点,然后依次遍历根结点的各个子树。如此递推。当将一颗普通树转换为对应的二叉树时(孩子兄弟表示法),其实就相当于是前序遍历。

树的后根遍历就不用多说了吧,跟先根遍历相反,先访问根结点的各颗子树,再访问树根结点。而树的后根遍历就相当于转换后二叉树的中序遍历。不信的话你试试。

4 树、森林和二叉树的相互转换

写到这,突然发现好像忘记介绍森林是什么东西了。其实森林的概念很简单,就是很多颗树。对,就是这样。

树、森林和二叉树本质上都是类似的结构,因此相互之间可以进行转换。任意一个森林或者一棵树都可以对应表示为一颗二叉树,而任何一颗二叉树也能够对应到一个森林或一棵树上。

树转换为二叉树,我们在前面已经介绍过,就是通过树的孩子兄弟表示法。通过孩子兄弟法进行表示时,每一个树都可以用一颗唯一的二叉树来表示。但是转换过来的二叉树却有一个非常显著的特点。仔细观察。

如何理解Java中的树

很显然,这不是一颗平衡的二叉树。并且,根节点是没有右子树的,我敢肯定的说。这是因为根节点是没有兄弟结点的,它只有孩子结点,所以在转换为二叉树之后,一定是没有右子树的。

不过这样的缺陷可以在森林中进行弥补。由于森林中有很多棵树,因此可以将其它树作为右子树。具体的实现步骤,先将森林中的每一棵树转换为二叉树,再将第一颗树的根结点作为转换后的二叉树的根。第一棵树的左子树作为转换后二叉树根结点的左子树,第二棵树作为转换后二叉树的右子树。第三颗树作为转换后二叉树根结点的右子树的右子树。以此类推。

咱们来举个例子。这里有一个由三颗树构成的森林。

如何理解Java中的树

将上面三棵树分辨转换二叉树是以下形式。

如何理解Java中的树

然后将绿色二叉树作为蓝色二叉树根节点的右子树,将黄色二叉树作为绿色二叉树根节点的右子树,就可以得到森林转换为二叉树的结果。

如何理解Java中的树

根据以上的规则,同样可以将一颗二叉树转换为树和森林。

感谢各位的阅读,以上就是“如何理解Java中的树”的内容了,经过本文的学习后,相信大家对如何理解Java中的树这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是血鸟云,小编将为大家推送更多相关知识点的文章,欢迎关注!


/template/Home/Zkeys/PC/Static