1、1数据结构课程的内容数据结构课程的内容2第第6章章 树和二叉树（树和二叉树（Tree&Binary Tree）6.1 树的基本概念树的基本概念6.2 二叉树二叉树6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.5 赫夫曼树及其应用赫夫曼树及其应用36.1 树的基本概念1.树的定义树的定义2.若干术语若干术语3.逻辑结构逻辑结构4.存储结构存储结构5.树的运算树的运算41.树的定义树的定义注注1：过去许多书籍中都定义树为过去许多书籍中都定义树为n1，曾经有，曾经有“空树不是空树不是树树”的说法，但现在树的定义已修改。的说法，但现在树的定义已修改。注注2：树的定义具
2、有树的定义具有递归性递归性，即树中还有树。，即树中还有树。由一个或多个由一个或多个(n0n0)结点组成的有限集合结点组成的有限集合T T，有且，有且仅有仅有一个结点称为根一个结点称为根（rootroot），），当当n1n1时，其余的结点时，其余的结点分为分为m(m0)m(m0)个个互不相交互不相交的有限集合的有限集合T1,T2T1,T2，TmTm。每。每个集合本身又是棵树，被称作这个根的个集合本身又是棵树，被称作这个根的子树子树 。5树的表示法有几种：树的表示法有几种：图形表示法图形表示法嵌套集合表示法嵌套集合表示法广义表表示法广义表表示法目录表示法目录表示法6 树的抽象数据类型定义树的抽象数
3、据类型定义（见教材（见教材P118-119P118-119）ADT Tree数据对象数据对象D:数据关系数据关系R:基本操作基本操作 P：ADT Tree若若D为空集，则称为空树；为空集，则称为空树；/允许允许n=0若若D中仅含一个数据元素，则中仅含一个数据元素，则R为空集；为空集；其他情况下的其他情况下的R存在二元关系：存在二元关系：root 唯一唯一 /关于根的说明关于根的说明 DjDk=/关于子树不相交的说明关于子树不相交的说明 /关于子树的子树不相交的说明关于子树的子树不相交的说明D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。76.1 树的基本概念1.树的定义树的定
4、义2.若干术语若干术语3.逻辑结构逻辑结构4.存储结构存储结构5.树的运算树的运算82.若干术语若干术语即上层的那个结点即上层的那个结点(直接前驱直接前驱)即下层结点的子树的根即下层结点的子树的根(直接后继直接后继)同一双亲下的同层结点（孩子之间互称兄弟）同一双亲下的同层结点（孩子之间互称兄弟）即双亲位于同一层的结点（但并非同一双亲）即双亲位于同一层的结点（但并非同一双亲）即从根到该结点所经分支的所有结点即从根到该结点所经分支的所有结点即该结点下层子树中的任一结点即该结点下层子树中的任一结点ABCGEIDHFJMLK 根根 叶子叶子 森林森林有序树有序树无序树无序树即根结点即根结点(没有前驱没
5、有前驱)即终端结点即终端结点(没有后继没有后继)指指m棵不相交的树的集棵不相交的树的集合合(例如删除例如删除A后的子树个数后的子树个数)双亲双亲孩子孩子兄弟兄弟堂兄弟堂兄弟祖先祖先子孙子孙结点各子树从左至右有序，不能互换（左为第一）结点各子树从左至右有序，不能互换（左为第一）结点各子树可互换位置。结点各子树可互换位置。92.若干术语（续）若干术语（续）即树的数据元素即树的数据元素结点挂接的子树数结点挂接的子树数（有几个直接后继就是几度（有几个直接后继就是几度，亦称，亦称“次数次数”）结点结点结点的度结点的度结点的层次结点的层次终端结点终端结点分支结点分支结点树的度树的度树的深度树的深度(或高度
6、或高度)ABCGEIDHFJMLK从根到该结点的层数（根结点算第一层）从根到该结点的层数（根结点算第一层）即度为即度为0的结点，即叶子的结点，即叶子即度不为即度不为0的结点（也称为内部结点）的结点（也称为内部结点）所有结点度中的最大值（所有结点度中的最大值（Max各结点的度各结点的度）指所有结点中最大的层数（指所有结点中最大的层数（Max各结点的层次各结点的层次）问：问：右上图中的结点数右上图中的结点数 ；树的度；树的度 ；树的深度；树的深度13133 34 4106.1 树的基本概念1.树的定义树的定义2.若干术语若干术语3.逻辑结构逻辑结构4.存储结构存储结构5.树的运算树的运算113.树
7、的逻辑结构树的逻辑结构(特点特点)：一对多（一对多（1:n），有多个直接后继（如家谱树、），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且目录树等等），但只有一个根结点，且子子树之间互不相交树之间互不相交。126.1 树的基本概念1.树的定义树的定义2.若干术语若干术语3.逻辑结构逻辑结构4.存储结构存储结构5.树的运算树的运算134.树的存储结构树的存储结构 讨论讨论1：树是非线性结构，该怎样存储？树是非线性结构，该怎样存储？仍然有顺序存储、链式存储等方式。仍然有顺序存储、链式存储等方式。14讨论讨论3：树的树的链式存储链式存储方案应该怎样制定？方案应该怎样制定？可规定为：可规
8、定为：从上至下、从左至右从上至下、从左至右将树的结点依次存入内存。将树的结点依次存入内存。重大缺陷：重大缺陷：复原困难（不能唯一复原就没有实用价值）。复原困难（不能唯一复原就没有实用价值）。讨论讨论2：树的树的顺序存储顺序存储方案应该怎样制定？方案应该怎样制定？可用多重链表：可用多重链表：一个前趋指针，一个前趋指针，n n个后继指针。个后继指针。细节问题：细节问题：树中结点的结构类型样式该如何设计？树中结点的结构类型样式该如何设计？即应该设计成即应该设计成“等长等长”还是还是“不等长不等长”？缺点：缺点：等长结构太浪费（每个结点的度不一定相同）；等长结构太浪费（每个结点的度不一定相同）；不等长
9、结构太复杂（要定义好多种结构类型）。不等长结构太复杂（要定义好多种结构类型）。解决思路：解决思路：先研究最简单、最有规律的树，然后设法把先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。一般的树转化为简单树。156.1 树的基本概念1.树的定义树的定义2.若干术语若干术语3.逻辑结构逻辑结构4.存储结构存储结构5.树的运算树的运算165.树的运算树的运算 要明确：要明确：1.普通树（即多叉树）若不转化为二叉树，则运普通树（即多叉树）若不转化为二叉树，则运算很难实现。算很难实现。2.二叉树的运算仍然是插入、删除、修改、查找、二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必
10、须建立在排序等，但这些操作必须建立在对树结点能够对树结点能够“遍历遍历”的基础上！的基础上！（遍历遍历指每个结点都被访问且仅访问一次，指每个结点都被访问且仅访问一次，不遗漏不重复）。不遗漏不重复）。17第第6章章 树和二叉树（树和二叉树（Tree&Binary Tree）6.1 树的基本概念树的基本概念6.2 二叉树二叉树6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.5 赫夫曼树及其应用赫夫曼树及其应用186.2 二叉树二叉树为何要重点研究每结点最多只有两个为何要重点研究每结点最多只有两个“叉叉”的树？的树？二叉树的结构最简单，规律性最强；二叉树的结构最简单，
11、规律性最强；可以证明，所有树都能转为唯一对应的二叉树。可以证明，所有树都能转为唯一对应的二叉树。1.二叉树的定义二叉树的定义2.二叉树的性质二叉树的性质3.二叉树的存储结构二叉树的存储结构19定义：定义：是是n（n0）个结点的有限集合，由一个根结点以及两棵互）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为不相交的、分别称为左子树和右子树左子树和右子树的二叉树组成的二叉树组成。逻辑结构：逻辑结构：一对二（一对二（1：2）基本特征基本特征:每个结点最多只有两棵子树（不存在度大于每个结点最多只有两棵子树（不存在度大于2 2的结点）；的结点）；左子树和右子树次序不能颠倒（有序树）。左子树和
12、右子树次序不能颠倒（有序树）。基本形态：基本形态：5种种/2种种20二叉树的抽象数据类型定义二叉树的抽象数据类型定义（见教材（见教材P121-122）ADT BinaryTree数据对象数据对象D:数据关系数据关系R:基本操作基本操作 P：ADT BinaryTree若若D=，则，则R=；若若D，则，则R=H；存在二元关系：；存在二元关系：root 唯一唯一 /关于根的说明关于根的说明 DjDk=/关于子树不相交的说明关于子树不相交的说明 /关于根和左右子树有唯一联系的说明关于根和左右子树有唯一联系的说明 /关于左子树和右子树的说明关于左子树和右子树的说明D是具有相同特性的数据元素的集合。是具
13、有相同特性的数据元素的集合。216.2 二叉树二叉树1.二叉树的定义二叉树的定义2.二叉树的性质二叉树的性质3.二叉树的存储结构二叉树的存储结构22讨论讨论1 1：第：第i i层的结点数至多是多少？层的结点数至多是多少？（利用二进制性质可轻松求出）（利用二进制性质可轻松求出）性质性质1:1:在二叉树的第在二叉树的第i i层上至多有层上至多有个结点（个结点（i0i0）。）。性质性质2:2:深度为深度为k k的二叉树至多有的二叉树至多有个结点（个结点（k0k0）。）。2 2i-1i-1个个提问：第提问：第i i层上至少有层上至少有 个结点？个结点？1 1讨论讨论2 2：深度为：深度为k k的二叉树
14、，至多有多少个结点？的二叉树，至多有多少个结点？（利用二进制性质可轻松求出）（利用二进制性质可轻松求出）2 2k k-1-1提问：深度为提问：深度为k k时至少有时至少有 个结点？个结点？k k23讨论讨论3：二叉树的叶子数和度为：二叉树的叶子数和度为2的结点数之间有关系吗？的结点数之间有关系吗？性质性质3:3:对于任何一棵二叉树，若对于任何一棵二叉树，若2 2度的结点数有度的结点数有n n2 2个，个，则叶子数（则叶子数（n n0 0）必定为必定为n n2 21 1（即（即n0=n2+1）二叉树中全部结点数二叉树中全部结点数nn0+n1+n2(叶子数叶子数1 1度结点数度结点数2 2度结点数
15、度结点数)二叉树中全部结点数二叉树中全部结点数nB+1 (总分支数根结点总分支数根结点 )（除根结点外，每个结点必有一个直接前趋，即一个分支）（除根结点外，每个结点必有一个直接前趋，即一个分支）总分支数总分支数B=n1+2n2 (1(1度结点必有度结点必有1 1个直接后继，个直接后继，2 2度结点必有度结点必有2 2个个)n0+n1+n2=n1+2n2+1,即即n0=n2+1实际意义：实际意义：叶子数叶子数2 2度结点数度结点数1 1ABCGEIDHFJ24对于两种特殊形式的二叉树（对于两种特殊形式的二叉树（满二叉树和完全二叉树满二叉树和完全二叉树），），还特别具备以下还特别具备以下2个性质：
16、个性质：性质性质4:4:具有具有n n个结点的完全二叉树的深度必为个结点的完全二叉树的深度必为 loglog2 2n n 1 1性质性质5:5:对完全二叉树，若从上至下、从左至右编号，对完全二叉树，若从上至下、从左至右编号，则编号为则编号为i 的结点，其左孩子编号必为的结点，其左孩子编号必为2i，其右孩子编号，其右孩子编号必为必为2i1；其双亲的编号必为；其双亲的编号必为i/2（i1 时为根时为根,除外除外）。）。证明：根据性质证明：根据性质2 2，深度为，深度为k k的二叉树最多只有的二叉树最多只有2 2k k-1-1个结点，且完全二叉树个结点，且完全二叉树的定义是与同深度的满二叉树前面编号
17、相同，即它的总结点数的定义是与同深度的满二叉树前面编号相同，即它的总结点数n n位于位于k k层和层和k-1k-1层满二叉树容量之间，即层满二叉树容量之间，即 2 2k-1k-1-1n2-1n2k k-1 -1 或或2 2k-1k-1n n 2 2k k三边同时取对数，于是有：三边同时取对数，于是有：k-1logk-1log2 2nk ndata);/访问访问D DLR(root-lchild);/递归遍历左子树递归遍历左子树 DLR(root-rchild);/递归遍历右子树递归遍历右子树 return(0);中序遍历算法中序遍历算法LDR(Node*root)if(root!=NULL)L
18、DR(root-lchild);printf(“%d”,root-data);LDR(root-rchild);return(0);后序遍历算法后序遍历算法LRD(Node*root)if(root!=NULL)LRD(root-lchild);LRD(root-rchild);printf(“%d”,root-data);return(0);结点数据类型自定义结点数据类型自定义typedef struct Node int data;struct Node *lchild,*rchild；Node,*root;39对遍历的分析：对遍历的分析：1.从前面的三种遍历算法可以知道：如果将从前面的三
19、种遍历算法可以知道：如果将printf语句抹去，语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的遍历算法的访问路径是相同的，只是访问结点的时机不同访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点的路径从虚线的出发点到终点的路径上，每个结点经过上，每个结点经过3次次。AFEDCBG第第1次次经过时访问经过时访问先序先序遍历遍历第第2次次经过时访问经过时访问中序中序遍历遍历第第3次次经过时访问经过时访问后序后序遍历遍历2.2.二叉树遍历的时间效率和空间效率二叉树遍历的时间效率和空间效率时间效率时间效率:/每个
20、结点只访问一次每个结点只访问一次空间效率空间效率:/栈占用的最大辅助空间栈占用的最大辅助空间40例：例：【严题集【严题集6.42】编写递归算法，计算二叉树编写递归算法，计算二叉树中叶子结点的数目。中叶子结点的数目。思路：思路：输出叶子结点比较简单，用任何一种遍历算法，凡输出叶子结点比较简单，用任何一种遍历算法，凡是左右指针均空者，则为叶子，将其统计并打印出来。是左右指针均空者，则为叶子，将其统计并打印出来。DLR(Node*root)/采用中序遍历的递归算法采用中序遍历的递归算法 if(root!=NULL)/非空二叉树条件，还可写成非空二叉树条件，还可写成if(rootif(root)if(
21、!root-lchild&!root-rchild)/是叶子结点则统计并打印是叶子结点则统计并打印 sum+;printf(%dn,root-data);DLR(root-lchild);/递归遍历左子树，直到叶子处；递归遍历左子树，直到叶子处；DLR(root-rchild);/递归遍历右子树，直到叶子处；递归遍历右子树，直到叶子处；return(0);41思路：思路：利用利用前序前序遍历来建树遍历来建树（结点值陆续从键盘输入，用（结点值陆续从键盘输入，用DLR为宜）为宜）status createBTree(Bintree&T)scanf(“%c”,&ch);if(ch=)T=NULL;e
22、lse if(!(T=(BiTNode*)malloc(sizeof(BinTNode)exit(overflow);T-data=ch;createBTpre(T-lchild);createBTpre(T-rchild);return OK;建树建树见教材见教材P131程序程序42习题讨论：习题讨论：算法思路：算法思路：只查各结点后继链表指针，若左只查各结点后继链表指针，若左(右右)孩子的左孩子的左(右右)指针非空，则层次数加指针非空，则层次数加1 1；否则函数返回。；否则函数返回。算法思路：算法思路：既然要求从上到下，从左到右，则既然要求从上到下，从左到右，则利用队列利用队列存放存放各子
23、树结点的指针是个好办法，而不必拘泥于递归算法。各子树结点的指针是个好办法，而不必拘泥于递归算法。技巧：技巧：当根结点入队后，令其左、右孩子结点入队，而左孩当根结点入队后，令其左、右孩子结点入队，而左孩子出队时又令它的左右孩子结点入队，子出队时又令它的左右孩子结点入队，由此便可产生按由此便可产生按层次输出的效果。层次输出的效果。A B CD E43算法思路：算法思路：若不用递归，则要实现二叉树遍历的若不用递归，则要实现二叉树遍历的“嵌套嵌套”规规则，必用堆栈。可直接用则，必用堆栈。可直接用whilewhile语句和语句和push/poppush/pop操作。操作。参见教参见教材材P130-131
24、P130-131程序。程序。算法思路：算法思路：完全二叉树的特点是：没有左子树空而右子树单完全二叉树的特点是：没有左子树空而右子树单独存在的情况独存在的情况(前前k-1k-1层都是满的，且第层都是满的，且第k k层左边也满）层左边也满）。技巧技巧:按层序遍历方式，先把所有结点按层序遍历方式，先把所有结点（不管当前结点是否有（不管当前结点是否有左右孩子）左右孩子）都入队列都入队列.若为完全二叉树若为完全二叉树,则层序遍历时得到的则层序遍历时得到的肯定是一个连续的不包含空指针的序列肯定是一个连续的不包含空指针的序列.如果序列中出现了空如果序列中出现了空指针，则说明不是完全二叉树。指针，则说明不是完
25、全二叉树。44【严题集【严题集6.31】证明：由一棵二叉树的先序序列和中序证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树。序列可唯一确定这棵二叉树。例：例：已知一棵二叉树的已知一棵二叉树的中序序列中序序列和和后序序列后序序列分别是分别是BDCEAFHG 和和 DECBHGFA，请画出这棵二叉树。，请画出这棵二叉树。分析：分析：由后序遍历特征，根结点必在后序序列尾部由后序遍历特征，根结点必在后序序列尾部（即（即A A）；由中序遍历特征，根结点必在其中间，而且其左部必全部是由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙左子树子孙（即（即BDCEBDCE），其右部必全部是
26、右子树子孙，其右部必全部是右子树子孙（即（即FHGFHG）；继而，根据后序中的继而，根据后序中的DECBDECB子树可确定子树可确定B B为为A A的左孩子，根据的左孩子，根据HGFHGF子串可确定子串可确定F F为为A A的右孩子；以此类推。的右孩子；以此类推。45中序遍历：中序遍历：B D C E A F H G后序遍历：后序遍历：D E C B H G F A（B D C E）（F H G）ABF （D C E）（H G）CD EGHABBFF46问：问：用二叉链表法（用二叉链表法（l_child,r_child）存储包含）存储包含n个结点的二个结点的二叉树，结点的指针区域中会有多少个空
27、指针？叉树，结点的指针区域中会有多少个空指针？分析：分析：用二叉链表存储包含用二叉链表存储包含n个结点的二叉树，结点必有个结点的二叉树，结点必有2n个链域个链域（见二叉链表数据类型说明）（见二叉链表数据类型说明）。除根结点外，二叉树中每一个结点除根结点外，二叉树中每一个结点有且仅有一个双亲有且仅有一个双亲（直接前驱），所以只会有（直接前驱），所以只会有n1个结点的链域存放指针，指个结点的链域存放指针，指向非空子女结点（即直接后继）。向非空子女结点（即直接后继）。思考：思考：二叉链表空间效率这么低，能否利用这些空闲区存放二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？有用的信息或
28、线索？我们可以用它来存放当前结点的直接前驱和后继等线索，我们可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。以加快查找速度。所以，所以，空指针数目空指针数目2n(n-1)=n+1个个。n+1476.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树一、遍历二叉树（遍历二叉树（Traversing Binary Tree）二、线索二叉树（二、线索二叉树（Threaded Binary Tree）48二、线索二叉树线索二叉树（Threaded Binary Tree）普通二叉树只能找到结点的左右孩子信息，普通二叉树只能找到结点的左右孩子信息，而该结点的而该结点的直接前驱和直接后继只能在
29、遍历过程中获得。直接前驱和直接后继只能在遍历过程中获得。若将若将遍历后对应的有关前驱和后继预存遍历后对应的有关前驱和后继预存起来，则从起来，则从第一第一个结点个结点开始就能很快开始就能很快“顺藤摸瓜顺藤摸瓜”而遍历整个树了。而遍历整个树了。两种解决方法两种解决方法增加两个域：增加两个域：fwd和和bwd；利用空链域（利用空链域（n+1个空链域）个空链域）存放前驱指针存放前驱指针存放后继指针存放后继指针如何预存这类信息？如何预存这类信息？例如中序遍历结果：例如中序遍历结果：B D C E A F H GB D C E A F H G，实际上，实际上已将二叉已将二叉树转为线性排列，显然具有唯一前驱
30、和唯一后继！树转为线性排列，显然具有唯一前驱和唯一后继！可能是根、或最左（右）叶子可能是根、或最左（右）叶子49规规 定：定：1）若结点有左子树，则）若结点有左子树，则lchild指向其左孩子；指向其左孩子；否则，否则，lchild指向其直接前驱指向其直接前驱(即线索即线索)；2）若结点有右子树，则）若结点有右子树，则rchild指向其右孩子；指向其右孩子；否则，否则，rchild指向其直接后继指向其直接后继(即线索即线索)。为了避免混淆，增加两个标志域为了避免混淆，增加两个标志域，如下图所示：，如下图所示：lchildLTagdataRTag rchild约定约定:当当Tag域为域为0时时,
31、表示表示正常正常情况情况;当当Tag域为域为1时时,表示表示线索线索情况情况.50有关线索二叉树的几个术语：有关线索二叉树的几个术语：线索链表：线索链表：用上一页结点结构所构成的二叉链表用上一页结点结构所构成的二叉链表 线线 索：索：指向结点前驱和后继的指针指向结点前驱和后继的指针线索二叉树：线索二叉树：加上线索的二叉树加上线索的二叉树（图形式样）（图形式样）线线 索索 化：化：对二叉树以对二叉树以某种次序遍历某种次序遍历使其变为线使其变为线索二叉树的过程索二叉树的过程注：注：在线索化二叉树中，并不是每个结点都能直在线索化二叉树中，并不是每个结点都能直接找到其后继的，接找到其后继的，当标志为当
32、标志为0时，则需要通过一时，则需要通过一定运算才能找到它的后继定运算才能找到它的后继。51dataAGEIDJHCFBltag0011110101rtag0001010111AGEIDJHCFB例例1：带了带了两个标志两个标志的某的某先序遍历先序遍历结果如表所示，请画结果如表所示，请画出对应二叉树。出对应二叉树。52ABCGEIDHFroot悬空？悬空？悬空？悬空？解：解：该二叉树中序遍历结果为该二叉树中序遍历结果为:H,D,I,B,E,A,F,C,G所以添加线索应当按如下路径进行：所以添加线索应当按如下路径进行：例例2：画出以下二叉树对应的画出以下二叉树对应的中序中序线索二叉树。线索二叉树。
33、为避免悬空为避免悬空态，应增设态，应增设一个头结点一个头结点53对应的中序线索二叉树存储结构如图所示：对应的中序线索二叉树存储结构如图所示：00A00C00B11E11F11G00D11I11H注：此图中序遍历结果为注：此图中序遍历结果为:H,D,I,B,E,A,F,C,G0-root0544.【2000年计算机系考研题年计算机系考研题】给定如图所示二叉给定如图所示二叉树树T，请画出与其对应的中序线索二叉树。，请画出与其对应的中序线索二叉树。2825405560330854解解:因为中序遍历序列是：因为中序遍历序列是：5555 40 25 60 40 25 60 2828 08 33 08 3
34、3 5454对应线索树应当按此规律连线，即对应线索树应当按此规律连线，即在原二叉树中添加虚线。在原二叉树中添加虚线。NILNILNILNIL55上堂课例题讨论上堂课例题讨论问问:设一棵完全二叉树具有设一棵完全二叉树具有10001000个结点，则它有个结点，则它有 个叶个叶子结点，有子结点，有 个度为个度为2 2的结点。的结点。先计算树的深度先计算树的深度 k=k=log2n 1=10;=10;末层节点数末层节点数=1000-(29-1)=489第第9层节点数层节点数=28=256 第第9层叶子节点数层叶子节点数=(256*2-489)/2=11法法1：先求全部叶子数。先求全部叶子数。n0489
35、(末层末层)11(第第9层层)=500个；个；法法2：先求先求2度结点数。度结点数。n2=255(前前8层层)244(第第9层层)=499个；个；法法3 3：无需求树深无需求树深k k，便可快捷求出，便可快捷求出 取大于取大于n/2n/2的最小整数值的最小整数值 可由二叉树性质可由二叉树性质5 5轻松证明！轻松证明！(编号为编号为i i的结点，其孩子编号必为的结点，其孩子编号必为2i2i和和2i+1)2i+1)nn已知最后一个结点编号为已知最后一个结点编号为n n，则其双亲（，则其双亲（n/2n/2或或(n-1)/2)(n-1)/2)肯定是最后一个非叶子结点。其编号之后的全部结点都肯定是最后一
36、个非叶子结点。其编号之后的全部结点都是叶子了！是叶子了！故，故，n0=n-n/2n0=n-n/2或或n-(n-1)/2=n-(n-1)/2=56线索二叉树的生成算法线索二叉树的生成算法（算法（算法6.6,见教材见教材P134）目的：目的：在在依某种顺序遍历依某种顺序遍历二叉树时修改空指针，添加前驱或后继。二叉树时修改空指针，添加前驱或后继。注解：注解：为方便添加结点的前驱或后继，需要设置两个指针：为方便添加结点的前驱或后继，需要设置两个指针：p指针指针当前结点之指针；当前结点之指针；pre指针指针前驱结点之指针。前驱结点之指针。技巧：技巧：当结点当结点p的左的左/右域为空右域为空时，只改写它的
37、左域（装入前驱时，只改写它的左域（装入前驱pre），而其右域（后继）留给下一结点来填写。，而其右域（后继）留给下一结点来填写。或者说，当前结点的指针或者说，当前结点的指针p应当送到前驱结点的空右域中。应当送到前驱结点的空右域中。若若p-lchildNULL,则则p-Ltagp-Ltag=1;=1;p-lp-lchildchildprepre;/p/p的前驱结点指针的前驱结点指针prepre存入左空域存入左空域若若pre-rchildNULL,则则pre-Rtagpre-Rtag1;1;pre-rpre-rchildchild=p p;/p p存入其前驱结点存入其前驱结点prepre的右空域的右
38、空域573.线索二叉树的遍历线索二叉树的遍历理论上，只要找到序列中的理论上，只要找到序列中的第一个结点第一个结点，然后，然后依次访依次访问结点的后继问结点的后继直到后继为空时结束。直到后继为空时结束。在线索化二叉树中，并不是每个结点都能直接找到其在线索化二叉树中，并不是每个结点都能直接找到其后继的，后继的，当标志为当标志为0 0时，时，R_child=R_child=右孩子地址指针，并非后继！右孩子地址指针，并非后继！需要通过一定运算才能找到它的后继。需要通过一定运算才能找到它的后继。以以中序线索二叉树中序线索二叉树为例：为例：对叶子结点（对叶子结点（RTag=1），直接后继指针就在其），直接
39、后继指针就在其rchild域内；域内；对其他结点（对其他结点（RTag=0），直接后继是其），直接后继是其右子树最左下的结点右子树最左下的结点；（因为中序遍历规则是（因为中序遍历规则是LDR，）58程序注解程序注解 (非递归，且不用栈非递归，且不用栈）：P=T-lchild;/从头结点进入到根结点；从头结点进入到根结点；while(p!=T)while(p-LTag=link)p=p-lchild;/先找到中序遍历起点先找到中序遍历起点 if(!visit(p-data)return ERROR;/若起点值为空则出错告警若起点值为空则出错告警 while(p-RTag=Thread)p=p-r
40、child;Visit(p-data);/若有后继标志，则直接提取若有后继标志，则直接提取p-rchild中线索并中线索并访问后继结点；访问后继结点；p=p-rchild;/当前结点右域不空当前结点右域不空或或已经找好了后继已经找好了后继，则一律从，则一律从结点的右子树开始重复结点的右子树开始重复 的全部过程。的全部过程。Return OK;线索二叉树的线索二叉树的中序中序遍历算法遍历算法（算法（算法6.5,参见教材参见教材P134）LTag=0RTag=159算法流程：算法流程：return OK;p=T-lchild;p!=Tp-LTag=0p=p-lchild;vist(p-data);
41、p-LTag=1&p-rchild!=Tp=p-rchild;visit(p-data);p=p-rchild;YNYNYN60提前介绍：二叉树的应用提前介绍：二叉树的应用平衡树平衡树排序树排序树字典树字典树判定树判定树带权树带权树最优树最优树特点：左右子树深度差特点：左右子树深度差 1特点：特点：“左小右大左小右大”由字符串构成的二叉树排序树由字符串构成的二叉树排序树例如，例如，12个球只称个球只称3次分出轻重次分出轻重特点：路径长度带权值特点：路径长度带权值带权路径长度最短的树，又称带权路径长度最短的树，又称 Huffman树，用途之一是通信中的压缩编码。树，用途之一是通信中的压缩编码。6
42、11 1、定义和性质定义和性质2 2、存储结构存储结构3 3、遍历遍历4 4、线索化线索化：线索树：线索树顺序结构顺序结构链式结构链式结构二叉链表二叉链表三叉链表三叉链表先序线索树先序线索树中序线索树中序线索树后序线索树后序线索树树二叉树二叉树森林中序遍历中序遍历后序遍历后序遍历先序遍历先序遍历霍夫曼树霍夫曼树霍夫曼编码霍夫曼编码62第第6章章 树和二叉树（树和二叉树（Tree&Binary Tree）6.1 树的基本概念树的基本概念6.2 二叉树二叉树6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.5 赫夫曼树及其应用赫夫曼树及其应用636.4 树和森林1.树
43、和森林与二叉树的转换树和森林与二叉树的转换2.树和森林的存储方式树和森林的存储方式3.树和森林的遍历树和森林的遍历641.树和森林与二叉树的转换树和森林与二叉树的转换转换步骤：转换步骤：step1:step1:将树中同一结点的兄弟相连将树中同一结点的兄弟相连;step2:step2:保留结点的最左孩子连线，删除其它孩保留结点的最左孩子连线，删除其它孩子连线；子连线；step3:step3:将同一孩子的连线绕左孩子旋转将同一孩子的连线绕左孩子旋转4545度角。度角。加线加线抹线抹线旋转旋转讨论讨论1 1：树如何转为二叉树？：树如何转为二叉树？65方法：方法：加加线线抹线抹线旋转旋转 abeidf
44、hgc树转二叉树举例：树转二叉树举例：abeidfhgc兄弟相连兄弟相连长兄为父长兄为父孩子靠左孩子靠左66讨论讨论2：二叉树怎样还原为树？：二叉树怎样还原为树？abeidfhgc要点：要点：把所有右孩子变为兄弟！把所有右孩子变为兄弟！abeidfhgc67法一：法一：各森林先各自转为二叉树；各森林先各自转为二叉树；依次连到前一个二叉树的右子树上。依次连到前一个二叉树的右子树上。讨论讨论3 3：森林如何转为二叉树？：森林如何转为二叉树？法二：法二：森林直接变兄弟，再转为二叉树森林直接变兄弟，再转为二叉树（参见教材（参见教材P138P138图图6.176.17）即即F=TF=T1 1,T,T2
45、2,T,Tm m B=root,LB,RB B=root,LB,RB68ABCDEFGHJIABCDEFGHJIBCDEFGHJI森林转二叉树举例：森林转二叉树举例：（法二）（法二）兄弟相连兄弟相连 长兄为父长兄为父孩子靠左孩子靠左 头根为根头根为根 69讨论讨论4：二叉树如何还原为森林？：二叉树如何还原为森林？要点：要点：把最右边的子树变为森林，其余右子树变为兄弟把最右边的子树变为森林，其余右子树变为兄弟 ABCDEFGHJIABCDEFGHJIEFABCDGHJI即即B=root,LB,RB F=TB=root,LB,RB F=T1 1,T,T2 2,T,Tm m 706.4 树和森林1.
46、树和森林与二叉树的转换树和森林与二叉树的转换2.树和森林的存储方式树和森林的存储方式3.树和森林的遍历树和森林的遍历712.树和森林的存储方式树和森林的存储方式树有三种常用存储方式：树有三种常用存储方式：双亲表示法双亲表示法 孩子表示法孩子表示法 孩子兄弟表示法孩子兄弟表示法 1 1、用双亲表示法来存储、用双亲表示法来存储思路：思路：用一组用一组连续空间连续空间来存储树的结点，同时在每个来存储树的结点，同时在每个结点中结点中附设一个指示器附设一个指示器，指示其双亲结点在链表中的，指示其双亲结点在链表中的位置。位置。parentsdata结点结构结点结构dataparents1树结构树结构 23
47、n72缺点：求结点的孩子时需要遍历整个结构。缺点：求结点的孩子时需要遍历整个结构。01234567812233ABCDEFGHI-1001例例1:双亲表示法双亲表示法73思路：思路：将每个结点的将每个结点的孩子孩子排列起来，形成一个排列起来，形成一个带表头带表头（装父结点）（装父结点）的线性表的线性表（n n个结点要设立个结点要设立n n个链表）；个链表）；再将再将n n个表头用数组存放个表头用数组存放起来，这样就形成一个起来，这样就形成一个混合混合结构结构。例如例如：abecdfhgdefghgfedcbah123456782、用孩子表示法来存储、用孩子表示法来存储bc74思路：思路：用二叉
48、链表用二叉链表来表示树，但链表中的两个来表示树，但链表中的两个指针域含义不同。指针域含义不同。左指针指向该结点的第一个孩子；左指针指向该结点的第一个孩子；右指针指向该结点的下一个兄弟结点。右指针指向该结点的下一个兄弟结点。nextsiblingdatafirstchild3、用孩子兄弟表示法来存储、用孩子兄弟表示法来存储指向左孩子指向左孩子指向右兄弟指向右兄弟75abecdfhgbacedfgh问：问：树树二叉树的二叉树的“连线连线抹线抹线旋转旋转”如如何由计算机自动实现？何由计算机自动实现？答：答：用用“左孩子右兄弟左孩子右兄弟”表示法来存储即可。表示法来存储即可。例如：例如：766.4 树
49、和森林1.树和森林与二叉树的转换树和森林与二叉树的转换2.树和森林的存储方式树和森林的存储方式3.树和森林的遍历树和森林的遍历773、树和森林的遍历、树和森林的遍历先序遍历先序遍历C 访问根结点；访问根结点；C 依次先序遍历根结点的每棵子树。依次先序遍历根结点的每棵子树。例如：例如：abdec先序序列：先序序列：后序序列：后序序列：a b c d eb d c e a 后序遍历后序遍历F依次后序遍历根结点的每棵子树；依次后序遍历根结点的每棵子树；F访问根结点。访问根结点。树没有中序遍历（因子树不分左右）树没有中序遍历（因子树不分左右）遍历遍历深度遍历（先序、中序、后序）深度遍历（先序、中序、后
50、序）广度遍历（层次）广度遍历（层次）78讨论：若采用讨论：若采用“先转换，后遍历先转换，后遍历”方式，结果是否一样？方式，结果是否一样？abdec先序遍历：先序遍历：后序遍历：后序遍历：中序遍历：中序遍历：d e c b aabdeca b c d eb d c e a1.树的先序遍历二法相同；树的先序遍历二法相同；2.树的树的后序后序遍历相当于对应二叉树的遍历相当于对应二叉树的中序中序遍历；遍历；3.树没有中序遍历，因为子树无左右之分。树没有中序遍历，因为子树无左右之分。结论：结论：79 先序遍历先序遍历F若森林为空，返回；若森林为空，返回；F访问森林中第一棵树的根结点；访问森林中第一棵树的
