数据结构（Java语言版）课件 第七章 树与二叉树

数据结构（Java语言版）07树与二叉树【知识目标】²

掌握树的定义、表示方法和存储结构；²

掌握二叉树的定义、性质和存储结构；²

掌握完全二叉树和满二叉树的概念；²

掌握二叉树的前序遍历、中序遍历、后序遍历和层次遍历算法；²

掌握线索二叉树的基本概念；²

理解树与二叉树的转换、树的遍历；²

掌握二叉排序树的基本概念、二叉排序树的创建及查找算法；²

了解哈夫曼树和哈夫曼编码的基本概念，掌握哈夫曼编码的设计方法；²

了解决策树的概念、方法及用途。【能力目标】²

提升编写递归函数的能力；²

具备运用二叉排序树实现查找的能力；²

具备运用哈夫曼树实现对字符进行编码的能力；²

初步具备运用决策树实现项目进度决策、投资决策的能力。实例引入:系部结构示意图。(层次关系)

河北石油计算机工程系机械工程系电子工程系机制软件网络媒体化机焊接电子检测测控树结构图树（Tree）是由n（n≥0）个节点构成的有限集合。节点数为0的树称为空树，节点数大于0的树称为非空树。在任何一棵非空树中：

(1)有且仅有一个特定的根节点。

(2)当n>1时，除根节点外的其余节点可分为m（m>0）个互不相交的子集T1，T2，…，Tm，其中每个子集Ti本身又是一棵树。

树的定义

(1)有且仅有一个的根节点。(2)根节点外的其余节点可分为m个互不相交的子树。树的定义ABF

DEGICHKA树非树树的特点树具有两个特点：（1）树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。（2）树中所有结点可以有零个或多个后继结点。

ABFK

DEGCHLJI树的相关术语ABFK

DEGICHLJB结点的度：结点所拥有的子树的个数称为该结点的度。例如：A的度为3树的度：树中结点度的最大值。树的相关术语结点：一个数据元素及若干个指向其子树的分支。ABFK

DEGICHLJ

叶子结点：度为0的结点。

分支结点：度不为0的结点。孩子、双亲和兄弟结点：某结点的子树的根称为该结点的孩子。相应地，该结点称为孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。树的相关术语节点的层次数：规定树的根节点的层次数为1，其余节点的层次数等于它的双亲节点的层次数加1。如G的层次数是3。树的相关术语ABFM

DEGICHLJ树的深度：树中所有结点的最大层数称为树的深度。图中树深度为4。树的相关术语树的相关术语有序树和无序树：如果一棵树中结点的各子树从左到右是有次序的—有序树；反之，—无序树。森林：m（m≥0）棵互不相交的树的集合称为森林。HIJLKFEDCG森林树的表示有四种方法：直观表示法、凹入表示法、嵌套集合表示法、广义表表示法。

A

BCEDFHGIABDEHFCGIABEHCDIG嵌套集合表示法凹入表示法直观表示法F树的表示：(A(B(D,E(H),F),C(G(I))))

广义表表示法(兄弟逗号分隔，孩子括号括起)

ABEHCDIG直观表示法F树的表示：树的表示有四种方法：直观表示法、凹入表示法、嵌套集合表示法、广义表表示法。树的表示有四种方法：直观表示法、凹入表示法、嵌套集合表示法、广义表表示法。ABDEHFCGI凹入表示法树的表示：树的表示有四种方法：直观表示法、凹入表示法、嵌套集合表示法、广义表表示法。

A

BCEDFHGI嵌套集合表示法树的表示：树的表示有四种方法：直观表示法、凹入表示法、嵌套集合表示法、广义表表示法。树的表示：(A(B(D,E(H),F),C(G(I))))

广义表表示法(兄弟逗号分隔，孩子括号括起)

二叉树定义：二叉树是n个（n≥0）节点的集合，该集合或者为空、或者由一个根节点和两个分别称为左子树和右子树的互不相交的二叉树组成，当集合为空时，称为空二叉树。二叉树具有五种基本形态：左子树右子树左子树右子树(b)仅有根节点(c)右子树为空(d)左子树为空(e)左右子树均不为空有序(a)空二叉树二叉树的概念与性质：性质1：二叉树的第i（i≥1）层上最多有2i-1个节点。每个节点最多有两个子树，每层节点数构成等比为2的等比数列。第一层为根20个；第二层最多有21个；以此类推，第i层上最多只有2i-1个节点。

ABCDEGFHIKJMLNO152346789101112131415二叉树的重要性质：性质2：在一棵深度为k的二叉树中，最多具有2k－1个节点。

ABFEC

证明：等比数列求和公式

a1为首项，q为公比，Sn为前n项和。ABFECHG二叉树的重要性质：ABFEC性质3对于一棵非空的二叉树，如果叶子节点数为n0，度数为2的节点数为n2，则有:n0＝n2＋1。G二叉树的重要性质：证明：设度为i的节点有ni

个(其中：i=0，1，2)，总节点个数为n，总分支数为e，则根据二叉树的定义，有如下的式子：

n=n0+n1+n2

e=2n2+n1=n–1(除根节点外，每个节点都有分支进入)将两式结合即有：n0=n2+1

ABFEC性质3

对于一棵非空的二叉树，如果叶子节点数为n0，度数为2的节点数为n2，则有:n0＝n2＋1。G二叉树的重要性质：一棵深度为k且有2k－1个节点的二叉树称为满二叉树。

ABFECABFECHGABFECG满二叉树：1）每一层上的节点数都达到最大值，即对给定的高度，它是节点数最多的二叉树。2）不存在度数为1的节点，每个分支节点均有两棵高度相同的子树，且叶子节点都在最下面一层上。ABFECHG满足如下两条的树为满二叉树1.所有叶子节点的层数相同2.非叶子节点的度都为2满二叉树的特点：ACBEDFGHIJ1243576

8910(b)完全二叉树ACBEDFGHIJ1243576

8910LM

1213NO1415K11(a)满二叉树(c)非完全二叉树ACBEDFGHIJ1243576

8910完全二叉树为二叉树的节点从上至下由左至右进行编号，当且仅当其每个节点的编号与相应满二叉树节点顺序编号从1~n互相对应时，则称此二叉树为完全二叉树。ACBEDFGHIJ1243576

8910(b)完全二叉树ACBEDFGHIJ1243576

8910LM

1213NO1415K11(a)满二叉树只有将满二叉树的最下层的节点，从最右节点开始连续往左删去若干个节点后得到的二叉树才是一棵完全二叉树。完全二叉树ACBEDFGHIJ1243576

8910(b)完全二叉树(c)非完全二叉树ACBEDFGHIJ1243576

8910满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。在完全二叉树中，度为1的节点最多有一个，该节点缺少右孩子且左孩子是树中最后一个节点。完全二叉树

性质4对于具有n个节点的完全二叉树，如果按照从上至下和从左到右的顺序对所有节点从1开始顺序编号，则对于任意的序号为i的节点有：

(1)若i=1则该节点为根节点i，无双亲；

(2)若i＞1,则

i节点的双亲为i/2向下取整；

(3)某节点i的左孩子为2i（2i≤n即保证2i存在）

，右孩子为2i+1（2i+1≤n）。ACBEDFG1243576二叉树的重要性质：

二叉树存储结构：顺序存储结构和链式存储结构。

顺序存储结构（针对完全二叉树和满二叉树）把所有节点按照一定的顺序存放到一维数组中，让节点的编号与数组元素的下标对应。

节点在数组中的位置隐含了节点之间的关系。ABCDEFGHIJ12345678910

ACBEDFGHIJ1243576

8910数组下标从1开始二叉树的存储结构：ABCDE12345ACBDE12345二叉树的存储结构：ACBDE1245ABC^DE12345对于完全二叉树和满二叉树采用顺序存储非常适合，但一般的二叉树由于节点的编号不同于完全二叉树，所以存储后数组下标不能体现节点的逻辑关系，因此一般的二叉树用链式存储。ABCDEFHIJ123456789ACBEDFHIJ124356

789D节点的存储位置为4，但位置为8的节点I并非其左孩子二叉树的存储结构：

用链表的形式来存储二叉树，即用指针来指示元素之间的逻辑关系。最常用的有二叉链表和三叉链表。

1.二叉链表存储

每个节点由三个域组成，一个数据域和两个指针域。两个指针lchild和rchild分别指向其左孩子和右孩子节点。lchilddatarchild二叉树的存储结构链式存储结构：2.三叉链表存储

每个节点由四个域组成，具体结构如图所示：

parent为指向该节点双亲节点的指针。

这种存储结构既便于查找孩子节点，又便于查找双亲节点；但相对于二叉链表，它增加了空间开销。二叉树的存储结构lchilddatarchildparentABDCEFG二叉树A

^D

^E^

^F^

^G^bt二叉链表

A^

B^

C^D

^E^

^F^

^G^bt三叉链表C^B二叉树的存储结构二叉树节点类的定义ABDCEFG二叉树lchilddatarchild二叉链表的节点类

二叉树的遍历是指按照某种顺序访问树中的每个节点，并且每个节点仅被访问一次的过程。一棵二叉树是由根节点、左子树和右子树三部分组成。若以N、L、R分别表示访问根节点、遍历根节点的左子树、遍历根节点的右子树，可以有三种遍历方式，即NLR（先序）、LNR（中序）和LRN（后序）。ABFEC第五节：二叉树的遍历1．先序遍历先序遍历是一个递归的过程：若二叉树为空，遍历结束。否则（1）访问根节点；（2）先序遍历左子树；（3）先序遍历右子树。ABFECABEFC第五节：二叉树的遍历2．中序遍历若二叉树为空，遍历结束。否则（1）中序遍历左子树；（2）访问根节点；（3）中序遍历右子树。ABFECEBFAC第五节：二叉树的遍历3．后序遍历若二叉树为空，遍历结束。否则（1）后序遍历左子树；（2）后序遍历右子树。（3）访问根节点；ABFEC

EFBCA第五节：二叉树的遍历例题1:写出如图二叉树的先序，中序，后序遍历的序列ABFECHGIJ先序: ABEIFCGHJ中序:EIBFAGCJH后序:IEFBGJHCA例题2:写出如图二叉树的先序，中序，后序遍历的序列先序: 0137849256中序:7381940526后序:7839415620例:写出如图二叉树的先序，中序，后序遍历的序列先序: 12453中序:42513后序:45231二叉树的遍历算法1．先序遍历

a、若二叉树为空，遍历结束。b、否则（1）访问根节点；（2）先序遍历左子树；（3）先序遍历右子树。ABFECABEFC先序遍历算法publicvoidpreorder(TreeNoderoot1){//先序if(root1!=null){

System.out.println(root1.data);

if(root1.left!=null)

preorder(root1.left);

if(root1.right!=null)

preorder(root1.right);}}

publicvoidpreorder(){preorder(root);}先序遍历算法

publicvoidinorder(TreeNoderoot1){//中序if(root1!=null){if(root1.left!=null)

inorder(root1.left);System.out.println(root1.data);

if(root1.right!=null)

inorder(root1.right);}}中序遍历算法

publicvoidpostorder(TreeNoderoot1){//后序if(root1!=null){if(root1.left!=null)postorder(root1.left);

if(root1.right!=null)

postorder(root1.right);

System.out.println(root1.data);}}后序遍历算法4．按层次遍历二叉树

从二叉树的第一层开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对节点逐个访问。图所示的二叉树，按层次遍历所得到的结果序列为：ABCDEG。

ABEDCG层次遍历的实现层次遍历实现：设置一个队列，从二叉树的根节点开始，首先将根节点入队列，然后反复执行下面两个操作，直到队列空为止。

ABEDCG

(1)从队头取出一个元素，每取一个元素，访问该节点；

(2)若该元素所指节点的左、右孩子节点非空，则将该元素的左孩子和右孩子顺序入队。层次遍历的实现ABEDCGAABCBCDCEDDEGEGG层次遍历的实现classQueueNode{

TreeNodedata;QueueNodenext=null;}

ABEDCGABC链队列节点类？

层次遍历的实现classLinkQueue{

QueueNoderear=null;

QueueNodefront=null;publicbooleanempty(){return(rear==null&&front==null);}

∧∧frontrear层次遍历的实现publicvoidput(QueueNodeqn){//入队if(empty())front=rear=qn;else{rear.next=qn;rear=qn;}}frontrear

y

∧

x

元素y入队qn

∧frontrear

x∧qn元素x入队层次遍历的实现publicQueueNoderemove(){//出队if(empty()){

System.out.println("此队为空，不能出队！");

returnnull;}else{System.out.println(front.data.data);QueueNodefront1=front;

front=front.next;

if(front==null)

rear=null;

returnfront1;}}层次遍历实现：设置一个队列，从二叉树的根节点开始，首先将根节点入队列，然后反复执行下面两个操作，直到队列空为止。

ABEDCG

(1)从队头取出一个元素，每取一个元素，访问该节点；

(2)若该元素所指节点的左、右孩子节点非空，则将该元素的左孩子和右孩子顺序入队。层次遍历的实现层次遍历的实现publicvoidlevelOrderStack(TreeNodep){

if(p!=null){

LinkQueuequeue=newLinkQueue();QueueNodea=newQueueNode();a.data=p;queue.put(a);while(!queue.empty()){QueueNodetemp=queue.remove();

层次遍历的实现if(temp.data.left!=null){QueueNodeb=newQueueNode();b.data=temp.data.left;queue.put(b);}if(temp.data.right!=null){QueueNodec=newQueueNode();c.data=temp.data.right;queue.put(c);}}}第六节线索二叉树7.6.1线索二叉树的定义以某种方式对二叉树进行遍历，可以得到节点的一个线性序列。这使得每个节点在遍历后的序列中有唯一的前驱与后继。遍历是树形结构线性化的一个过程。

ABEDCG第六节线索二叉树7.6.1线索二叉树的定义使用二叉链表存储二叉树时，利用二叉链表存储结构中的闲置的指针域来指示该节点的前驱和后继，把指向前驱或后继的信息称为线索，加了线索的二叉链表存储的二叉树称为线索二叉树。

2．线索二叉树的结构

n个节点的二叉链表中有2n个指针域，但n＋1个指针域被闲置。因此，当节点有左右孩子时，指针域仍指向该节点左、右孩子。当节点无左孩子时，令其左指针域指向其直接前驱节点；当该节点无右孩子时，令其右指针域指向其直接后继节点。

2．线索二叉树的结构为了区别指针是指向其前驱后继还是指向左右孩子，需在原节点结构中增设两个标志位Ltag和Rtag。这样节点的结构为：lchildLtagdataRtagrchild

0lchild指向节点的左孩子

1lchild指向节点的直接前驱节点

0rchild指向节点的右孩子

1rchild指向节点的直接后继节点

Ltag＝Ltag＝lchildLtagdataRtagrchild

2．线索二叉树的结构，写出其中序遍历序列？

0A0

0B1

0C0^1D0

1E1

1F1^

1G1lchildLtagdataRtagrchildABEDCGFD无前驱中序遍历序列：DGBAECF树的三种存储结构

1．双亲表示法树中每个节点（除根）只有唯一的一个双亲节点，用一维数组来存储一个一般的树，节点包括数据元素及其双亲节点在数组中的序号。节点类为：

classPtNode{chardata；

intparent；

}ABCDEFGHIJ01201723456A-1B0C0D1E1F2I2J2G4H489Dataparent双亲表示法的缺点查找某个节点的双亲节点较为容易，但要查找某一个节点的孩子时，则要访问整个数组。C节点的孩子，从头查询parent为2的节点01723456A-1B0C0D1E1F2I2J2G4H489DataparentABCDEFGHIJ0122．孩子链表表示法数组元素中提供指针域指向该节点的最左边孩子，并把该节点的所有孩子用链表连接，构成一个单链表。单链表的节点由两个域组成，一个存放孩子节点在一维数组中的序号（防止有重复节点），另一个域指向下一个孩子。12∧34∧589∧01723456ABCD∧EF∧I∧J∧G∧H∧67∧98ABCDEFGHIJ这种存储方式对节点孩子的查询非常方便，但查询节点的双亲比较麻烦

A∧∧G..∧H∧

B

C∧∧D

E∧∧F∧I∧J∧3．孩子－兄弟表示法节点结构：一个数据域和两个指针域，其中一个指针指向它的第一个孩子节点，另一个指针指向它的兄弟节点。ABCDEFGHIJ森林：m（m≥0）棵互不相交的树的集合称为森林。HIJLKFEDCG树的相关术语

树与二叉树的转换

1．一般树转换为二叉树（将兄弟转换为子孙）（1）连线：在各兄弟之间用虚线相连。（2）抹线：对树中的每个节点，只保留它与第一个孩子节点之间的连线，删去它与其它孩子节点之间的连线。（3）旋转：将节点旋转相应的度角（45），使之结构层次分明。（转化完毕根只有左子树）AABCDEFGHABCDEFGHBCDEFGHABCDEFGH

树与二叉树的转换

2．森林转换为二叉树（1）将森林中的每棵树转换成相应的二叉树，形成二叉树的森林。（2）按森林中的先后顺序，依次把后一棵二叉树的根节点作为前一棵二叉树根节点的右孩子。

森林与二叉树的转换

HIJLKFEDCBAHIFEDCBAKJLGG(a)一般树的森林(b)二叉树的森林ABCLJKFEIHDG(c)最终的二叉树

森林与二叉树的转换

哈夫曼树及其应用

哈夫曼（Huffman）树，也称最优二叉树，是指一类带权路径最短的树。1．哈夫曼树的基本概念（1）路径、路径长度：从树中一个节点到另一个节点之间的分支构成两个节点间的路径，路径上的分支数目称为路径长度。（2）树的路径长度：根节点到树中每个节点的路径长度之和。

ABEDCGF哈夫曼树及其应用

（3）节点的带权路径长度：从根节点到该节点的路径长度与该节点所带的权值的乘积。（4）树的带权路径长度：树中所有叶子节点的带权路径长度之和。记为：

ABEDCGF457（5）哈夫曼树：设有n个权值{W1，W2，…，Wn}，构造一个具有n个叶子节点的二叉树，每个叶子节点带有权值Wi，在所有的二叉树中，带权路径长度WPL最小的二叉树称为哈夫曼树。用{3，4，5，6，8}为叶子权值构造如下二叉树，判断哪棵为哈夫曼树？(c)4ED68BA34C5(b)24AB34CE56D8(a)CDAB3458E6哈夫曼树WPL=65WPL=59WPL=812．思考任何构造哈夫曼树？一棵二叉树要使其WPL值最小，所以必须使权值越大的叶子节点越靠近根节点。使权值越小的叶子节点越远离根节点。已知n个权值，用这n个权值作n个叶子节点的权值构造一棵含有n个叶子节点的二叉树，使其叶子的权值与路径长度的乘积的和最小。2．构造哈夫曼树（1）用给定的n个权值