树
介绍
一个树是基于层次结构存储元素的抽象数据结构。除了顶部元素(也称为根元素)之外,树中的每个元素都有一个父元素,而一些或所有元素可能包含子元素。
树通常由一组节点定义,这些节点包含父和孩子们变量。例如,对于 ,根没有父母,但有孩子 , 和 .这些变量实际上是指向其他节点的指针。尽管从技术上讲树是图,但我们可以通过在树抽象数据类型中,任意两个顶点由一条且只有一条路径连接来区分它们。两个节点是同一个父节点的子节点兄弟姐妹(即。 和 ).一个节点外部如果它没有孩子(即没有孩子)。 ).相反,如果一个节点有一个或多个子节点,则它是内部的。外部节点也称为叶子.的深度或水平是从根结点到该结点的简单路径的长度水平的 是2,因为这是从它到根的边数)。
有很多方法高度根树的定义。很多信息来源,包括Brilliant的课程二叉树将高度定义为出现的最大级别数。这意味着图的高度是3。但是要注意:其他人将树的高度定义为沿着最长简单路径的节点数;根据这个定义,高度最终会大1。
下面的树包含多少外部节点(叶节点)?
记住,叶节点是没有子节点的节点。自 和 树上面都是叶子,有四片叶子。
在前面的例子中,树的高度是多少?
通过观察图表,我们可以看到 是到图中任何单个节点的最长路径。因此 是树的高度。
树的Java实现
让我们构建一个非正式的Java树ADT。我们首先将树中的一个位置表示为a节点
.该对象将包含父
,左
和正确的
变量。然后,树将成为根节点及其各自的指针。
12 34 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
|
编写一个输出树值的方法
12 3 4 5 6 7 8 9 10 11 12 13私人无效打印(节点p) {如果(p! =零) {打印(p.左);系统.出.println(p.价值);打印(p.正确的);}}公共无效打印(){//输出树中的值//在这里添加一些东西打印(根);}
这里我们建立了一个基本的递归解,如果它是平衡二叉搜索树,它会输出树。主要思想是考虑我们的基本情况
p.value = =零
到那时什么都做不了。
编写一个计算给定树高度的方法。
1 2 3 4 5 6 7 8 9私人int高度(节点p){//返回树的高度如果(p==零)返回-1;返回数学.马克斯(高度(p.左),高度(p.正确的))+1;}公共int高度(){返回高度(根);}
霍夫曼编码
看到全文:霍夫曼编码.
在计算机内部表示字符的最常见方法是使用固定长度的位字符串。例如ASCII,用一个7位的字符串表示每个字符。例子如下:
霍夫曼编码,它通过变长位字符串表示字符,提供了ASCII和其他固定长度代码的替代方案。其思想是使用短位字符串来表示更常用的字符,比如文本和程序,使用的空间比使用ASCII时要小。由于内存有限,一些手持计算机使用霍夫曼编码。
霍夫曼代码很容易用树来定义。要解码一个位字符串,我们从根开始,向下移动直到一个字符
遇到。位,0或1,告诉我们是向左还是向右移动。作为一个例子,让我们解码这个字符串 我们从根开始。因为第一个位是 第一步是正确的。接下来我们向左,然后向右移动。此时,我们遇到了第一个字符r。为了解码下一个字符,我们再次从根开始。下一个位是1,所以我们向左移动,遇到下一个字符a。最后一个位0111解码为t。因此,这个位串表示这个单词 .
霍夫曼给出了一个算法来构造一个霍夫曼代码,从表中给出要表示的字符出现的频率,这样构建的代码在最小的空间中表示字符的字符串。