树

一个树是基于层次结构存储元素的抽象数据结构。除了顶部元素(也称为根元素)之外，树中的每个元素都有一个父元素，而一些或所有元素可能包含子元素。

树通常由一组节点定义，其中包含父而且孩子们变量。例如,对于 $\ bf{\颜色{# E81990}{\文本{红}}}$，根没有父母，但有孩子 $\ bf{\颜色{# CEBB00}{\文本{黄色}}}$， $\ bf{\颜色{# 3 d99f6}{\文本{蓝}}}$而且 $\ bf{\颜色{# D61F06}{\文本{红}}}$．这些变量实际上是指向其他节点的指针。尽管从技术上讲树是图，但我们可以通过注意在树抽象数据类型中，任何两个顶点都由一条且仅一条路径连接来区分这两者。两个节点是同一父节点的子节点兄弟姐妹(即。 $\ bf{\颜色{# 69047 e}{\文本{紫色}}}$而且 $\ bf{\颜色{白}{\文本{白}}}$)．一个节点外部如果它没有孩子(即。 $\ bf{\颜色{# 20 a900}{\文本{绿}}}$)．相反，如果节点有一个或多个子节点，则它是内部节点。外部节点也称为叶子．的深度或水平的长度为从根节点到该节点的简单路径的长度水平的 $\ bf{\颜色{# EC7300}{\文本{橙色}}}$是2，因为这是从它到根结点的边数)。

有多种方法高度的定义。很多资料，包括Brilliant的课程二叉树将高度定义为出现的最大级别数。这意味着图的高度是3。但要小心:其他人将树的高度定义为最长简单路径上的节点数;在这个定义下，高度最终要大1。

下面的树包含多少外部节点(叶)?

图像

---

记住，叶节点是没有子节点的。自 $4、5、6,$而且 $7$树上都是叶子，上面有四片叶子。 $_ \广场$

在前面的例子中，树的高度是多少?

---

仔细观察图表，我们会发现 $2$是从图中任意节点出发的最长路径。因此 $2$是树的高度。 $_ \广场$

让我们构建一个非正式的Java树ADT。我们首先将树中的一个位置表示为节点．该对象将包含一个父，左而且正确的变量。然后，树将是根节点及其各自的指针。

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

公共类树｛静态类节点｛节点父，左，正确的；int价值；公共节点（节点父，int价值）｛这．父＝父；这．价值＝价值；｝｝节点根；树（节点p）｛//在这个实现中，树从不为空。//换句话说，它总是包含至少/ /一个节点;根＝p；｝////////////////////////////////////////////////////////////////////公共int大小（）｛//计算树的大小返回大小（根）;｝公共int大小（节点p）｛//计算子树的大小//以p为根如果（p= =零）返回0；其他的返回大小（p．左）+大小（p．正确的）+1；｝｝｝

编写一个方法来打印树的值

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，告诉我们是向右移动还是向左移动。作为一个例子，让我们解码字符串 $01010111.$我们从根源开始。因为第一个比特是 $0$，第一步是对的。接下来我们向左移动，然后向右移动。此时，我们遇到了第一个字符r。要解码下一个字符，我们再次从根字符开始。下一位是1，所以我们向左移动，遇到下一个字符a。最后的位0111解码为t。因此，位串代表单词 $老鼠$．

霍夫曼给出了一种算法，该算法从一个表中构造霍夫曼代码，该表给出了要表示的字符出现的频率，因此构造的代码在最小空间中表示字符串字符。