《数据结构》课件-项目六 树与二叉树

用二叉树实现文本压缩项目概述

树是数据元素之间具有层次关系的非线性结构。树在文件系统、编译器、索引以及查找算法中都有广泛的应用。二叉树是树的一种重要类型，在树结构的应用中起着非常重要的作用，如利用最优二叉树对文本内容进行重新编码，可以对文本内容进行无损压缩，在存储时可以减少存储空间，在通信传输时可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。在数据库中，二叉树被广泛应用于实现索引。在编程语言中，二叉树被广泛应用于解析和生成语法树。在人工智能中，二叉树被广泛应用于实现决策树和搜索树。许多实际问题抽象出来的数据结构往往是二叉树，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。项目目标序号能力目标知识要点1理解二叉树的逻辑结构树的基本概念二叉树的基本概念、性质、基本操作、抽象数据类型2理解二叉树的顺序与链式存储结构及其算法实现二叉树顺序存储二叉树链式存储及其算法实现3能实现二叉树的遍历二叉树的遍历4能在实际问题中找出二叉树并用二叉树解决实际问题使用最优二叉树解决文本压缩编码问题项目情境编程统计学生的成绩

1．情境描述

前常用的图像、音频、视频等多媒体信息，由于数据量大，一般会采用数据压缩技术对它们进行压缩后存储和传输。数据压缩技术通过对数据重新编码进行压缩，以减少数据占用的存储空间，提升数据传输效率。使用时，再进行解压缩，恢复数据原来的特性。假设待压缩的文本为“Youareaprogrammer!”，这段文本中用到的字符集为{!，Y，g，p，u，e，m，o，˽，a，r}（为了描述方便，用˽表示空格），各字母出现的次数依次为{1，1，1，1，1，2，2，2，3，3，4}。现要求为这些字母重新设计编码，使文本的编码总长度尽可能短。在计算机系统中，字符采用等长的ASCII编码，每个字符8位，各字符对应的ASCII编码为{00100001，01011001，01100111，01110000，01110101，01100101，01101101，01101111，00100000，01100001，01110010}，文本编码总长度为168位。实际应用中，各个字符的出现频度或使用次数是不相同的，在设计编码时，可以采用变长编码，使用频率高的字符用短码，使用频率低的用长码，以优化整个文本编码。一种优化后的编码所示。重新编码后，各字符编码长度变短，对应的新编码为{0100，0101，0110，0111，1100，1101，000，001，100，101，111}，文本编码总长度为70位，实现了文本的压缩.2.

基本要求根据上面的描述，完成下面的任务：

(1)根据待压缩的文本，设计一种编码，使文本压缩编码后的总长度最短；(2)输入一段待处理的文本，输出其对应的新压缩编码和编码的长度；(3)输入一段压缩的编码，输出解码后对应的文本。任务二

用顺序最优二叉树实现文本压缩学习目标理解二叉树的顺序存储结构能基于顺序存储结构构建二叉树12能应用最优二叉树解决问题3

在任务一中，己分析出二叉树的逻辑结构，定义了二叉树的抽象数据类型，并学习了最优二叉树（最优二叉树）的构建的方法。接下来考虑将逻辑结构为二叉树的数据元素存储到计算机中去，进行存储结构的设计。存储结构有顺序存储结构和链式存储结构两种，本任务将二叉树的逻辑结构映射成顺序存储结构，并基于顺序存储结构实现最优二叉树的基本运算，最后，将己实现的顺序最优二叉树应用在文本压缩问题中。任务描述步骤一：将二叉树的逻辑结构映射成顺序存储结构基于完全二叉树的顺序存储

性质5

对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从0开始顺序编号，则对于序号为i（0≤i<n)的结点：（1）若i＝0，则i为根结点；若i>0，则i的双亲结点的序号为（i-1）/2。（2）若2i+1<n，则序号为i的结点的左孩子结点的序号为2i+1；否则序号为i的结点无左孩子。（3）若2i＋2<n，则序号为i的结点的右孩子结点的序号为2i＋2；否则序号为i的结点无右孩子。完全二叉树中结点的序号可以唯一地反映结点之间的逻辑关系。将完全二叉树的结点从上至下、从左至右顺序编号，按顺序存储在一维数组中。利用数组元素的下标值确定结点在二叉树中的位置以及结点之间的关系数组0123456789ABCDEGHIJF结点A:下标0左孩子B:下标为2×0+1=1

右孩子C:下标为

2×0+2=2

结点B:下标1左孩子D:下标为2×1+1=3

右孩子E:下标为2×1+2=4结点C:下标2左孩子F:下标为2×2+1=5

右孩子G:下标为2×2+2=6结点D:下标3左孩子H:下标为2×3+1=7

右孩子I:下标为2×3+2=8结点E:下标4左孩子J:下标为2×4+1=9

基于完全二叉树的顺序存储

对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，需要增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。存储改造二叉树为完全二叉树时，如需增加很多空结点，浪费空间，不宜顺序存储。最坏的情况是右单支树。插入和删除中间结点的操作复杂，会造成大量数据的移动，因此很少使用基于静态链表的顺序存储二叉链表：使用一维数组来存储二叉树的结点，而二叉树的结点除了存储本身信息外，还存储该结点左孩子、右孩子结点下标，这样的结点称为二叉链存储结构。(b)基于二叉链的二叉树顺序存储示意图

(c)基于三叉链的二叉树顺序存储示意图

三叉链表：使用一维数组来存储二叉树的结点，而二叉树的结点除了存储本身信息外，还存储该结点左孩子、右孩子、双亲结点的下标，这样的结点称为三叉链存储结构。data：数据域lchild：左孩子下标rchild：右孩子下标parent：双亲结点下标设计最优二叉树顺序存储结构的结点最优二叉树的数据结点包括3个数据域：weight用于存放该结点的权值name用于存放结点的字符名称code用于存放该字符对应的编码public

classHData{

private

int

weight; //结点权值

privateStringname; //结点数据,存放字符名称

privateStringcode; //存放结点的字符编码

publicHData(Stringname,int

weight){

this.weight=weight;

this.name=name;}//其他构造函数和set/get方法省略}public

classHNode{

private

int

lchild;//左孩子结点

private

int

rchild;//右孩子结点

private

int

parent;//父结点

privateHDatadata; //结点数据

//构造器

publicHNode(HDatadata){

this.setData(data);

this.lchild=-1;

this.rchild=-1;

this.parent=-1;}

publicHNode(){

this(null);}//省略get/se}

用三叉链构建最优二叉树顺序存储结构的结点：结点data域包含三个数据：weight、name、codelchild于存放该结点的左孩子结点在数组中的序号rchild存放该结点的右孩子结点在数组中的序号parent存放该结点的双亲结点在数组中的序号创建基于顺序存储结构的最优二叉树创建基于顺序存储结构的最优二叉树：创建类SeqHuffmanTree，定义2个类变量data和leafNum，data是类型为HNode一维数组，用来存储最优二叉树中的结点leafNum为整型，用来存放叶子结点数目。public

classHuffmanTree{

privateHNode[]data;//结点数组

private

int

leafNum;//叶子结点数目

……}在二叉树的顺序存储结构中，每个节点按层次依次填入数组，父节点的索引为i，则左子节点的索引为2i+1，右子节点的索引为2i+2。这种紧凑的布局，使得数据访问高效且易于管理，体现了计算机科学中的简洁之美。静态链表通过数组实现顺序存储，元素间以索引相连。无需动态申请内存，节省资源且管理简便。每个节点包含数据和指针，便于快速访问与操作，体现高效与秩序之美。步骤二：设计最优二叉树的基本操作通过分析，最优二叉树类中应该有以下功能：（1）voidcreate(Stringmessage):根据输入的报文字符串message，计算每个字符的出现频率（权值），然后创建一棵最优二叉树。（2）booleanisLeaf(HNodep):判断结点p是否是叶子结点。（3）inttraverse()：前序遍历二叉树，输出所有报文字符的编码，并输出总的报文编码长度。（4）search(HNodep,Stringname)：在二叉树上查找名称为name的结点。（5）Stringcodes(Stringmessage):对报文message进行编码。（6）Stringdecodes(Stringcodes):对编码报文codes解码成对应报文。最优二叉树的基本操作步骤三：编码实现最优二叉树的基本操作构建最优二叉树create(Stringmessage)对给定文本进行字符频次统计，根据统计信息构建最优二叉树（哈夫曼树），为字符编码（如哈夫曼编码）提供基础。文本预处理：通过String.trim()方法去除输入文本（message）的前后空格，并计算处理后的文本长度。字符频次统计：使用一个HashMap<Character,Integer>（charSet）来统计文本中每个字符出现的频次。遍历处理后的文本字符串，对于每个字符，如果它已经在charSet中，则增加其计数；否则，将其添加到charSet中并设置计数为1。初始化存储数组：根据统计得到的字符数量（leafNum），初始化一个HNode数组（data），大小为2*leafNum-1。这是因为在一个完全二叉树中，如果有n个叶子结点，那么总的结点数将是2n-1。这里，HNode是自定义的类，用于表示二叉树的结点，包含数据（这里为字符频次）、左右子结点引用以及父结点引用等。排序字符集：通过sortMapByValueKey方法，将字符及其频次按照频次（升序）和字符ASCII码（升序，作为次要排序条件）进行排序。这有助于后续构建哈夫曼树时，确保低频字符的编码更短，高频字符的编码更长，从而实现高效的数据压缩。创建静态链表：使用for循环来遍历sortedCharSet列表中的每个元素，分别获取当前键值对的键（字符）和值（频次，）创建一个HData对象，HData对象又被存储在HNode类型的数组中，以便于后续构建哈夫曼树。………………public

voidcreate(Stringmessage){Stringstr=message.trim();System.out.println("待处理的文本长度:"

+str.length());Map<Character,Integer>charSet=newHashMap<>();for(int

i=0;i<str.length();i++){char

key=str.charAt(i);if(charSet.containsKey(key)){int

v=charSet.get(key)+1;charSet.put(key,v);}

else{charSet.put(key,1);}}this.leafNum=charSet.size();System.out.println("待处理的字符数量:"

+leafNum);data=newHNode[this.leafNum*2-1];for(int

i=0;i<2*leafNum-1;i++)data[i]=newHNode();System.out.println("各个字符出现频次:");int

cnt=0;List<Map.Entry<Character,Integer>>sortedCharSet=sortMapByValueKey(charSet);for(Map.Entry<Character,Integer>item:sortedCharSet){char

key=item.getKey();int

v=item.getValue();HDatahd=newHData(key+"",v);data[cnt++].setData(hd);System.out.print(key+":"+v+"");}……………}构建最优二叉树create(Stringmessage)初始化变量：m1,m2用于存储当前找到的最小和次小权重。x1,x2用于存储对应权重最小和次小的结点的索引。循环构建过程：外层循环控制需要进行的合并次数。因为初始时有leafNum个叶子结点，每合并一次就减少一个叶子结点，所以需要合并leafNum-1次来构建完整的哈夫曼树。寻找最小和次小结点：在内层循环中，寻找权重最小的叶子结点（如果找到了权重更小的结子结点，则更新m1,x1），然后继续寻找次小的叶子结点（更新m2,x2），然后再检查是否还需要更新m2和x2。合并结点：计算合并后新结点的权重w，并创建一个新的HData对象来表示这个中间结结点。将新结点添加到data数组的下一个可用位置（this.leafNum+i），设置其左右子结点的索引为之前找到的两个最小权重结点的索引修改被合并的两个结点的父结点索引，指向新生成的中间结点。public

voidcreate(Stringmessage){

……………

System.out.println();int

m1,m2,x1,x2;for(int

i=0;i<this.leafNum-1;++i){m1=m2=Integer.MAX_VALUE;x1

=x2

=0;for(int

j=0;j<this.leafNum+i;++j){if((data[j].getData().getWeight()<m2)&&(data[j].getParent()==-1)){m2=data[j].getData().getWeight();x2=j;if(m2<m1){m2=m1;x2=x1;m1=data[j].getData().getWeight();x1=j;}}}int

w=data[x1].getData().getWeight()+

data[x2].getData().getWeight();

HDatahd=newHData("",w);data[this.leafNum+i].setData(hd);data[this.leafNum+i].setLchild(x1);data[this.leafNum+i].setRchild(x2);data[x1].setParent(this.leafNum+i);data[x2].setParent(this.lefNum+i);}……………}这些排序后的键值对存储在一个数组中，每个键值对都封装在一个HData对象中，这些HData对象又被存储在HNode类型的数组中，以便于后续构建哈夫曼树

排序方法sortMapByValueKey(Map<Character,Integer>map)在构建最优二叉树的过程中，使用了sortMapByValueKey的方法，它接收一个Map<Character,Integer>类型的参数map，并返回一个List<Map.Entry<Character,Integer>>类型的列表。这个列表包含了原始映射中所有的键值对，但根据特定的排序规则进行了排序。下面是这段代码的详细解释：创建列表：创建了一个新的ArrayList，并将其初始化为包含map中所有键值对的列表。排序列表：（1）使用Collections.sort()方法对列表进行排序。这个方法需要一个列表和一个比较器（Comparator）作为参数。在这个例子中，使用了一个Lambda表达式作为比较器。（2）Lambda表达式定义了排序规则，即首先按照键值对的值（Integer）进行升序排序。如果两个键值对的值相等，则按照它们的键（Character）的字典顺序进行排序。这是通过比较两个键值对的值之差（如果非零则直接决定顺序）以及当值相等时比较它们的键来实现的返回列表。返回结果：排序完成后的列表通过returnlist//对Map对象按value和key进行升序排序privateList<Map.Entry<Character,Integer>>sortMapByValueKey(Map<Character,Integer>map){List<Map.Entry<Character,Integer>>list=new

ArrayList<>(map.entrySet());Collections.sort(list,((o1,o2)->{int

x=o1.getValue()-o2.getValue();if(x!=0)return

x;//先按Value排序returno1.getKey().compareTo(o2.getKey());}));return

list;}在静态链表的精细构造中，依托顺序存储的坚实基础，匠心独运地构建起最优二叉树的框架。每个结点如同精心打磨的齿轮，彼此间严丝合缝，共同驱动着数据处理的引擎。它不仅是对技术能力的展现，更是对效率与优雅双重追求的体现。判断是否为叶结点isLeaf(HNodep)判断一个给定的结点p是否是叶结点检查结点是否为空：p!=null。这是非常重要的，因为如果p是null，那么尝试访问p.getLchild()或p.getRchild()将导致NullPointerException。这个检查确保了代码的健壮性。检查左孩子是否为空：p.getLchild()==-1。如果左孩子的引用是-1，则表示该结点没有左孩子。检查右孩子是否为空：p.getRchild()==-1。如果右孩子的引用是-1，则表示该结点没有右孩子。综合判断：如果上述三个条件都满足（即结点不为空，且没有左孩子和右孩子），则该函数返回true，表示该结点是一个叶子结点。否则，返回false。//判断结点p是否是叶子结点public

booleanisLeaf(HNodep){return((p!=null)&&(p.getLchild()==-1)&&(p.getRchild()==-1));}获得根结点getRoot()

从一个静态顺序存储结构中获取最优二叉树的根结点在静态链表的顺序存储结构中，根结点是存在数组最后一个位置，下标为2*leafNum-2，算法执行以下的操作：条件检查：检查是2*leafNum-2是否小于0，是的话，意味不是最优二叉树，returnnull。返回根结点：如果条件满足，则返回data数组中位于2*leafNum-2位置的元素。//获得最优二叉树的根结点publicHNodegetRoot(){if(2*leafNum-2<0)return

null;return

data[2*leafNum-2];}遍历二叉树traverse()通过在traverse方法中，调用前序遍历方法preOrder

，为每个结子结点分配一个唯一的二进制编码，并计算所有叶子结点编码的加权长度总和。preOrder方法如果当前结点不为空，进行如下操作：（1）将该结点的数据对象的编码设置为当前的code。

（2）如果当前结点是叶子结点（通过isLeaf(root)检查），则打印出该结点的名称和对应的编码，计算并返回该结点的权重与编码长度的乘积。（3）如果当前结点有左子结点，则递归调用preOrder方法，将左子结点作为新的根结点，并在当前编码后追加'0'，然后累加返回的加权编码长度到sum。

（4）如果当前结点有右子结点，则进行类似的操作，但这次追加的是"1"。

（5）返回从当前结点开始的所有叶子结点的加权编码长度之和。traverse方法（1）通过getRoot()方法获取树的根结点。（2）如果根结点为空，则返回0。（3）使用空字符串作为初始编码调用preOrder方法，并传入根结点。这将从根结点开始遍历整棵树，并计算所有叶子结点的加权编码长度总和。（4）返回计算得到的加权编码长度总和。private

intpreOrder(HNoderoot,Stringcode){int

sum=0;if(root!=null){root.getData().setCode(code);if

(isLeaf(root)){System.out.println(root.getData().getName()+":“

+root.getData().getCode());return

root.getData().getWeight()*

root.getData().getCode().length();}if(root.getLchild()!=-1){sum+=preOrder(data[root.getLchild()],code+"0");}if(root.getRchild()!=-1){sum+=preOrder(data[root.getRchild()],code+"1");}}return

sum;}public

inttraverse(){HNoderoot=getRoot();if(root==null){return0;}int

sum=preOrder(root,"");return

sum;}查找结点search(HNodep,Stringname)在一棵二叉树p中搜索一个具有指定名称（name）的结点，返回该结点的引用（HNode类型）。检查当前结点是否为空：如果当前结点p为空，说明已经遍历到了树的底部而没有找到指定名称的结点，因此方法返回null。检查当前结点是否为目标结点：通过比较当前结点p的数据对象（p.getData()）的名称（getName()方法返回的字符串）是否与指定的名称name相等来判断。如果相等，说明找到了目标结点，方法返回当前结点的引用p。在左子树中搜索：如果当前结点不是要找的结点，并且该结点有左子结点（通过p.getLchild()获取左子结点的索引，并检查该索引是否大于等于0，因为通常使用-1表示没有子结点），则递归地在左子树中搜索指定名称的结点。如果在左子树中找到了目标结点，方法将返回找到的结点的引用。在右子树中搜索：如果左子树中没有找到目标结点（即search方法返回了null），则检查当前结点是否有右子结点（同样通过p.getRchild()获取右子结点的索引，并检查）。如果有右子结点，则递归地在右子树中搜索指定名称的结点，并返回找到的结点的引用（如果找到的话）。返回null：如果左子树和右子树中都没有找到目标结点，则方法返回null，表示在整棵树中没有找到具有指定名称的结点。publicHNodesearch(HNodep,Stringname){

if(p==null)return

null;if(p.getData().getName().equals(name)){return

p;}if(p.getLchild()>=0){//存在左子树HNoderes=search(data[p.getLchild()],name);if(res!=null){//在左子树找到元素ves返回return

res;}}//左子树没找到，在右子树继续查找if(p.getRchild()>=0){//存在右子树returnsearch(data[p.getRchild()],name);}return

null;}文本编码codes(Stringmessage)将一个给定的字符串（message）转换为对应的哈夫曼编码（Huffmancoding）。初始化：使用StringBuilder对象sb来构建最终的编码字符串，因为它比字符串连接（+）在性能上更优，特别是在需要多次拼接字符串时。获取根结点：通过调用getRoot()方法获取哈夫曼树的根结点，这是进行后续搜索操作的起点。遍历消息字符串：通过for循环遍历message字符串中的每个字符。搜索字符结点：对于字符串中的每个字符c，将其转换为字符串（c+""）并作为参数传递给search方法。search方法将在哈夫曼树中搜索与该字符相对应的结点。这里假设search方法能够正确地找到结点，并且该结点有一个getData()方法来获取结点的数据对象，该数据对象有一个getCode()方法来返回结点的哈夫曼编码。拼接编码：将找到的结点的哈夫曼编码追加到StringBuilder对象sb中。这样，随着循环的进行，sb将构建出整个message字符串的哈夫曼编码。返回编码字符串：使用sb.toString()将StringBuilder对象转换为字符串，并返回这个字符串作为message的哈夫曼编码。publicStringcodes(Stringmessage){StringBuildersb=newStringBuilder();HNoderoot=getRoot();for(int

i=0;i<message.length();i++){char

c=message.charAt(i);HNodehn=search(root,c+"");sb.append(hn.getData().getCode());}return

sb.toString();}报文解码decodes(Stringcodes)解码一个由哈夫曼编码组成的字符串（codes），并将其转换回原始的文本字符串。初始化：使用一个队列q来保存待处理的哈夫曼树结点，队列初始时只包含根结点root。同时，初始化一个空字符串str来存储解码后的文本。层序遍历：通过一个while循环进行层序遍历，直到队列为空，即没有更多结点需要处理。结点匹配：在每次循环中，从队列中取出一个结点tmp。然后检查codes字符串是否以该结点的哈夫曼编码（tmp.getData().getCode()）开头。如果不是，则跳过该结点，继续处理下一个结点（如果有的话）。处理叶子结点：如果当前结点tmp是叶子结点（通过isLeaf(tmp)方法判断），则将叶子结点对应的数据（通常是字符）添加到str字符串中，并从codes字符串中移除已匹配的哈夫曼编码部分。如果codes字符串仍然包含剩余未处理的编码，则清空队列并重新从根结点开始遍历（这是一个不典型的做法，可能会导致性能问题）。子结点入队：如果当前结点有左子结点或右子结点，则将它们加入队列中以便后续处理。这里假设data是一个全局数组或类似结构，用于根据子结点的索引获取实际的结点对象。返回结果：如果codes字符串在遍历结束后仍然包含剩余未处理的编码，说明给定的哈夫曼编码字符串无法被完全解码（可能是由于错误的编码或树结构不完整），此时返回空字符串。否则，返回解码后的文本字符串str。publicStringdecodes(Stringcodes){Queue<HNode>q=newLinkedList<HNode>();HNoderoot=getRoot();q.add(root);Stringstr="";while(!q.isEmpty()){HNodetmp=q.poll();if(!codes.startsWith(tmp.getData().getCode()))continue;if(isLeaf(tmp)){str=str+tmp.getData().getName();codes=codes.substring(

tmp.getData().getCode().length());if(codes.length()>0){q.clear();q.add(root);continue;}}if(tmp.getLchild()!=-1){q.add(data[tmp.getLchild()]);}if(tmp.getRchild()!=-1){q.add(data[tmp.getRchild()]);}}return

codes.length()>0?"":str;}解码一个由哈夫曼编码组成的字符串（codes），并将其转换回原始的文本字符串。

在静态链表的精细构造中，依托顺序存储的坚实基础，匠心独运地构建起最优二叉树的框架。每个结点如同精心打磨的齿轮，彼此间严丝合缝，共同驱动着数据处理的引擎。它不仅是对技术能力的展现，更是对效率与优雅双重追求的体现。任务三

用链式存储实现二叉树学习目标熟悉二叉树的链式存储结构掌握二叉树的基本操作的链式实现方法12能应用二叉树的链式存储解决问题3

二叉树的顺序存储，寻找后代节点和祖先节点都非常方便，但对于普通的二叉树，顺序存储浪费大量的存储空间，同样也不利于节点的插入和删除。因此顺序存储一般用于存储完全二叉树，一般的二叉树通常用链式存储结构。本任务将二叉树的逻辑结构映射成链式存储结构，并基于链式存储结构实现二叉树的基本操作。。任务描述步骤一：将二叉树的逻辑结构映射成链式存储结构二叉链式存储结构二叉树的链式存储结构是用链表来表示一棵二叉树，即用链表来指示元素的逻辑关系。通常有二叉链表和三叉链表两种存储形式。二叉链式存储结构（二叉链表）：链表中每个结点由三个域组成：数据域、左孩子指针域、右孩子指针域，左右孩子指针域为该结点左孩子和右孩子的存储地址。data：数据域lchild：左孩子指针域rchild：右孩子指针域图中结点A的左孩子指针域、右孩子指针域分别存储了结点B和结点C的存储地址，而B结点只有左孩子，因此左孩子指针域存储了结点D的存储地址，而右孩子指针域则为空值。三叉链式存储结构三叉链式存储结构（三叉链表）：链表中每个结点由四个域组成：数据域、左孩子指针域、右孩子指针域、双亲结点指针域，左右孩子指针域为该结点左孩子和右孩子的存储地址,双亲结点指针域为该结点父结点的存储地址。data：数据域lchild：左孩子指针域rchild：右孩子指针域parent:双亲结点指针域图中根结点A的左孩子指针域、右孩子指针域分别存储了结点B和结点C的存储地址，而双亲结点指针域为空。而B结点只有左孩子，因此其左孩子指针域存储了左孩子结点D的存储地址，而右孩子指针域则为空值，双亲结点指针域则存储了父结点A的存储域址。

(a)一棵二叉树

(b)三叉链表链式存储结构基于二叉链式存储结构创建二叉树类（1）创建一个二叉链表或三叉链表的结点类Node<E>，表示链表的结点类型，成员变量：data是结点数据域，lchild与rchild分别存放指向左孩子和右孩子的指针，parent存放指向父结点的指针。public

classNode<E>{

privateEdata; //结点的数据

privateNode<E>lchild; //当前结点的左子树

privateNode<E>rchild; //当前结点的右子树

publicNode(Edata){

this(data,null,null);}

publicNode(Edata,Node<E>lchild,Node<E>rchild){

this.data=data;

this.lchild=lchild;

this.rchild=rchild;}

//此处省略get/set方法

@Override

publicStringtoString(){

return

"Node[data="+data+",lchild="+lchild+",rchild="+rchild+"]";}public

classNode<E>{

privateEdata; //结点的数据

privateNode<E>lchild; //当前结点的左子树

privateNode<E>rchild; //当前结点的右子树privateNode<E>parent; //当前结点的父结点

publicNode(Edata){

this(data,null,null);}publicNode(Edata,Node<E>lchild,Node<E>rchild,Node<E>parent){

this.data=data;

this.lchild=lchild;

this.rchild=rchild;this.parent=parent;}

//此处省略get/set方法

@Override

publicStringtoString(){

return

"Node[data="+data+",lchild="+lchild+",rchild="+rchild+",parent="+parent+"]";}}二叉链表结点虽不能直接寻双亲，但其结构灵活且操作便捷，是二叉树常用的存储方式。后续若无特别说明，二叉树的链式存储均指二叉链表结构。基于二叉链式存储结构创建二叉树类（2）创建一个链式二叉树类LinkedBiTree<E>，该类实现二叉树的抽象数据类型中定义的基本操作，基本操作的算法实现在步骤二完成。（3）在类定义LinkedBiTree<E>一个类变量root，指向二叉树的根结点。通过构造函数，使用参数e作为根结点的值来创建一个新的二叉树。（4）定义了一个方法getRoot()，返回二叉树的根结点。public

classLinkBiTree<E>{

privateNode<E>root;//根结点

publicLinkBiTree(Ee){

root=newNode<E>(e);}

publicNode<E>getRoot(){

return

root;}//……在后面逐步实现二叉树的基本操作}在编程的奇幻森林里，二叉树的链式存储结构犹如一条由智慧编织的藤蔓，其上的结点通过指针相互相连，让数据在动态变化中保持平衡与和谐。正如自然界中的藤蔓能够灵活适应各种环境，二叉树的链式存储结构也在算法的世界中展现出其独特的魅力和无限的可能性。步骤二：基于链式存储结构实现二叉树的基本操作建立二叉树生成一棵包含根结点和左右子树的二叉树。根据给定的值v和左右子树结点引用l、r，来创建或更新一棵二叉树的根结点root。public

voidcreate(Ev,Node<E>l,Node<E>r){//以v为根结点元素，l和r为左右子树构造二叉树

root=newNode<E>(v,l,r);

}图中，以A为根结点，B和C为左右子树，构建一棵二叉树。获取左子树定义一个方法getLchild，接收一个类型为Node<E>的参数p，并返回结点p的左子结点。publicNode<E>getLchild(Node<E>p){

return

p.getLchild();//获取p的左子树}图中，获取以A为根结点的左子树B。获取右子树publicNode<E>getRchild(Node<E>p){

return

p.getRchild();//获取p的右子树}图中，获取以A为根结点的右子树C。定义一个方法getRchild，接收一个类型为Node<E>的参数p，并返回结点p的右子结点。插入数据到左子树public

voidinsertL(Eval,Node<E>p){Node<E>node=newNode<E>(val);node.setLchild(p.getLchild());

p.setLchild(node);

}创建新结点：创建了一个新的结点node，并将其值设置为方法参数val指定的值。链接新结点：将新结点node的左子结点设置为原本p结点的左子结点。这意味着，如果p原本就有一个左子结点，那么这个左子结点现在变成了新结点node的左子结点。插入新结点：将p结点的左子结点设置为新创建的结点node。这样，新结点node就被成功地插入到了p结点的左子结点位置。在二叉树中，将一个新结点插入到给定结点p的左子结点位置如图（a）,将数据H构造的结点插入到以A为根结点的左子树，原左子树B成为结点H的左子树插入数据到右子树public

voidinsertL(Eval,Node<E>p){Node<E>node=newNode<E>(val);node.setRchild(p.getRchild());

p.setRchild(node);

}创建新结点：创建了一个新的结点node，并将其值设置为方法参数val指定的值。链接新结点：将新结点node的右子结点设置为原本p结点的右子结点。这意味着，如果p原本如有一个右子结点，那么这个右子结点现在变成了新结点node的右子结点。插入新结点：将p结点的右子结点设置为新创建的结点node。这样，新结点node就被成功地插入到了p结点的右子结点位置。在二叉树中，将一个新结点插入到给定结点p的右子结点位置如图（a）,将数据H构造的结点插入到以A为根结点的右子树，原右子树C成为结点H的右子树删除左子树publicNode<E>deleteL(Node<E>p){

if((p==null)||(p.getLchild()==null)){

return

null;

}

Node<E>tmp=p.getLchild();

p.setLchild(null);

return

tmp;}图中，删除根结点A的左子树，断开了以B为根结点的左子树与结点A的链接参数检查：首先，方法检查传入的结点p是否为null，或者p的左子结点（p.getLchild()）是否为null。如果任一条件为真，则方法直接返回null。保存左子结点：如果p不为null且p有一个左子结点，那么将p的左子结点引用（p.getLchild()）保存在局部变量tmp中。断开链接：将p的左子结点引用设置为null，在二叉树中从p结点删除了其左子树，返回删除的结点：返回之前保存的tmp引用，即被删除的左子结点的引用。删除并返回给定结点p的左子结点删除右子树publicNode<E>deleteR(Node<E>p){

if((p==null)||(p.getRchild()==null)){

return

null;

}

Node<E>tmp=p.getRchild();

p.setRchild(null);

return

tmp;}图中，删除根结点A的右子树，断开了以C为根结点的右子树与结点A的链接参数检查：首先，方法检查传入的结点p是否为null，或者p的右子结点（p.getRchild()）是否为null。如果任一条件为真，则方法直接返回null。保存右子结点：如果p不为null且p有一个右子结点，那么将p的右子结点引用（p.getRchild()）保存在局部变量tmp中。断开链接：将p的右子结点引用设置为null，在二叉树中从p结点删除了其右子树，返回删除的结点：返回之前保存的tmp引用，即被删除的右子结点的引用。删除并返回给定结点p的右子树遍历二叉树-先序遍历（DLR）public

voidpreOrder(Node<E>p){

if(p!=null){

//访问根结点System.out.print(p.getData()+""//递归先序遍历左子树preOrder(p.getLchild());

//递归先序遍历右子树

preOrder(p.getRchild()); }}检查根结点：首先，方法检查传入的结点p是否为null。如果p为null，则不执行任何操作。访问根结点：如果p不为null，则首先访问（或打印）根结点的值。这是通过调用p.getData()获取根结点的值，并使用System.out.print()将其输出到控制台。递归遍历左子树：然后，方法通过调用preOrder(p.getLchild())递归地对左子树进行先序遍历。这一步是深度优先遍历的体现，即先尽可能深地遍历左子树。递归遍历右子树：在左子树遍历完成后，方法通过调用preOrder(p.getRchild())递归地对右子树进行先序遍历。注意，这一步是在左子树遍历完成后进行的，这符合先序遍历的定义。先序遍历遍历二叉树中每个结点：首先访问根结点，然后递归地先序遍历左子树，最后递归地先序遍历右子树。遍历二叉树-中序遍历（LDR）public

voidinOrder(Node<E>p){

if(p!=null){

//递归中序遍历左子树inOrder(p.getLchild());

//访问根结点

System.out.print(p.getData()+"");

//递归中序遍历右子树inOrder(p.getRchild());}}检查根结点：方法首先检查传入的结点p是否为null。如果p为null，则不执行任何操作。递归遍历左子树：如果p不为null，则方法首先通过调用inOrder(p.getLchild())递归地对左子树进行中序遍历。这是中序遍历的第一步，即首先遍历完左子树的所有结点。访问根结点：在左子树遍历完成后，方法会访问（或打印）当前结点p的值。这是通过调用p.getData()获取结点的值，并使用System.out.print()将其输出到控制台。递归遍历右子树：最后，方法通过调用inOrder(p.getRchild())递归地对右子树进行中序遍历。这一步是在访问了根结点之后进行的，符合中序遍历的定义。中序遍历遍历二叉树中每个结点：首先递归地中序遍历左子树，然后访问根结点，最后递归地中序遍历右子树。

""

遍历二叉树-后序遍历（LRD）public

void

postOrder(Node<E>p){

if(p!=null){

//递归后序遍历左子树

postOrder(p.getLchild());

//递归后序遍历右子树

postOrder(p.getRchild());//访问根结点

System.out.print(p.getData()+"");

}}检查根结点：方法首先检查传入的结点p是否为null。如果p为null，则不执行任何操作。递归遍历左子树：如果p不为null，则方法首先通过调用postOrder(p.getLchild())递归地对左子树进行后序遍历。这是后序遍历的第一步，即先遍历完左子树的所有结点。递归遍历右子树：接下来，方法通过调用postOrder(p.getRchild())递归地对右子树进行后序遍历。这一步是在遍历完左子树之后进行的。访问根结点：在左右子树都被遍历完之后，方法会访问（或打印）当前结点p的值。这是通过调用p.getData()获取结点的值，并使用System.out.print()将其输出到控制台。这是后序遍历的最后一步。后序遍历遍历二叉树中每个结点：首先递归地遍历左子树，然后递归地遍历右子树，最后访问根结点。

""

遍历二叉树-层序遍历public

void

levelOrder(Node<E>p){if(p==null){

return;}

//设置一个队列保存层序遍历的结点

Queue<Node<E>>q=newLinkedList<Node<E>>();

//根结点入队

q.add(p);

//队列非空，结点没有处理完

while(!q.isEmpty()){

//结点出队

Node<E>tmp=q.poll();

//访问当前结点System.out.print(tmp.getData()+"");

if(tmp.getLchild()!=null){//将当前结点的左孩子结点入队

q.add(tmp.getLchild())}

if(tmp.getRchild()!=null){

//将当前结点的右孩子结点入队

q.add(tmp.getRchild());} }}参数检查：首先检查传入的根结点p是否为空。如果为空，则直接返回，因为空树不需要进行遍历。队列初始化：创建一个Queue<Node<E>>类型的队列q，并使用LinkedList<Node<E>>作为队列的实现。这个队列用于存储待处理的结点，以实现逐层访问。根结点入队：将根结点p加入队列q。这是层序遍历的起始点。遍历过程：使用一个while循环来遍历队列中的结点，直到队列为空。在循环内部，执行以下步骤：结点出队：从队列q中移除并返回队首元素（即当前层最左边的结点），赋值给临时变量tmp。访问结点：通过System.out.print(tmp.getData()+"");）访问当前结点的数据。子结点入队：如果当前结点的左孩子（tmp.getLchild()）不为空，则将其加入队列。接着，如果右孩子（tmp.getRchild()）也不为空，则同样将其加入队列。这样，下一轮循环时，队列中的结点就是当前层所有结点的子结点，从而实现了逐层遍历。结束遍历：当队列为空时，所有结点都被访问过，遍历结束。层次遍历是按照二叉树的层级从上到下、从左到右依次访问每个结点的遍历方式。

""

查找结点publicNode<E>search(Node<E>p,Ev){

//如果p为空或p是要找的元素，返回

if(p==null||p.getData().equals(v)){

return

p;}Node<E>res=search(p.getLchild(),v);

if(res!=null){//在左子树找到元素v返回

return

res;}

//左子树没找到，在右子树继续查找

returnsearch(p.getRchild(),v);}图中，以先序遍历查找元素为F的结点基本情况检查：首先，方法检查传入的结点p是否为null。如果是，说明已经遍历到了树的末端而没有找到目标结点，因此返回null。然后，检查p结点的值是否与目标值v相等。如果相等，说明找到了目标结点，因此返回p。递归查找左子树：如果当前结点p不是要找的结点，则方法会递归地在其左子树中查找目标值v。这是通过调用search(p.getLchild(),v)实现的，其中p.getLchild()返回p结点的左子结点。如果左子树中存在目标值，则递归调用会返回该结点，此时外层调用也会立即返回这个结点。递归查找右子树：如果左子树中没有找到目标值（即search(p.getLchild(),v)返回了null），则方法会继续在其右子树中查找。这是通过调用search(p.getRchild(),v)实现的（注意这里假设getRchild()是访问右子结点的方法的正确名称，尽管之前的描述中可能有一个笔误）。返回值：方法最终会返回找到的结点（如果找到的话），或者如果遍历了整个树都没有找到目标值，则返回null。在二叉树中查找特定值的结点在静态链表的精细构造中，依托顺序存储的坚实基础，匠心独运地构建起最优二叉树的框架。每个结点如同精心打磨的齿轮，彼此间严丝合缝，共同驱动着数据处理的引擎。它不仅是对技术能力的展现，更是对效率与优雅双重追求的体现。任务四

用链式存储结构设计最优二叉树学习目标能在实际问题中识别二叉链表的结构能针对具体问题构建对应的最优二叉树12掌握应用最优二叉树解决问题的方法3

基于二叉链表的思想构建最优二叉树，对待压缩的文本进行编码压缩，并输出压缩后每个字符对应的编码，然后计算压缩后文本的总长度。任务描述步骤一：用链式存储结构设计最优二叉树设计最优二叉树的数据结点最优二叉树采用二叉链表进行构造，数据结点包括3个数据域：weight用于存放该结点的权值，name用于存放结点的字符名称，code用于存放该字符对应的编码。public

classHData{

private

int

weight; //结点权值

privateStringname; //结点数据,存放字符名称

privateStringcode; //存放结点的字符编码

publicHData(Stringname,int

weight){

this.weight=weight;

this.name=name;}//其他构造函数和set/get方法省略}最优二叉树结点结构最优二叉树的结点存储结构采用前面定义的二叉链表结点类Node<HData>。创建基于二叉链式存储结构的最优二叉树根结点(root):这是一个类型为Node<HData>的私有成员变量，代表哈夫曼树的根结点。Node<HData>用于表示树中的结点，其中HData是一个封装了数据的类。根结点是访问和操作整棵哈夫曼树的入口点。优先级队列(queue):是一个类型为PriorityQueue<Node<HData>>的私有成员变量，用于在构建哈夫曼树的过程中存储结点。PriorityQueue是一个基于优先级堆的无界优先级队列，元素在后面通过比较器Comparator进行排序。在哈夫曼树的构建过程中，结点按照它们的权值被添加到这个队列中，每次从队列中取出两个权值最小的结点来合并成一个新的结点，直到队列中只剩下一个结点，即根结点。队列的使用使得每次都能高效地找到并移除两个权值最小的结点public

class

LinkedHuffmanTree{//最优二叉树的根结点

privateNode<HData>root;//优先级队列

privatePriorityQueue<Node<HData>>queue;

......}创建类LinkedHuffmanTree，定义了两个变量：

构建优先级队列比较器PriorityQueue<Node<HData>> queue=newPriorityQueue<>(newComparator<Node<HData>>(){

@Override

public

intcompare(Node<HData>n1,Node<HData>n2){

//按权值从小到大排序

int

x1=n1.getData().getWeight()-n2.getData().getWeight()