《数据结构》树

1、计科系计科系 王丹丹王丹丹第6章 树主要内容主要内容树的定义和存储结构二叉树的定义、性质和存储结构二叉树的遍历、建立和线索化树、森林与二叉树的转换赫夫曼树及其应用重点和难点重点和难点二叉树的数组、结构数组及链表的表示法二叉树的建立算法二叉树的遍历算法（前序、中序、后序）二叉树的查找算法二叉树的结点删除算法6.1 开场白开场白AVATAR6.2 树的定义树的定义树的表示法ABCDEFHIJG根结点根结点6.2.1 结点分类结点分类树的结点树的结点结点的度结点的度叶结点叶结点分支结点分支结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数。（Degree）度为0的结点。（终端结点）度不为0

2、的结点。（非终端结点/内部结点）树的度树的度树内各结点的度的最大值。例：思考结点A、B、C、D、E、J是什么类型，度是多少？ABCDEFHIJG6.2.2 结点间关系结点间关系孩子结点（孩子结点（Child）结点的子树的根称为该结点的孩子。双亲结点（双亲结点（Parent）孩子结点的上层结点叫该结点的双亲结点。祖先祖先结点（结点（ancestor）从根到该结点的所经路径上的所有结点均称为祖先结点。兄弟兄弟结点（结点（Sibling）同一双亲的孩子互称为兄弟结点。堂堂兄弟结点兄弟结点（Cousin）双亲在同一层上的结点互称为堂兄结点。子孙子孙结点结点以某结点为根的子树中任一结点都称为该结点的子孙

3、结点。思考：结点E的孩子、双亲、兄弟、堂兄弟、祖先、子孙结点分别是哪些？ABCDEFHIJG6.2.3 树的其他相关概念树的其他相关概念结点的层次(Level)从根开始定义起。树的深度(Depth)/高度：树中结点的最大层次。ABCDEFHIJG第一层第二层第三层第四层深度为4有序树和无序树 如果将树中结点的各子树看成从左至右是有秩序的，不能互换的，则称该树为有序树，否则称为无序树。森林(Forst) m(m0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。对比线性表与树的结构线性结构线性结构第一个数据元素：无前驱第一个数据元素：无前驱最后一个数据元素：无后继最后一个数据元素

4、：无后继中间元素：一个前驱一个后继中间元素：一个前驱一个后继树结构树结构根结点：无双亲，唯一根结点：无双亲，唯一叶结点：无孩子，可以多个叶结点：无孩子，可以多个中间结点：一个双亲多个孩子中间结点：一个双亲多个孩子6.3 树的抽象数据类型树的抽象数据类型ADT 树树(Tree)Data树是由一个根结点和若干棵子树构成。树中结点树是由一个根结点和若干棵子树构成。树中结点具有相同数据类型及层次关系。具有相同数据类型及层次关系。OperationInitTree(*T)：构造空树。：构造空树。Destroy(*T)：销毁树：销毁树T。CreateTree(*T,definition)：按：按defin

5、ition中给出树中给出树的定义来构造树。的定义来构造树。ClearTree(*T)：若树：若树T存在，则将树存在，则将树T清为空树。清为空树。TreeEmpty(*T)：若：若T为空树，返回为空树，返回true，否则返，否则返回回false。接上页接上页TreeDepth(*T)：返回：返回T的深度。的深度。Root(T)：返回：返回T的根结点。的根结点。Value(T,cur_e)：cur_e是树是树T中一个结点，返回此中一个结点，返回此结点的值。结点的值。Assign(T,cur_e,value)：给树：给树T的结点的结点cur_e赋值为赋值为value。Parent(T,cur_e)：

6、若：若cur_e是树是树T的非根结点，则的非根结点，则返回它的双亲，否则返回空。返回它的双亲，否则返回空。LeftChild(T,cur_e)：若：若cur_e是树是树T的非叶结点，的非叶结点，则返回它的双亲，否则返回空。则返回它的双亲，否则返回空。接上页接上页RightSibling(T,cur_e)：若：若cur_e有有兄弟，则返有有兄弟，则返回它的右兄弟，否则返回空回它的右兄弟，否则返回空。InisertChild(*T,*p,i,c)：其中：其中p指向树指向树T的某个结的某个结点，点，i为所指结点为所指结点p的的度度上加上加1，非空树，非空树c与与T不相交，操不相交，操作结果为插入作结

7、果为插入c为树为树T中中p指结点的第指结点的第i棵子树。棵子树。 DeleteChild(*T,*p,i)：其中其中p指向树指向树T的某个结点，的某个结点，i为所指结点为所指结点p的度，操作的度，操作结果结果为删除为删除T中中p指结点的第指结点的第i棵子树棵子树。endADT6.4 树的存储结构树的存储结构链式存储链式存储顺序顺序存储存储 结 点 的 存储位置无法直接反映逻辑关系。 充分利用二者的特点完全可以实现对树的存储结构的表示！6.4.1 双亲表示法双亲表示法假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点在数组中的位置。其结点结构为： data是数据域，存

8、储结点的数据信息； parent是指针域，存储该结点的双亲在数组中的下标。 约定根结点的位置域为-1，则所有的结点都存有它双亲的位置。dataparent双亲表示法的结点结构定义代码/*树的双亲表示法结点结构定义树的双亲表示法结点结构定义*/#define MAX_TREE_SIZE 100typedef int TElemType;/树结点的数据类型树结点的数据类型typedef struct PTNode/结点结构结点结构TElemType data;/结点数据结点数据int parent;/双亲位置双亲位置PTNode;typedef struct/树结构树结构PTNode nodesM

9、AX_TREE_SIZE;/结点数组结点数组int r, n;/根的位置和结点树根的位置和结点树PTree;树结构和树双亲表示ABCDEFHIJG下标下标 dataparent0A-11B02C03D14E25F26G37H38I39J4 根据结点的parent指针很容易找到它的双亲结点，所用时间复杂度为O(1)。 结点的孩子呢？遍历整个结构！改进：增加长子域，如果没有长子域就设置为-1。ABCDEFHIJG下标下标 data parent firstchild0A-111B032C043D164E295F2-16G3-17H3-18I3-19J4-1 对于有0或1个孩子的结点，解决了要找结点

10、孩子的问题。 关注各兄弟之间的关系？方法：增加一个右兄弟域来体现兄弟关系。 每一个结点如果它存在右兄弟，则记录下右兄弟的下标；否则，赋值为-1。ABCDEFHIJG下标下标 data parentrightsib0A-1-11B022C0-13D1-14E255F2-16G377H388I3-19J4-1 存储结构的设计是一个非常灵活的过程。设计是否合理，取决于基于该存储结构的运算是否适合、是否方便，时间复杂度好不好等。6.4.2 孩子表示法孩子表示法多重链表表示法 每个结点有多个指针域，其中每个指针域指向一棵子树的根结点。 不过，树的每个结点的度是不同，故可以设计两种方案来解决。方案一：指针

11、域的个数等于树的度。其结构为： data：数据域； child1childd：指针域，用来指向该节点的孩子结点。datachild1chilid2 child3 childd对于下图的树，树的度是3，故指针域是3。ABCDEFHIJGABCDEFG H IJ头指针很多结点的指针域都是空的。很多结点的指针域都是空的。对于树中各结点的度相差很大对于树中各结点的度相差很大时，是很浪费空间的。时，是很浪费空间的。方案二：每个结点的指针域的个数等于该结点的度，专门取一个位置来存储结点指针域的个数。其结构为： data：数据域； degree：度域，存储该结点孩子结点的个数； child1childd：指

12、针域，指向该结点的各个孩子结点。data degree child1 chilid2childd方法实现ABCDEFHIJGA2B1C2D3E1F0头指针H 0IJ0G 0 克服了浪费空间的缺点，空间利用率提高； 各链表结构不同、维护结点的度数值，在运算上带来时间上的损耗。能否有更好的方法，既可以减少空指针的浪费又能使结点结构相同？孩子表示法孩子表示法 把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。 然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。下标下标0123456789ABCDEFGHIJdata fir

13、stchild1child next23456789设计两种结点结构孩子链表的孩子结点child：数据域，用来存储某个结点在表头数组中的下标；next：指针域，用来存储指向某结点的下一个孩子结点的指针。表头数组的表头结点data：数据域，存储某结点的数据信息；firstchild：头指针域，存储该结点的孩子链表的头指针。childnextdatafirstchild孩子表示法的结构定义代码/*树的孩子表示法结构定义树的孩子表示法结构定义*/#define MAX_TREE_SIZE 100typedef struct CTNode/孩子结点孩子结点int child;struct CTNode

14、 *next;*ChildPtr;typedef struct /表头结构表头结构TElemType data;ChildPtr firstchild;CTBox;typedef struct /树结构树结构CTBox nodesMAX_TREE_SIZE;/结点数组结点数组int r, n;CTree;6.4.3 孩子兄弟表示法孩子兄弟表示法任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。结点结构为：data：数据域；firstchild：指针域，存储该结点第一个孩子结点的存储地址；righ

15、tsib：指针域，存储该结点的右兄弟的存储地址。datafirstchildrightsib结构代码/*树的孩子兄弟表示法结构定义树的孩子兄弟表示法结构定义*/typedef struct CSNodeTElemType data;struct CSNode *firstchild, *rightsib;CSNode,*CSTree;ABCDEF 头指针G H I J 最大好处：把一棵复杂的树变成一棵二叉树。ABCDEF 头指针G H I J 这样就可以充分这样就可以充分利用二叉树的特利用二叉树的特性和算法来处理性和算法来处理这棵树了！这棵树了！6.5 二叉树二叉树猜数字？猜数字？规则：只告诉

16、是“大了”或“小了”。 对于这种在某个阶段都是两种结果的情形，都适合用树状结构来建模，而这种树是一种很特殊的树状结构，叫作二叉树。二叉树 n(n0)个结点的有限集合，该集合或者为空集(空二叉树)，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。ABCDEFHIJGABCDEFHIJG二叉树不是二叉树6.5.1 二叉树特点二叉树特点每个结点最多有两棵子树，所以二叉树不存在度大于2的结点。左子树和右子树是有顺序的，次序不能任意颠倒。即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。ABCDEFHIJG树1树2二叉树的特点：二叉树的五种基本形态空二叉树空二叉树A

17、只有一个只有一个根节点根节点AAA根结点只根结点只有左子树有左子树根结点只根结点只有右子树有右子树根结点既有左子根结点既有左子树，又有右子树树，又有右子树例：3个结点的二叉树树1树2树3树4树5形态：两层和三层；形态：两层和三层；二叉树：区别左右，二叉树：区别左右，演变为演变为5 5中形态。中形态。6.5.2 特殊二叉树特殊二叉树斜树 所有结点只有左子树的二叉树叫左斜树。 所有结点只有右子树的二叉树叫右斜树。例：斜树左斜树右斜树斜树的特点： 每每一一层都只有层都只有一个结点，结点的一个结点，结点的个数与二叉树的深个数与二叉树的深度相同。度相同。线性线性表结构？！表结构？！满二叉树 在一棵二叉树

18、中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。如下图：满二叉树的特点： 叶子只能出现在最下一层；非叶子结点的度一定是2；在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。完全二叉树 对一棵具有n个结点的二叉树按层序编号，如果编号为i(1in)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。如下图所示：12984105367满二叉树一定是一棵完全二叉树，完全二叉树不一定是满的。判断：下列树是否是完全二叉树。123114589121367101415123114589126710123456712

19、3456树1树2树4树31231145896710123114589126710123458967树1树3树2判断某二叉树是否是完全二叉树的办法：给树的示意图中每个结点按照满二叉树的结构逐层顺序编号，如果编号出现空挡，就说明不是完全二叉树，否则就是。完全二叉树的特点01叶子结点只能出现在最下两层。02030405最下层的叶子一定集中在左部连续位置。倒数第二层若有叶子结点，一定都在右部连续位置。若结点度为1，则该结点只有左孩子。同样结点树的二叉树，完全二叉树的深度最小。6.6 二叉树的性质二叉树的性质ABCDEGHIJF01如果2in，则结点i无左孩子(结点i为叶子结点)；否则其左孩子是结点2i

20、。02如果2i+1n，则结点i无右孩子；否则其右孩子是结点2i+1.03129845367106.7 二叉树的存储结构二叉树的存储结构二叉树顺序存储结构 二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，且结点的存储位置(数组下标)要能体现结点之间的逻辑关系。 例：一棵完全二叉树如图所示ABCDEGHIJF 将这棵二叉树存入到数组中，相应的下标对应其同样的位置：12345678910ABCDEGHIJF下标ABCDEFGHIJ 由于完全二叉树定义严格，所以顺序结构也可以表现出二叉树的结构来。 例：对于一棵一般二叉树 尽管层序编号不能反映逻辑关系，但可以将其按完全二叉树编号，把不存在的结点设

21、置为“”。ABCDEGHIJF12345678910下标ABCEGJABDC12345678910 11 12 13 14 15下标ABCCD二叉链表 二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域，我们称这样的链表叫做二叉链表。结点结构如下图所示, data：数据域 lchild、rchild：指针域，分别存放指向左孩子和右孩子的指针。lchilddatarchild/*二叉树的二叉链表结点结构定义二叉树的二叉链表结点结构定义*/typedef struct BiTNode/结点结构结点结构TElemType data;/结点数据结点数据struct BiTNode *lc

22、hild, *rchild;/左右孩子指针左右孩子指针BiTNode,*BiTree; 结构示意图ABCDE F 头指针 G H I J 三叉链表 根据需要增加一个指向其双亲的指针域，就称为三叉链表。typedef struct node datatype data; struct node *lchild, *rchild, *parent;JD;ABCDEFG A B C D E F Glchilddataparentrchild6.8 遍历二叉树遍历二叉树二叉树的遍历(traversing binary tree)是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问

23、一次且仅被访问一次。访问：访问：根据实际需要根据实际需要来确定具体做什么。来确定具体做什么。比如：对每个结点进比如：对每个结点进行相关计算、输出打行相关计算、输出打印等。印等。树的结点之间不存在树的结点之间不存在唯一的前驱和后继关唯一的前驱和后继关系。由于系。由于选择方式的选择方式的不同，遍历的次序就不同，遍历的次序就完全不同。完全不同。为什么要研究遍历方法？ 计算机只会处理线性序列，而4种遍历方法把树中结点变成某种意义的线性序列；不同的遍历提供了对结点依次处理的不同方式，可以在遍历过程中对结点进行各种处理。 遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。6.8.2

24、二叉树的遍历方法二叉树的遍历方法 二叉树的遍历方式可以很多，如果限制从左到右的习惯方式，则主要分为4种：前序遍历ABCDFGHIE规则：规则：若二叉树为空，若二叉树为空，则空操作返回，否则则空操作返回，否则(1)访问根结点，访问根结点，(2)前序遍历左子树，前序遍历左子树，(3)前序遍历右子树。前序遍历右子树。遍历的顺序为：遍历的顺序为：ABDGHCEIFABDGHCEIF二叉树的前序遍历算法/*二叉树的前序遍历递归算法二叉树的前序遍历递归算法*/void PreOrderTraverse(BiTree T)if (T = NULL)return;printf(%c, T-data);/显示结

25、点数据显示结点数据PreOrderTraverse(T-lchild);/先序遍历左子树先序遍历左子树PreOrderTraverse(T-rchild);/先序遍历右子树先序遍历右子树中序遍历ABCDFGHIE规则：规则：若二叉树为空，若二叉树为空，则空操作返回，否则则空操作返回，否则从根结点开始，从根结点开始，(1)中序遍历根节点的中序遍历根节点的左子树左子树(2)访问根节点访问根节点(3)中序遍历右子树。中序遍历右子树。中序遍历中序遍历的顺序为的顺序为：GDHBAEICFGDHBAEICF二叉树的中序遍历算法/*二叉树二叉树的的中序中序遍历遍历递归算法递归算法*/void InOrder

26、Traverse(BiTree T)if (T = NULL)return;InOrderTraverse(T-lchild); /中序中序遍历遍历左子树左子树printf(%c, T-data);/显示结点显示结点数据数据InOrderTraverse(T-rchild);/中中序序遍历右子树遍历右子树后序遍历ABCDFGHIE规则：规则：若二叉树为空，若二叉树为空，则空操作返回，否则则空操作返回，否则从左到右先叶子后结从左到右先叶子后结点的方式遍历访问左点的方式遍历访问左右子树，最后是访问右子树，最后是访问根结点。根结点。后后序遍历序遍历的顺序为的顺序为：GHDBIEFCAGHDBIEFC

27、A二叉树的后序遍历算法/*二叉树二叉树的后序遍历的后序遍历递归算法递归算法*/void PostOrderTraverse(BiTree T)if (T = NULL)return;PostOrderTraverse(T-lchild);/后序后序遍历遍历左子树左子树PostOrderTraverse(T-rchild);/后序后序遍历右子遍历右子树树printf(%c, T-data);/显示结点显示结点数据数据层序遍历ABCDFGHIE规则：规则：若二叉树为空，若二叉树为空，则空操作返回，否则则空操作返回，否则从树的第一层，也就从树的第一层，也就是根结点开始访问，是根结点开始访问，从上而下

28、逐层遍历，从上而下逐层遍历，在同一层中，按从左在同一层中，按从左到右的顺序对结点逐到右的顺序对结点逐个访问。个访问。层序遍历层序遍历的顺序为的顺序为：ABCDEFGHIABCDEFGHI练习：求出二叉树的先序、中序、后序遍历结果。先序遍历结果：ABDEGHCFI中序遍历结果：DBGEHACFI后序遍历结果：DGHEBIFCA练习：求出二叉树的先序、中序、后序遍历结果。G HD E FB CA先序遍历结果：ABDGCEFH中序遍历结果：DGBAECHF后序遍历结果：GDBEHFCA练习-+/a*b-efcd先序遍历结果：- + a * b c d / e f中序遍历结果：a + b * c d

29、e / f后序遍历结果：a b c d - * + e f / -层序遍历结果：- + / a * e f b c d6.8.6 推推导导遍历结果遍历结果已知一棵二叉树的前序遍历序列为ABCDEF，中序遍历序列为CBAEDF，请问这棵二叉树的后序遍历序列结果是多少？二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，求前序序列？二叉树遍历的性质注意：已知前序和后序遍历是不能确定一棵二叉树的。已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。后序序列：CBEFDA前序序列：EACBDGF6.9 二叉树的建立二叉树的建立如果我们

30、要在内存中建立一个如下图的树，为了能让每个结点确认是否有左右孩子，我们对它进行了扩展，即将二叉树中每个结点的空指针引出一个虚结点，其值为一个特定值。我们称这种处理后的二叉树为原二叉树的扩展二叉树。ABCDABCD# # # # # #原二叉树原二叉树扩展扩展二叉树二叉树假设二叉树的结点均为一个字符，扩展二叉树的前序遍历序列结果是多少？将该前序遍历序列用键盘一次键入，就生成该二叉树。实现代码见下页：ABCD# # # # # #扩展扩展二叉树二叉树前序遍历前序遍历序：序：AB#D#C#/*按前序输入二叉树中结点的值（一个字符）按前序输入二叉树中结点的值（一个字符）*/*#表示空树，构造二叉链表表

31、示二叉树表示空树，构造二叉链表表示二叉树T*/void CreateBitree(BiTree *T)TElemType ch;scanf(%c, &ch);if (ch = #)*T = NULL;else*T=(BiTree)malloc(sizeof(BiTNode);if (!*T)exit(OVERFLOW);(*T)-data = ch;/生成根结点生成根结点CreateBitree(&(*T)-lchild);/构造左子树构造左子树CreateBitree(&(*T)-rchild);/构造右子树构造右子树基本操作：构造空二叉树基本操作：构造空二叉树/*构

32、造空二叉树构造空二叉树T*/Status InitBiTree(BiTree *T)*T = NULL;return OK;课堂练习 建立二叉树，并实现二叉树的3种遍历的递归算法 void CreateBiTree(BiTree *T) void PreOrderTraverse(BiTree T) void InOrderTraverse(BiTree T) void PostOrderTraverse(BiTree T) 要求：在编译器上调试通过写到作业本上，提交纸质作业。6.10 线索线索二叉树二叉树线索二叉树原理ABCDE F 头指针 G H I J 观察：指针域有许多“”(空指针域)

33、。想办法利用起来？！中序遍历：HDIBJEAFCG清楚的知道任意一个结点的前驱和后继。考虑利用空地址存放指向结点的某种遍历次序下的前驱和后继结点的地址。6.10.1 线索二叉树原理线索二叉树原理线索线索线索链表线索链表线索二叉树线索二叉树线索化线索化指向前驱和后继的指针。按照不同的遍历次序进行线索化，可得到不同的线索二叉树。加上线索的二叉链表。对二叉树以某种次序遍历使其变为线索二叉树的过程。把二叉树进行中序遍历后，将所有的空指针域中的rchilid改为指向它的后继结点。ABCDE F G HI J头指针NULL中 序 遍 历 ：HDIBJEAFCG共有共有6 6个空指针个空指针域被利用。域被利

34、用。把二叉树的所有空指针域中的lchilid改为指向当前结点的前驱。ABCDEFGHIJ头指针NULL中 序 遍 历 ：HDIBJEAFCG共有共有5 5个空指针个空指针域被利用。域被利用。把一棵二叉树转变成一个双向链表ABCDFGHIEJ 如何知道某一结点的lchild是指向它的左孩子还是指向前驱？rchild是指向它的右孩子还是后继？再增设两个标志域ltag和rtag，只是存放0或1数字的布尔型变量。结点结构为 ltag=0，指向该结点的左孩子； ltag=1，指向该结点的前驱。 rtag=0，指向该结点的右孩子； rtag=1，指向该结点的后继。lchildltagdatartagrch

35、ild二叉链表图修改后，如下图0 A 0头指针1 G 10 B 00 D 01 H 11I11 J 11 F 10 C 00 E 16.10.2 线索二叉树结构实现线索二叉树结构实现/*二叉树的二叉线索存储结构定义二叉树的二叉线索存储结构定义*/*Link=0表示指向左右孩子指针表示指向左右孩子指针*/*Thread=1表示指向前驱或后继的线索表示指向前驱或后继的线索*/typedef enum Link, Thread PointerTag; typedef struct BiThrNode/二叉线索存储结点结构二叉线索存储结点结构TElemType data;/结点数据结点数据struct

36、 BiThrNode *lchild, *rchild;/左右孩子指针左右孩子指针PointerTag LTag;PointerTag RTag;/左右标志左右标志BiThrNode,*BiThrTree;知识回顾知识回顾(枚举类型枚举类型)适用情况：一个变量只有几种可能的值。枚举：把可能的值一一列举出来，变量的值只限于列举出来的值的范围内。声明枚举类型的一般形式 enum 枚举名 枚举元素列表 例：enum Weekday sun,mon,tue,wed,thu,fri,sat;使用枚举类型定义变量 例：enum Weekday workday,weekend;枚举变量线索化的过程就是在遍历

37、的过程中修改空指针的过程。中序遍历线索化的递归函数代码：BiThrTree pre;/全局变量，始终指向刚刚访问过的结点全局变量，始终指向刚刚访问过的结点void InThreading(BiThrTree p)if (p)InThreading(p-lchild);/递归左子树线索化递归左子树线索化if (!p-lchild)/没有左孩子没有左孩子p-LTag = Thread;/前驱线索前驱线索p-lchild = pre;/左孩子指针指向前驱左孩子指针指向前驱接上页if (!pre-rchild)/前驱没有右孩子前驱没有右孩子pre-RTag = Thread;/后继线索后继线索pre-

38、LTag = p;/前驱右孩子指针前驱右孩子指针指指/向后继向后继(当前结点当前结点p)pre=p;InThreading(p-rchild);/递归右子树线索化递归右子树线索化6.11 树、森林与二叉树的转换树、森林与二叉树的转换将树转换为二叉树的步骤：01在所有兄弟结在所有兄弟结点之间加一条点之间加一条连线。连线。加线加线02对树中每个结点，对树中每个结点，只保留它与第一个只保留它与第一个孩子结点的连线，孩子结点的连线，删除它与其他孩子删除它与其他孩子结点之间的连线。结点之间的连线。去线去线03以树的根结点为轴以树的根结点为轴心，将整棵树顺时心，将整棵树顺时针旋转一定角度，针旋转一定角度，

39、使之结构层次分明。使之结构层次分明。层次层次调整调整ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI 树转换成的二叉树其右子树一定为空。例：练习：将下面的树转换为二叉树(a) 一般的树ABCDEFGH(b) 相邻兄弟加连线ABCDEFGH(c) 删除双亲与不是第一个孩子的连线ABCDEFGH(d) 整理后的二叉树ABCDEFGH6.11.2 森林转换为二叉树森林转换为二叉树森林转换为二叉树的步骤：1 把每个树转换为二叉树。 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根节点的右孩子，用线连接起来。2例：ABCDEF

40、GHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ拥有三棵树的森林步骤1：森林中每棵树转换为二叉树步骤2：将所有二叉树转换成一棵二叉树练习：将下面森林转换为二叉树ABCKEFGHIDLJ6.11.3 二叉树转换为树二叉树转换为树步骤： 1.加线。加线。若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来。 2.去去线。线。删除原二叉树中所有结点与其右孩子结点的连线。 3.层次调整。层次调整。使之结构层次分明。例：ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI练习：将下列二叉树转换

41、为树(d) 一般树ABCDEFGH(a) 二叉树ABCDEFGH(b) 添加连线ABCDEFGH(c) 删除连线ABCDEFGH6.11.4 二叉树转换为森林二叉树转换为森林步骤： 抹抹线：线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树。 还原：还原：将孤立的二叉树还原成树。例：ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ二叉树步骤1：寻找右孩子去线步骤2：将分离的二叉树转换成树6.11.5 树与森林的遍历树与森林的遍历树的遍历 1.先根遍历树。先访问树的根结点，再依次先根遍历根的每棵子树。 2.后根遍历

42、树。先依次后根遍历每棵子树，再访问根结点。 例：ABDFCG GE E先根遍历序列：ABEFCDG后根遍历序列：EFBCGDA森林的遍历 1.前序遍历：访问森林中第一棵树的根结点，再依次先根遍历根的每棵子树，然后依次用同样的方式遍历除去第一棵树的剩余树构成的森林。 2.后序遍历：先访问森林中第一棵树，后根遍历的方式遍历每棵子树，再访问根结点，然后依次同样方式遍历除去第一棵树的剩余树构成的森林。6.12 赫夫曼树及其应用赫夫曼树及其应用赫夫曼树(举例) 有些课程需要将最终的分数由百分制转换成五级分制：if (a60)b=“不及格不及格”else if (a70)b=“及格及格”else if (

43、a80)b=“良好良好”else if (a90)b=“中等中等”elseb=“优秀优秀” 如果学生的成绩在5个等级上的分布规律如表所示 将这棵二叉树重新进行分配：分数分数059 6069 7079 8089 90100所占比例5%15%40%30%10%大约占大约占80%80%的成绩都需要的成绩都需要经过经过3 3次以上的判断才可次以上的判断才可以得到结果。以得到结果。从图中感觉，应该效从图中感觉，应该效率要高一些。率要高一些。6.12.2 赫夫曼树定义与原理赫夫曼树定义与原理赫夫曼树的基本概念 例：先把这两棵树简化成叶子结点带权的二叉树。ABCDE515403010CD DEA AB515403010二叉树a二叉树b权权(Weight)：树结点间的边树结点间的边相关