数据结构(java)-第6章树与二叉树

1、基本内容1.树的定义和基本术语树的定义和基本术语 第第6章章 树与二叉树树与二叉树 2.二叉树二叉树 3.遍历二叉树和线索二叉树遍历二叉树和线索二叉树 4.树和森林树和森林 5.哈夫曼树及其应用哈夫曼树及其应用 NEXT Neusoft1.树的定义树的定义树（树（tree）是由）是由n(n0)个有限数据元素组成的数据集合，其中个有限数据元素组成的数据集合，其中数据元素被称为结点。同时，树还必须满足以下数据元素被称为结点。同时，树还必须满足以下两个条件两个条件： 在树中有一个特殊的结点被称为根结点，它只有后继结点，在树中有一个特殊的结点被称为根结点，它只有后继结点，没有前驱结点。没有前驱结点。1

2、. 除根结点以外，其余结点可以分为除根结点以外，其余结点可以分为m（m0）个互不相交的）个互不相交的集合集合T1，T2，Tm，其中每一个集合，其中每一个集合Ti（1im）本身）本身又是一棵树。树又是一棵树。树T1，T2，Tm称为根结点的子树。称为根结点的子树。一.树的定义和基本术语 NEXT Neusoft1.树的定义树的定义一.树的定义和基本术语 ACDBFEIGHNEXT Neusoft2. 基本术语基本术语 1）双亲结点、子结点、兄弟结点双亲结点、子结点、兄弟结点 如图如图6.2中，中，B结点为结点为E结点的双亲结点；结点的双亲结点；A结点为结点为D结点的双亲结点；结点的双亲结点；D结点

3、结点为为I结点的双亲结点结点的双亲结点 如图如图6.2中，中，E结点为结点为B结点的子结点；结点的子结点；D结点为结点为A结点的子结点；结点的子结点；H结点为结点为D结点的子结点结点的子结点 如图如图6.2中，中，B结点和结点和C、D结点互为兄弟结点；结点结点互为兄弟结点；结点G和和H不为兄弟结点。不为兄弟结点。 2）叶子结点叶子结点没有后继的结点称为叶子结点，如图没有后继的结点称为叶子结点，如图6.2中的中的E、F、G、H、I结点。结点。一.树的定义和基本术语 NEXT Neusoft2. 基本术语基本术语 3）结点的度结点的度结点的度是结点所拥有的子树的棵数。如图结点的度是结点所拥有的子树

4、的棵数。如图6.2中，中，A结点的度为结点的度为3；C结点结点的度为的度为1；H结点的度为结点的度为0；4）树的度树的度树的度是指树中各个结点度的最大值。如图树的度是指树中各个结点度的最大值。如图6.2中，由于中，由于A结点的度为结点的度为3，其，其余结点的度都小于余结点的度都小于3，所以图，所以图6.2中树的度为中树的度为3。5）结点的层次结点的层次约定根结点的层次为约定根结点的层次为1，其余结点的层次都是在其双亲结点层次上加，其余结点的层次都是在其双亲结点层次上加1。如。如图图6.2中，中，B结点的双亲结点为根结点结点的双亲结点为根结点A，根结点，根结点A的层次为的层次为1，所以，所以B结

5、结点的层次为点的层次为2；同理，；同理，E结点与结点与F结点的层次是相同的，都为结点的层次是相同的，都为3。一.树的定义和基本术语 NEXT Neusoft2. 基本术语基本术语 6）树的高度树的高度树的高度是指树中结点的最大层次数。如图树的高度是指树中结点的最大层次数。如图6.2中，由于结点中，由于结点E、F、G、H、I的层次数都为的层次数都为3，其余结点的层次数都小于，其余结点的层次数都小于3，所以图，所以图6.2中树的高度为中树的高度为3。7）森林森林森林是森林是m（m0）棵互不相交的树的集合。如图）棵互不相交的树的集合。如图6.3即为一个森林。即为一个森林。一.树的定义和基本术语 CD

6、BFEIGHNEXT Neusoft1.定义定义 二叉树二叉树（binary tree）是）是n(n0)个结点组成的有限集合，并且每个结点最个结点组成的有限集合，并且每个结点最多有两棵子树。多有两棵子树。当当n=0时，二叉树被称为空二叉树时，二叉树被称为空二叉树 二叉树有以下五种基本形态：二叉树有以下五种基本形态：空二叉树，如图空二叉树，如图6.4所示；所示；只有根结点的二叉树，如图只有根结点的二叉树，如图6.5所示；所示；只有根结点和左子树的二叉树，如图只有根结点和左子树的二叉树，如图6.6所示；所示；只有根结点和右子树的二叉树，如图只有根结点和右子树的二叉树，如图6.7所示；所示；有根结点

7、、左子树和右子树的二叉树，如图有根结点、左子树和右子树的二叉树，如图6.8所示；所示；二.二叉树NEXT Neusoft2.满二叉树满二叉树 满二叉树满二叉树是指除了叶子结点以外所有结点都存在左子树和右子树，并且所有是指除了叶子结点以外所有结点都存在左子树和右子树，并且所有叶子结点都在同一层上的二叉树。下图是一棵满二叉树。叶子结点都在同一层上的二叉树。下图是一棵满二叉树。 二.二叉树ACBEDGFNEXT Neusoft3.完全二叉树完全二叉树 完全二叉树完全二叉树是指叶子结点只出现在最下层和次下层，且最下层的叶子结点集是指叶子结点只出现在最下层和次下层，且最下层的叶子结点集中在树的左部的二叉

8、树。下图是一棵完全二叉树。中在树的左部的二叉树。下图是一棵完全二叉树。 二.二叉树ACBEDNEXT NeusoftNEXT Neusoft1.遍历二叉树遍历二叉树二叉树的遍历二叉树的遍历是指按照一定顺序，依次访问二叉树中所有结点，并且每个结是指按照一定顺序，依次访问二叉树中所有结点，并且每个结点仅被访问一次。点仅被访问一次。二叉树的遍历一般可分为二叉树的遍历一般可分为三种次序遍历三种次序遍历，分别是先根遍历、中根遍历和后根，分别是先根遍历、中根遍历和后根遍历。遍历。先根遍历先根遍历：先访问根结点，再访问左子树，最后访问右子树。：先访问根结点，再访问左子树，最后访问右子树。中根遍历中根遍历：先

9、访问左子树，再访问根结点，最后访问右子树。：先访问左子树，再访问根结点，最后访问右子树。后根遍历后根遍历：先访问左子树，再访问右子树，最后访问根结点。：先访问左子树，再访问右子树，最后访问根结点。三.遍历二叉树和线索二叉树 NEXT Neusoft1.遍历二叉树遍历二叉树下图中，以下图中，以A为根结点的二叉树先根遍历的结果为为根结点的二叉树先根遍历的结果为ABDECFGH ACBDGFEH三.遍历二叉树和线索二叉树 NEXT Neusoft1.遍历二叉树遍历二叉树二叉树先根遍历代码二叉树先根遍历代码public void preOrder(BinaryTreeNode r) if (r !=

10、null) System.out.print(r.getData() + ); preOrder(r.getLeft(); preOrder(r.getRight(); 三.遍历二叉树和线索二叉树 NEXT Neusoft2. 线索二叉树线索二叉树 线索二叉树的结点由线索二叉树的结点由5个部分组成：数据域、左对象域、右对象域、左标志域、右标个部分组成：数据域、左对象域、右对象域、左标志域、右标志域。如图志域。如图6.21为线索二叉树的结点。为线索二叉树的结点。（二叉树不变的，所以各个的标志不变）（二叉树不变的，所以各个的标志不变）当结点存在左子树时，左标志域为当结点存在左子树时，左标志域为0，

11、左对象域指向其左子树；，左对象域指向其左子树；当结点不存在左子树时，左标志域为当结点不存在左子树时，左标志域为1，左对象域指向该结点的前驱结点；，左对象域指向该结点的前驱结点；(指遍历指遍历的的)当结点存在右子树时，右标志域为当结点存在右子树时，右标志域为0，右对象域指向其右孩子；，右对象域指向其右孩子；当结点不存在右子树时，右标志域为当结点不存在右子树时，右标志域为1，右对象域指向该结点的后继结点；，右对象域指向该结点的后继结点；(指遍历指遍历的的)三.遍历二叉树和线索二叉树 NEXT Neusoft2. 线索二叉树线索二叉树 ASGKUT三.遍历二叉树和线索二叉树 NEXT Neusoft

12、2. 线索二叉树线索二叉树 0 A 0 0 G 0 0 S 1 1 U 1 1 T 1 1 K 1 null三.遍历二叉树和线索二叉树 NEXT Neusoft1.树的存储结构树的存储结构 树的存储结构通常有树的存储结构通常有顺序存储顺序存储和和链式存储链式存储，分别使用数组和链，分别使用数组和链表来存储。表来存储。四.树和森林 NEXT Neusoft1.树的存储结构树的存储结构 四.树和森林 ACBDGFEHNEXT Neusoft1.树的存储结构树的存储结构树的双亲表示法树的双亲表示法 四.树和森林 NEXT Neusoft1.树的存储结构树的存储结构树的孩子链表表示法树的孩子链表表示法

13、 四.树和森林 NEXT Neusoft2.树转换为二叉树树转换为二叉树（1）加线）加线四.树和森林 ACBDGFEHNEXT Neusoft2.树转换为二叉树树转换为二叉树（2）抹线）抹线四.树和森林 ACBDGFEHNEXT Neusoft2.树转换为二叉树树转换为二叉树（3）旋转旋转四.树和森林 ACBDGFEHNEXT Neusoft2.森林转换为二叉树森林转换为二叉树 森林森林四.树和森林 CBDGFEHNEXT Neusoft2.森林转换为二叉树森林转换为二叉树 （1）在森林最上层增加一个虚拟结点，并让该结点指向森林中每棵树的根结点）在森林最上层增加一个虚拟结点，并让该结点指向森林

14、中每棵树的根结点 四.树和森林 CBDGFEHXNEXT Neusoft2.森林转换为二叉树森林转换为二叉树 （2）将树转换为二叉树）将树转换为二叉树 四.树和森林 CBDGFEHXNEXT Neusoft2.森林转换为二叉树森林转换为二叉树 （3）去掉根结点后，该二叉树即为森林转换成的二叉树）去掉根结点后，该二叉树即为森林转换成的二叉树 四.树和森林 CBDGFEHNEXT Neusoft3.二叉树转换为森林二叉树转换为森林 二叉树二叉树四.树和森林 ACBEDNEXT Neusoft3.二叉树转换为森林二叉树转换为森林 （1）增加一个虚拟根结点，虚拟根结点指向二叉树的根结点）增加一个虚拟根

15、结点，虚拟根结点指向二叉树的根结点 四.树和森林 ACBEDXNEXT Neusoft3.二叉树转换为森林二叉树转换为森林 （2）每个结点与其左孩子增加一条连线，结点与其左孩子的所有右孩子各增加一条）每个结点与其左孩子增加一条连线，结点与其左孩子的所有右孩子各增加一条连线连线 四.树和森林 ACBEDXNEXT Neusoft3.二叉树转换为森林二叉树转换为森林 （3）去掉每个结点之间原有连线。）去掉每个结点之间原有连线。 四.树和森林 ACBEDXNEXT Neusoft3.二叉树转换为森林二叉树转换为森林 （4）去掉虚拟根结点）去掉虚拟根结点 四.树和森林 ACBEDNEXT Neusof

16、t3.二叉树转换为森林二叉树转换为森林 （5）将连线逆时针旋转，整理成多棵树并列的森林）将连线逆时针旋转，整理成多棵树并列的森林 四.树和森林 ACBEDNEXT Neusoft4.树的遍历树的遍历 树的遍历树的遍历可以分为先根遍历和后根遍历。可以分为先根遍历和后根遍历。树的先根遍历是首先访问树的根结点，然后从左至右逐一先序遍历根的每一棵子树的先根遍历是首先访问树的根结点，然后从左至右逐一先序遍历根的每一棵子树。树。树的后根遍历是首先从左至右逐一后根遍历树的每一棵子树，最后访问树的根结树的后根遍历是首先从左至右逐一后根遍历树的每一棵子树，最后访问树的根结点。点。四.树和森林 NEXT Neus

17、oft4.树的遍历树的遍历 树的先根遍历结果为树的先根遍历结果为AQWPNSGCVF。树的后根遍历结果为树的后根遍历结果为WPNQGCSFVA。四.树和森林 AVQWPFNSCGNEXT Neusoft5.森林的遍历森林的遍历 森林的遍历森林的遍历也分为先根遍历和后根遍历。也分为先根遍历和后根遍历。先根遍历是从左至右对森林中的每一棵树使用树的先根遍历方法逐一进行遍历。先根遍历是从左至右对森林中的每一棵树使用树的先根遍历方法逐一进行遍历。后根遍历是从左至右对森林中的每一棵树使用树的后根遍历方法逐一进行遍历。后根遍历是从左至右对森林中的每一棵树使用树的后根遍历方法逐一进行遍历。四.树和森林 NEX

18、T Neusoft5.森林的遍历森林的遍历 森林的先根遍历结果为：森林的先根遍历结果为：BDGEHCF。 四.树和森林 CBDGFEHNEXT Neusoft1.哈夫曼树哈夫曼树 权值权值：赋予结点一个有意义的数字。：赋予结点一个有意义的数字。 树的路径长度树的路径长度：从树的根结点到每个结点的路径长度之和。：从树的根结点到每个结点的路径长度之和。 结点的带权路径长度结点的带权路径长度：结点到树根结点之间的路径长度与结点权值乘积。：结点到树根结点之间的路径长度与结点权值乘积。 树的带权路径长度树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记为：树中所有叶子结点的带权路径长度之和，通

19、常记为WPL。五.哈夫曼树及其应用 NEXT Neusoft1.哈夫曼树哈夫曼树 哈夫曼树哈夫曼树就是由具有权值的叶子结点组成的带权路径长度（就是由具有权值的叶子结点组成的带权路径长度（WPL）最小的二叉树。）最小的二叉树。哈夫曼算法的基本思想：哈夫曼算法的基本思想：1）对于给定）对于给定n个数据个数据Ww1,w2,wn,将其分别放入将其分别放入n个结点内，并将这个结点内，并将这n个结点分个结点分别看作别看作n棵二叉树，表示为棵二叉树，表示为T=T1,T2, ,Tn,。2）从）从T中选取根结点权值最小的两棵二叉树组成一棵新的二叉树，并分别作为新二中选取根结点权值最小的两棵二叉树组成一棵新的二叉

20、树，并分别作为新二叉树的左右子树，新二叉树根结点的权值为左右子树根结点权值之和。叉树的左右子树，新二叉树根结点的权值为左右子树根结点权值之和。3）从）从T中删除第中删除第2步所使用的两棵二叉树，并将第步所使用的两棵二叉树，并将第2步所产生的二叉树加入到步所产生的二叉树加入到T中。中。4）重复第）重复第2步与第步与第3步，直到步，直到T中只有一棵二叉树为止，这棵二叉树就是数据中只有一棵二叉树为止，这棵二叉树就是数据W的哈的哈夫曼树。夫曼树。五.哈夫曼树及其应用 NEXT Neusoft1.哈夫曼树哈夫曼树 五.哈夫曼树及其应用 3597NEXT Neusoft1.哈夫曼树哈夫曼树 第第1步，将数

21、据步，将数据W值放入结点内，并将其看作值放入结点内，并将其看作5棵二叉树棵二叉树T1,T2,T3,T4,T5。 T1 T2 T3 T4 T5 五.哈夫曼树及其应用 93751NEXT Neusoft1.哈夫曼树哈夫曼树 第第2步，从步，从T中选取权值最小的两棵二叉树，中选取权值最小的两棵二叉树，T5和和T3组成一棵新的二叉树组成一棵新的二叉树 五.哈夫曼树及其应用 413NEXT Neusoft1.哈夫曼树哈夫曼树 第第3步，从步，从T中去掉中去掉T5和和T3，并将第，并将第2步产生的二叉树放入集合步产生的二叉树放入集合T中中 五.哈夫曼树及其应用 947531NEXT Neusoft1.哈夫

22、曼树哈夫曼树 第第4步，从新集合步，从新集合T中选出两个根结点最小的二叉树，组成新的二叉树中选出两个根结点最小的二叉树，组成新的二叉树 五.哈夫曼树及其应用 45319NEXT Neusoft1.哈夫曼树哈夫曼树 第第5步，从步，从T中去掉根结点权值为中去掉根结点权值为4和根结点权值为和根结点权值为5的两棵二叉树，并将第的两棵二叉树，并将第4步产步产生的二叉树放入集合生的二叉树放入集合T中中 五.哈夫曼树及其应用 9745319NEXT Neusoft1.哈夫曼树哈夫曼树 第第6步，从新集合步，从新集合T中选出两个根结点最小的二叉树，组成新的二叉树中选出两个根结点最小的二叉树，组成新的二叉树

23、五.哈夫曼树及其应用 1697NEXT Neusoft1.哈夫曼树哈夫曼树 第第7步，从步，从T中去掉根结点权值为中去掉根结点权值为7和根结点权值为和根结点权值为9的两棵二叉树，并将第的两棵二叉树，并将第6步产步产生的二叉树放入集合生的二叉树放入集合T中中 五.哈夫曼树及其应用 453191697NEXT Neusoft1.哈夫曼树哈夫曼树 第第8步，从新集合步，从新集合T中选出两个根结点最小的二叉树，即根结点权值为中选出两个根结点最小的二叉树，即根结点权值为9和根结点和根结点权值为权值为16的两棵二叉树，组成新的二叉树，并放入集合的两棵二叉树，组成新的二叉树，并放入集合T中中 五.哈夫曼树及其应用 45319169725NEXT Neusof