数据结构课件：第6章树和二叉树.ppt

1、数数 据据 结结 构构 测测 绘绘 学学 院院一、教学内容：一、教学内容：1、树和森林的概念（树的定义、树的术语、性质、树和森林的概念（树的定义、树的术语、性质 及及运算）；运算）；2、二叉树的定义、性质及运算；、二叉树的定义、性质及运算；3、二叉树的存储结构（顺序、链式表示）；、二叉树的存储结构（顺序、链式表示）；4、遍历二叉树、遍历二叉树5、树的存储结构；树、森林与二叉树的转换；遍历、树的存储结构；树、森林与二叉树的转换；遍历树；遍历森林树；遍历森林6、哈夫曼树、哈夫曼编码。、哈夫曼树、哈夫曼编码。数数 据据 结结 构构 测测 绘绘 学学 院院二、教学要求：二、教学要求：1、了解树和森林的

2、概念。包括树的定义、树、了解树和森林的概念。包括树的定义、树的术语和性质；的术语和性质；2、熟练掌握二叉树的结构特性，熟悉二叉树、熟练掌握二叉树的结构特性，熟悉二叉树的各种存储结构的特点及适用范围；的各种存储结构的特点及适用范围；3、熟练掌握二叉树的遍历方法及遍历算法；、熟练掌握二叉树的遍历方法及遍历算法；4、熟悉树的各种存储结构及其特点，掌握树、熟悉树的各种存储结构及其特点，掌握树、森林与二叉树的转换方法、森林与二叉树的转换方法5.掌握哈夫曼树的概念、哈夫曼编码。掌握哈夫曼树的概念、哈夫曼编码。数数 据据 结结 构构 测测 绘绘 学学 院院树是一类重要的非线性数据结构，是以分支关系定义的树是

3、一类重要的非线性数据结构，是以分支关系定义的层次结构层次结构6.1 树的定义树的定义 定义定义 定义：树定义：树(tree)是是n(n=0)个结点的有限集个结点的有限集T，其中：其中： 有且仅有一个特定的结点，称为树的有且仅有一个特定的结点，称为树的根根(root) 当当n1时，其余结点可分为时，其余结点可分为m(m0)个个互不相交的互不相交的有限集有限集T1,T2,Tm，其中每一个集合本身又是一其中每一个集合本身又是一棵树，称为根的棵树，称为根的子树子树(subtree) 特点：特点： 树中至少有一个结点树中至少有一个结点根根 树中各子树是互不相交的集合树中各子树是互不相交的集合数数 据据

4、结结 构构 测测 绘绘 学学 院院数据对象数据对象 D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。 若若D为空集，则称为空树为空集，则称为空树 。 否则否则: (1) 在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root； (2) 当当n1时，其余结点可分为时，其余结点可分为m (m0)个互个互 不相交的有限集不相交的有限集T1, T2, , Tm，其中每一，其中每一 棵子集本身又是一棵符合本定义的树，棵子集本身又是一棵符合本定义的树， 称为根称为根root的子树。的子树。 数据关系数据关系 R：数数 据据 结结 构构 测测 绘绘 学学 院院 基本操作

5、：基本操作：查查 找找 类类 插插 入入 类类删删 除除 类类数数 据据 结结 构构 测测 绘绘 学学 院院 Root(T) / 求树的根结点求树的根结点 查找类：查找类：Value(T, cur_e) / 求当前结点的元素值求当前结点的元素值 Parent(T, cur_e) / 求当前结点的双亲结点求当前结点的双亲结点 LeftChild(T, cur_e) / 求当前结点的最左孩子求当前结点的最左孩子 RightSibling(T, cur_e) / 求当前结点的右兄弟求当前结点的右兄弟TreeEmpty(T) / 判定树是否为空树判定树是否为空树 TreeDepth(T) / 求树的深

6、度求树的深度TraverseTree( T, Visit() ) / 遍历遍历数数 据据 结结 构构 测测 绘绘 学学 院院InitTree(&T) / 初始化置空树初始化置空树 插入类：插入类：CreateTree(&T, definition) / 按定义构造树按定义构造树Assign(T, cur_e, value) / 给当前结点赋值给当前结点赋值InsertChild(&T, &p, i, c) / 将以将以c为根的树插入为结点为根的树插入为结点p的第的第i棵子树棵子树数数 据据 结结 构构 测测 绘绘 学学 院院 ClearTree(&T) / 将树清空将树清空 删除类：删除类：D

7、estroyTree(&T) / 销毁树的结构销毁树的结构DeleteChild(&T, &p, i) / 删除结点删除结点p的第的第i棵子树棵子树数数 据据 结结 构构 测测 绘绘 学学 院院A只有根结点的树只有根结点的树ABCDEFGHIJKLM有子树的树有子树的树根根子树子树数数 据据 结结 构构 测测 绘绘 学学 院院 基本术语基本术语 结点结点(node)表示树中的元素，包括数据项及若干表示树中的元素，包括数据项及若干指向其子树的分支指向其子树的分支 结点的度结点的度(degree)结点拥有的子树数结点拥有的子树数 叶子叶子(leaf)度为度为0的结点的结点 孩子孩子(child)结

8、点子树的根称为该结点的孩子结点子树的根称为该结点的孩子 双亲双亲(parents)孩子结点的上层结点叫该结点的双孩子结点的上层结点叫该结点的双亲亲 兄弟兄弟(sibling)同一双亲的孩子同一双亲的孩子 树的度树的度一棵树中最大的结点度数一棵树中最大的结点度数 结点的层次结点的层次(level)从根结点算起，根为第一层，从根结点算起，根为第一层，它的孩子为第二层它的孩子为第二层 深度深度(depth)树中结点的最大层次数树中结点的最大层次数数数 据据 结结 构构 测测 绘绘 学学 院院ABCDEFGHIJKLM结点结点A的度：的度：3结点结点B的度：的度：2结点结点M的度：的度：0叶子：叶子：

9、K，L，F，G，M，I，J结点结点A的孩子：的孩子：B，C，D结点结点B的孩子：的孩子：E，F结点结点I的双亲：的双亲：D结点结点L的双亲：的双亲：E结点结点B，C，D为兄弟为兄弟结点结点K，L为兄弟为兄弟树的度：树的度：3结点结点A的层次：的层次：1结点结点M的层次：的层次：4树的深度：树的深度：4结点结点F，G为堂兄弟为堂兄弟结点结点A是结点是结点F，G的祖先的祖先数数 据据 结结 构构 测测 绘绘 学学 院院bacghdefij数数 据据 结结 构构 测测 绘绘 学学 院院教师教师学生学生其他人员其他人员99级级 2000级级 2001级级 2002级级华中科技大学华中科技大学计算机系计

10、算机系电信系电信系自控系自控系叶子叶子根根子树子树数数 据据 结结 构构 测测 绘绘 学学 院院abdeijfcgh数数 据据 结结 构构 测测 绘绘 学学 院院ijdfghabcea ( b ( d, e ( i, j ),f), c ( g, h ) ) )数数 据据 结结 构构 测测 绘绘 学学 院院任何一棵非空树是一个二元组 Tree = （root，F）其中：root 被称为根结点 F 被称为子树森林森林：森林：是m（m0）棵互不相交的树的集合ArootBCDEFGHIJMKLF数数 据据 结结 构构 测测 绘绘 学学 院院对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构

11、特点数数 据据 结结 构构 测测 绘绘 学学 院院线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )数数 据据 结结 构构 测测 绘绘 学学 院院 6.2 二叉树二叉树 定义定义 定义：二叉树是定义：二叉树是n(n 0)个结点的有限集，它或为空树个结点的有限集，它或为空树(n

12、=0)，或由一个根结点和两棵分别称为左子树和右子树或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成的互不相交的二叉树构成 特点特点 每个结点至多有二棵子树每个结点至多有二棵子树(即不存在度大于即不存在度大于2的结点的结点) 二叉树的子树有左、右之分，且其次序不能任意颠倒二叉树的子树有左、右之分，且其次序不能任意颠倒A只有根结点只有根结点的二叉树的二叉树 空二叉树空二叉树AB右子树为空右子树为空AB左子树为空左子树为空ABC左、右子树左、右子树均非空均非空数数 据据 结结 构构 测测 绘绘 学学 院院 性质性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i1)用归

13、纳法证明用归纳法证明： 归纳基归纳基： 归纳假设：归纳假设： 归纳证明：归纳证明：i = 1 层时，只有一个根结点： 2i-1 = 20 = 1；假设对所有的 j，1 j i，命题成立；二叉树上每个结点至多有两棵子树，则第 i 层的结点数 = 2i-2 2 = 2i-1 。数数 据据 结结 构构 测测 绘绘 学学 院院 性质性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k1）。证明：证明： 基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+ +2k-1 = 2k-1 。数数 据据 结结 构构 测测 绘绘 学学 院院性质性质3 3：对任何一棵二叉树：对任何一棵二叉

14、树T T，如果其终端结如果其终端结点数为点数为n0n0，度为度为2 2的结点数为的结点数为n2n2，则则n0=n2+1n0=n2+1证明：证明：n1n1为二叉树为二叉树T T中度为中度为1 1的结点数的结点数 因为：二叉树中所有结点的度均小于或等于因为：二叉树中所有结点的度均小于或等于2 2 所以：其结点总数所以：其结点总数n=n0+n1+n2n=n0+n1+n2 又二叉树中，除根结点外，其余结点都只有一又二叉树中，除根结点外，其余结点都只有一 个分支进入个分支进入 设设B B为分支总数，则为分支总数，则n=B+1n=B+1 又：分支由度为又：分支由度为1 1和度为和度为2 2的结点射出，的结

15、点射出， B=n1+2n2B=n1+2n2 于是，于是，n=B+1=n1+2n2+1=n0+n1+n2n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1n0=n2+1数数 据据 结结 构构 测测 绘绘 学学 院院 几种特殊形式的二叉树几种特殊形式的二叉树 满二叉树满二叉树 定义：定义：12个结点的二叉树称为且有一棵深度为kk 特点：每一层上的结点数都是最大结点数特点：每一层上的结点数都是最大结点数 完全二叉树完全二叉树 定义：深度为定义：深度为k，有有n个结点的二叉树当且仅当其个结点的二叉树当且仅当其每一个结点都与深度为每一个结点都与深度为k的满二叉树中编号从的满二叉树中编号从1至

16、至n的结点一一对应时，称为的结点一一对应时，称为 特点特点 叶子结点只可能在层次最大的两层上出现叶子结点只可能在层次最大的两层上出现 对任一结点，若其右分支下子孙的最大层次为对任一结点，若其右分支下子孙的最大层次为L，则其左分支下子孙的最大层次必为则其左分支下子孙的最大层次必为L 或或L+1数数 据据 结结 构构 测测 绘绘 学学 院院1231145891213671014151231145891267101234567123456数数 据据 结结 构构 测测 绘绘 学学 院院 性质性质 4 ： 具有 n 个结点的完全二叉树的深度深度为 log2n +1 。证明：证明：设设完全二叉树的深度为

17、k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n 1i1，则其双亲是则其双亲是 i/2i/2 (2) (2) 如果如果2 2inin，则结点则结点i i无左孩子；无左孩子；如果如果2 2i i n n，则其左孩子是则其左孩子是2 2i i (3) (3) 如果如果2 2i+1ni+1n，则结点则结点i i无右孩子无右孩子；如果；如果2 2i+1i+1 n n，则其右孩子是则其右孩子是2 2i+1i+1数数 据据 结结 构构 测测 绘绘 学学 院院6.2.3 二叉树的存储结构二叉树的存储结构二、二叉树的链式二、二叉树的链式 存储表示存储表示一、一、 二叉树的顺序二叉树的顺序

18、存储表示存储表示数数 据据 结结 构构 测测 绘绘 学学 院院#define MAX_TREE_SIZE 100 / 二叉树的最大结点数typedef TElemType SqBiTreeMAX_ TREE_SIZE; / 0号单元存储根结点SqBiTree bt;一、一、 二叉树的顺序存储表示二叉树的顺序存储表示数数 据据 结结 构构 测测 绘绘 学学 院院实现：按满二叉树的结点层次编号，依次存放二叉树实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素中的数据元素特点：特点： 结点间关系蕴含在其存储位置中结点间关系蕴含在其存储位置中 浪费空间，适于存满二叉树和完全二叉树浪费空间，适于

19、存满二叉树和完全二叉树abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11数数 据据 结结 构构 测测 绘绘 学学 院院二、二叉树的链式存储表示二、二叉树的链式存储表示1. 1. 二叉链表二叉链表2三叉链表三叉链表数数 据据 结结 构构 测测 绘绘 学学 院院ADEBCF rootlchild data rchild结点结构结点结构:1. 1. 二叉链表二叉链表数数 据据 结结 构构 测测 绘绘 学学 院院typedef struct BiTNode / 结点结构结点结构 TElemType data; struct BiTNode *lch

20、ild, *rchild; / 左右孩子指针 BiTNode, *BiTree;lchild data rchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下: :数数 据据 结结 构构 测测 绘绘 学学 院院ADEBCF root 2三叉链表三叉链表parent lchild data rchild结点结构结点结构:数数 据据 结结 构构 测测 绘绘 学学 院院 “遍历遍历”是任何类型均有的操作，对线性结是任何类型均有的操作，对线性结构而言，只有一条搜索路径构而言，只有一条搜索路径(因为每个结点均只因为每个结点均只有一个后继有一个后继)，。而二叉树是非线性结构，。而二叉树是非

21、线性结构，顺着顺着某一条搜索路径某一条搜索路径巡访巡访二叉树中的结点，使得每二叉树中的结点，使得每个结点个结点均被访问一次均被访问一次，而且，而且仅被访问一次仅被访问一次。6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树二叉树的遍历二叉树的遍历数数 据据 结结 构构 测测 绘绘 学学 院院 1先上后下先上后下的按层次遍历；的按层次遍历； 2先左先左（子树）（子树）后右后右（子树）的遍历；（子树）的遍历； 3先右先右（子树）（子树）后左后左（子树）的遍历。（子树）的遍历。数数 据据 结结 构构 测测 绘绘 学学 院院二、先左后右的遍历算法二、先左后右的遍历算法先先（根）序的遍历算法中中（根）

22、序的遍历算法后后（根）序的遍历算法数数 据据 结结 构构 测测 绘绘 学学 院院 若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：先（根）序的遍历算法：数数 据据 结结 构构 测测 绘绘 学学 院院ADBCD L RAD L RD L RBDCD L R先序遍历序列：A B D C先序遍历:数数 据据 结结 构构 测测 绘绘 学学 院院 若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：中（根）序的遍历算法：数数 据据 结结 构构 测测 绘绘 学学 院院ADBC

23、L D RBL D RL D RADCL D R中序遍历序列：B D A C中序遍历:数数 据据 结结 构构 测测 绘绘 学学 院院 若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：后（根）序的遍历算法：数数 据据 结结 构构 测测 绘绘 学学 院院ADBC L R DL R DL R DADCL R D后序遍历序列： D B C A后序遍历:B数数 据据 结结 构构 测测 绘绘 学学 院院-+/a*b-efcd先序遍历：先序遍历：中序遍历：中序遍历：后序遍历：后序遍历：- +a * b - c d / e f-+a*b-cd

24、/ef-+a*b-c d/e f数数 据据 结结 构构 测测 绘绘 学学 院院void preorder(JD *bt) if(bt!=NULL) printf(%dt,bt-data); preorder(bt-lchild); preorder(bt-rchild); 主程序主程序Pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左

25、是空返回T右是空返回pre(T R);先序序列：A B D C数数 据据 结结 构构 测测 绘绘 学学 院院下面我们再给出两种遍历二叉树的方法：下面我们再给出两种遍历二叉树的方法： （1）对一棵二叉树中序遍历时，若我们将二叉树严）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列。顺序就是该二叉树的中序

26、遍历序列。数数 据据 结结 构构 测测 绘绘 学学 院院D G B A E C H F G HD E FB CA数数 据据 结结 构构 测测 绘绘 学学 院院 （2）任何一棵二叉树都可以将它的外部轮廓用）任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。这条包线对于理解二叉树的遍历过程很有用。G HD E FB CA数数 据据 结结 构构 测测 绘绘 学学 院院 由此可以看出：（由此可以看出：（1）遍历操作实际）遍历操作实际上是将非线性结构线性化的过程，其结上是将非线性结构线性化的过程

27、，其结果为线性序列，并根据采用的遍历顺序果为线性序列，并根据采用的遍历顺序分别称为先序序列、中序序列或后序序分别称为先序序列、中序序列或后序序列；（列；（2）遍历操作是一个递归的过程，）遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递因此，这三种遍历操作的算法可以用递归函数实现。归函数实现。数数 据据 结结 构构 测测 绘绘 学学 院院1）先序遍历递归算法）先序遍历递归算法 void PreOrder(BTree BT) if (BT) Visit(BT); PreOrder(BT-Lchild); PreOrder(BT-Rchild); 数数 据据 结结 构构 测测 绘绘 学学

28、 院院（2）中序遍历递归算法）中序遍历递归算法void InOrder(BTree BT) if (BT) InOrder(BT-Lchild); Visit(BT); InOrder(BT-Rchild); 数数 据据 结结 构构 测测 绘绘 学学 院院（3）后序遍历递归算法）后序遍历递归算法void PostOrder(BTree BT) if (BT) PostOrder(BT-Lchild); PostOrder(BT-Rchild); Visit(BT); ;数数 据据 结结 构构 测测 绘绘 学学 院院遍历算法应用遍历算法应用1 按先序遍历序列建立二叉树的二叉链表，已知先按先序遍历

29、序列建立二叉树的二叉链表，已知先序序列为：序序列为： A B C # # D E # G # # F # # #ABCDEFG A B C D E F G 数数 据据 结结 构构 测测 绘绘 学学 院院 为了保证唯一地构造出所希望的二叉树，在键为了保证唯一地构造出所希望的二叉树，在键入这棵树的先序序列时，需要在所有空二叉树的入这棵树的先序序列时，需要在所有空二叉树的位置上填补一个特殊的字符，比如，位置上填补一个特殊的字符，比如，#。在算法。在算法中，需要对每个输入的字符进行判断，如果对应中，需要对每个输入的字符进行判断，如果对应的字符是的字符是#，则在相应的位置上构造一棵空二叉，则在相应的位置

30、上构造一棵空二叉树；否则，创建一个新结点。整个算法结构以先树；否则，创建一个新结点。整个算法结构以先序遍历递归算法为基础，二叉树中结点之间的指序遍历递归算法为基础，二叉树中结点之间的指针连接是通过指针参数在递归调用返回时完成。针连接是通过指针参数在递归调用返回时完成。数数 据据 结结 构构 测测 绘绘 学学 院院 typedef struct BTNode ElemType data; struct BTNode *Lchild, *Rchild; BTNode, *BTree;数数 据据 结结 构构 测测 绘绘 学学 院院BTree PreCreate_BT( ) BTree BT; get

31、ch(ch); if (ch=#) return NULL; /构造空树构造空树 /构造新结点构造新结点 BT=(BTree)malloc(sizeof(BTNode); BT-data=ch; BT-lchild =PreCreate_BT( ); /构造左子树构造左子树 BT-rchild =PreCreate_BT( ); /构造右子树构造右子树 return BT;数数 据据 结结 构构 测测 绘绘 学学 院院2. 2. 计算一棵二叉树的叶子结点数目计算一棵二叉树的叶子结点数目 这个操作可以使用三种遍历顺序中的任何一种，这个操作可以使用三种遍历顺序中的任何一种，只是需要将访问操作变成判

32、断该结点是否为叶子结点只是需要将访问操作变成判断该结点是否为叶子结点，如果是叶子结点将累加器加，如果是叶子结点将累加器加1即可。下面这个算法即可。下面这个算法是利用中序遍历实现的。是利用中序遍历实现的。数数 据据 结结 构构 测测 绘绘 学学 院院void Leaf(BTree BT, int &count) if (!BT) return; Leaf(BT-Lchild, count); /计算左子树的叶子结计算左子树的叶子结点个数点个数 if (BT-Lchild=NULL&BT-Rchild=NULL) count+; Leaf(BT-Rchild, count); /计算右子树的叶子结

33、计算右子树的叶子结点个数点个数 数数 据据 结结 构构 测测 绘绘 学学 院院3 3 求二叉树的高度求二叉树的高度 这个操作使用后序遍历比较符合人们求这个操作使用后序遍历比较符合人们求解二叉树高度的思维方式。首先分别求出左解二叉树高度的思维方式。首先分别求出左右子树的高度，在此基础上得出该棵树的高右子树的高度，在此基础上得出该棵树的高度，即左右子树较大的高度值加度，即左右子树较大的高度值加1。数数 据据 结结 构构 测测 绘绘 学学 院院int hight(BTree BT) /h1和和h2分别是以分别是以BT为根的左右子树的高为根的左右子树的高度度 double h1, h2; if (BT

34、=NULL) return 0; h1=hight(BT-Lchild); h2=hight(BT-Rchild); return max(h1,h2)+1;数数 据据 结结 构构 测测 绘绘 学学 院院6.3.2线索二叉树遍历二叉树的结果是， 求得结点的一个线性序列。ABCDEFGHK例如:先序先序序列: A B C D E F G H K中序中序序列: B D C A H G K F E后序后序序列: D C B H K G F E A数数 据据 结结 构构 测测 绘绘 学学 院院指向该线性序列中的“前驱”和 “后继” 的指针指针，称作“线索线索”与其相应的二叉树，称作 “线索二叉树线索二

35、叉树”包含 “线索” 的存储结构，称作 “线索链线索链表表”A B C D E F G H K D C B E 数数 据据 结结 构构 测测 绘绘 学学 院院对对线索链表线索链表中结点的约定：中结点的约定： 在二叉链表的结点中增加两个标志域增加两个标志域，并作如下规定：若该结点的左子树不空，若该结点的左子树不空，则Lchild域的指针指向其左子树， 且左标志域的值为“指针 Link”； 否则，Lchild域的指针指向其“前驱”， 且左标志的值为“线索 Thread” 。数数 据据 结结 构构 测测 绘绘 学学 院院若该结点的右子树不空，若该结点的右子树不空，则rchild域的指针指向其右子树，

36、 且右标志域的值为 “指针 Link”；否则，rchild域的指针指向其“后继”， 且右标志的值为“线索 Thread”。 如此定义的二叉树的存储结构称作如此定义的二叉树的存储结构称作“线索链表线索链表”。数数 据据 结结 构构 测测 绘绘 学学 院院typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右指针 PointerThr LTag, RTag; / 左右标志 BiThrNode, *BiThrTree;线索链表的类型描述： typedef enum Link, Thread Poi

37、nterThr; / Link=0:指针，Thread=1:线索数数 据据 结结 构构 测测 绘绘 学学 院院实现实现在有在有n个结点的二叉链表中必定有个结点的二叉链表中必定有n+1个空链域个空链域在线索二叉树的结点中增加两个在线索二叉树的结点中增加两个标志域标志域ltag :若若 ltag=0, lchild 域指向左域指向左孩子；孩子；若若 ltar=1, lchild域指向其前驱域指向其前驱rtag :若若 rtag =0, rchild 域指向域指向右孩子；右孩子；若若 rtag=1, rchild域指向其后继域指向其后继typedef struct node int data; in

38、t ltag, rtag; struct node *lchild, *rchild;JD;数数 据据 结结 构构 测测 绘绘 学学 院院ABCDE A B D C ET先序序列：ABCDE先序线索二叉树00001111 11typedef struct node int data; int ltag, rtag; struct node *lchild, *rchild;JD; lchild ltag data rtag rchild数数 据据 结结 构构 测测 绘绘 学学 院院ABCDE A B D C ET中序序列：BCAED中序线索二叉树0000111111数数 据据 结结 构构 测测

39、 绘绘 学学 院院ABCDE A B D C ET后序序列：CBEDA后序线索二叉树0000111111数数 据据 结结 构构 测测 绘绘 学学 院院ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：中序序列：BCAED带头结点的中序线索二叉树带头结点的中序线索二叉树 0 1头结点：头结点：ltag=0, lchild指向根结点指向根结点rtag=1, rchild指向遍历序列中最后一个结点指向遍历序列中最后一个结点遍历序列中第一个结点的遍历序列中第一个结点的lchild域和最后域和最后一个结点的一个结点的rchild域都指向头结点域都指向头结点 A B D

40、C ET中序序列：中序序列：BCAED中序线索二叉树中序线索二叉树0000111111数数 据据 结结 构构 测测 绘绘 学学 院院目的：在依某种顺序遍历二叉树时修改空指针，添加前驱或后继。目的：在依某种顺序遍历二叉树时修改空指针，添加前驱或后继。注解：为方便添加结点的前驱或后继，需要设置两个指针：注解：为方便添加结点的前驱或后继，需要设置两个指针： p指针指针当前结点之指针；当前结点之指针； pre指针指针前驱结点之指针。前驱结点之指针。技巧：当结点技巧：当结点p的左的左/右域为空时，只改写它的左域（装入前驱右域为空时，只改写它的左域（装入前驱pre），而其右域（后继）留给下一结点来填写。）

41、，而其右域（后继）留给下一结点来填写。 或者说，当前结点的指针或者说，当前结点的指针p应当送到前驱结点的空右域中。应当送到前驱结点的空右域中。若若p-lchildNULL, ,则则p-Ltag=1;p-lchildp-Ltag=1;p-lchildpre;pre; /p /p的前驱结点指针的前驱结点指针prepre存入左空域存入左空域若若pre-rchildNULL, 则则pre-Rtagpre-Rtag1;pre-rchild=p;1;pre-rchild=p; /p /p存入其前驱结点存入其前驱结点prepre的右空域的右空域数数 据据 结结 构构 测测 绘绘 学学 院院void InTh

42、reading(BiThrTree p) if (p) / 对以p为根的非空二叉树进行线索化 InThreading(p-lchild); / 左子树线索化 if (!p-lchild) / 建前驱线索 p-LTag = Thread; p-lchild = pre; if (!pre-rchild) / 建后继线索 pre-RTag = Thread; pre-rchild = p; pre = p; / 保持 pre 指向 p 的前驱 InThreading(p-rchild); / 右子树线索化 / if / InThreading数数 据据 结结 构构 测测 绘绘 学学 院院Statu

43、s InOrderThreading(BiThrTree &Thrt, BiThrTree T) / 构建中序线索链表 if (!(Thrt = (BiThrTree)malloc( sizeof( BiThrNode) exit (OVERFLOW); Thrt-LTag = Link; Thrt-RTag =Thread; Thrt-rchild = Thrt; / 添加头结点 if (!T) Thrt-lchild = Thrt; else 数数 据据 结结 构构 测测 绘绘 学学 院院Thrt-lchild = T; pre = Thrt; InThreading(T); pre-rc

44、hild = Thrt; / 处理最后一个结点 pre-RTag = Thread; Thrt-rchild = pre; return OK; / InOrderThreading 数数 据据 结结 构构 测测 绘绘 学学 院院 算法算法 遍历中序线索二叉树遍历中序线索二叉树在中序线索二叉树中找结点后继的方法：在中序线索二叉树中找结点后继的方法：1）若）若rtag=1, 则则rchild域直接指向其后继域直接指向其后继2）若）若rtag=0, 则结点的后继应是其右子树的左链尾（则结点的后继应是其右子树的左链尾（ltag=1)的结点的结点在中序线索二叉树中找结点前驱的方法：在中序线索二叉树中找

45、结点前驱的方法：1）若）若ltag=1, 则则lchild域直接指向其前驱域直接指向其前驱2）若）若ltag=0, 则结点的前驱应是其左子树的右链尾（则结点的前驱应是其左子树的右链尾（rtag=1)的结点的结点ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：中序序列：BCAED带头结点的中序线索二叉树带头结点的中序线索二叉树 0 1数数 据据 结结 构构 测测 绘绘 学学 院院程序注解程序注解 (非递归，且不用栈非递归，且不用栈）：）：P=T-lchild; /从头结点进入到根结点；从头结点进入到根结点；while( p!=T) while(p-LTag=l

46、ink)p=p-lchild; /先找到中序遍历起点先找到中序遍历起点 if(!visit(p-data) return ERROR; /若起点值为空则出错告警若起点值为空则出错告警 while(p-RTag=Thread &p-rchild!=T) p=p-rchild; Visit(p-data); /若有后继标志，则直接提取若有后继标志，则直接提取p-rchild中线索并中线索并访问后继结点；访问后继结点；p=p-rchild; /当前结点右域不空或已经找好了后继，则一律从当前结点右域不空或已经找好了后继，则一律从结点的右子树开始重复结点的右子树开始重复 的全部过程。的全部过程。retu

47、rn OK;LTag=0RTag=1数数 据据 结结 构构 测测 绘绘 学学 院院6.4 树的存储结构树的存储结构 树的存储结构树的存储结构 双亲表示法双亲表示法实现：定义结构数组存放树的结点，每个实现：定义结构数组存放树的结点，每个结点含两个域：结点含两个域： 数据域：存放结点本身信息数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组双亲域：指示本结点的双亲结点在数组中位置中位置特点：找双亲容易，找孩子难特点：找双亲容易，找孩子难数数 据据 结结 构构 测测 绘绘 学学 院院abcdefhgiacdefghib012235551096012345789dataparent0号单元不

48、用或号单元不用或存结点个数存结点个数如何找孩子结点如何找孩子结点数数 据据 结结 构构 测测 绘绘 学学 院院 typedef struct PTNode Elem data; int parent; / 双亲位置域 PTNode; data parent#define MAX_TREE_SIZE 100结点结构结点结构:C语言的类型描述语言的类型描述: :数数 据据 结结 构构 测测 绘绘 学学 院院typedef struct PTNode nodes MAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数 PTree;树结构树结构:数数 据据 结结 构构 测测 绘绘

49、 学学 院院 孩子表示法孩子表示法多重链表：每个结点有多个指针域，分别指多重链表：每个结点有多个指针域，分别指向其子树的根向其子树的根结点同构：结点的指针个数相等，为树的度结点同构：结点的指针个数相等，为树的度D结点不同构：结点指针个数不等，为该结点的结点不同构：结点指针个数不等，为该结点的度度ddata child1 child2 . childDdata degreechild child2 . childd 孩子链表：每个结点的孩子结点用单链表存储，孩子链表：每个结点的孩子结点用单链表存储，再用含再用含n个元素的结构数组指向每个孩子链表个元素的结构数组指向每个孩子链表数数 据据 结结 构

50、构 测测 绘绘 学学 院院typedef struct CTNode int child; struct CTNode *next; *ChildPtr;孩子结点结构孩子结点结构: child nextC语言的类型描述语言的类型描述: :数数 据据 结结 构构 测测 绘绘 学学 院院 typedef struct Elem data; ChildPtr firstchild; / 孩子链的头指针 CTBox;双亲结点结构双亲结点结构 data firstchild数数 据据 结结 构构 测测 绘绘 学学 院院typedef struct CTBox nodesMAX_TREE_SIZE; in