第6章树和二叉树

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

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

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

9、的度：3结点结点B的度：的度：2结点结点M的度：的度：0叶子：叶子：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级级 200

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

11、树的集合ArootBCDEFGHIJMKLF数数 据据 结结 构构 测测 绘绘 学学 院院对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点数数 据据 结结 构构 测测 绘绘 学学 院院线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )数数 据据 结结 构构 测

12、测 绘绘 学学 院院 6.2 二叉树二叉树 定义定义 定义：二叉树是定义：二叉树是n(n 0)个结点的有限集，它或为空树个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成的互不相交的二叉树构成 特点特点 每个结点至多有二棵子树每个结点至多有二棵子树(即不存在度大于即不存在度大于2的结点的结点) 二叉树的子树有左、右之分，且其次序不能任意颠倒二叉树的子树有左、右之分，且其次序不能任意颠倒A只有根结点只有根结点的二叉树的二叉树 空二叉树空二叉树AB右子树为空右子树为空AB左子树为空左子树为空ABC左、右

13、子树左、右子树均非空均非空数数 据据 结结 构构 测测 绘绘 学学 院院 性质性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i1)用归纳法证明用归纳法证明： 归纳基归纳基： 归纳假设：归纳假设： 归纳证明：归纳证明：i = 1 层时，只有一个根结点：层时，只有一个根结点： 2i-1 = 20 = 1；假设对所有的假设对所有的 j，1 j i，命题成立；命题成立；二叉树上每个结点至多有两棵子树，二叉树上每个结点至多有两棵子树，则第则第 i 层的结点数层的结点数 = 2i-2 2 = 2i-1 。数数 据据 结结 构构 测测 绘绘 学学 院院 性质性质 2 ： 深度为 k 的二叉

14、树上至多含 2k-1 个结点（k1）。证明：证明： 基于上一条性质，深度为基于上一条性质，深度为 k 的二叉的二叉树上的结点数至多为树上的结点数至多为 20+21+ +2k-1 = 2k-1 。数数 据据 结结 构构 测测 绘绘 学学 院院 性质性质3 3：对任何一棵二叉树：对任何一棵二叉树T T，如果其终端结如果其终端结点数为点数为n0n0，度为度为2 2的结点数为的结点数为n2n2，则则n0=n2+1n0=n2+1证明：证明：n1n1为二叉树为二叉树T T中度为中度为1 1的结点数的结点数 因为：二叉树中所有结点的度均小于或等于因为：二叉树中所有结点的度均小于或等于2 2 所以：其结点总数

15、所以：其结点总数n=n0+n1+n2n=n0+n1+n2 又二叉树中，除根结点外，其余结点都只有一又二叉树中，除根结点外，其余结点都只有一 个分支进入个分支进入 设设B B为分支总数，则为分支总数，则n=B+1n=B+1 又：分支由度为又：分支由度为1 1和度为和度为2 2的结点射出，的结点射出， 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个结点的

16、二叉树称为且有一棵深度为kk特点：每一层上的结点数都是最大结点数特点：每一层上的结点数都是最大结点数 完全二叉树完全二叉树定义：深度为定义：深度为k，有有n个结点的二叉树当且仅当其个结点的二叉树当且仅当其每一个结点都与深度为每一个结点都与深度为k的满二叉树中编号从的满二叉树中编号从1至至n的结点一一对应时，称为的结点一一对应时，称为特点特点 叶子结点只可能在层次最大的两层上出现叶子结点只可能在层次最大的两层上出现 对任一结点，若其右分支下子孙的最大层次为对任一结点，若其右分支下子孙的最大层次为L，则其左分支下子孙的最大层次必为则其左分支下子孙的最大层次必为L 或或L+1数数 据据 结结 构构

17、测测 绘绘 学学 院院1231145891213671014151231145891267101234567123456数数 据据 结结 构构 测测 绘绘 学学 院院 性质性质 4 ： 具有具有 n 个结点的完全二叉树的个结点的完全二叉树的深度深度为为 log2n +1 。证明：证明：设完全二叉树的深度为设完全二叉树的深度为 k 则根据第二条性质得则根据第二条性质得 2k-1 n 2k 即即 k-1 log2 n 1i1，则其双亲是，则其双亲是 i/2i/2 (2) (2) 如果如果2 2inin，则结点，则结点i i无左孩子；无左孩子；如果如果2 2i i n n，则其左孩子是，则其左孩子是

18、2 2i i (3) (3) 如果如果2 2i+1ni+1n，则结点，则结点i i无右孩子无右孩子；如果；如果2 2i+1i+1 n n，则其右孩子是，则其右孩子是2 2i+1i+1数数 据据 结结 构构 测测 绘绘 学学 院院6.2.3 二叉树的存储结构二叉树的存储结构二、二叉树的链式二、二叉树的链式 存储表示存储表示一、一、 二叉树的顺序二叉树的顺序 存储表示存储表示数数 据据 结结 构构 测测 绘绘 学学 院院#define MAX_TREE_SIZE 100 / 二叉树的最大结点数二叉树的最大结点数typedef TElemType SqBiTreeMAX_ TREE_SIZE; /

19、0号单元存储根结点号单元存储根结点SqBiTree bt;一、一、 二叉树的顺序存储表示二叉树的顺序存储表示数数 据据 结结 构构 测测 绘绘 学学 院院实现：按满二叉树的结点层次编号，依次存放二叉树实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素中的数据元素特点：特点： 结点间关系蕴含在其存储位置中结点间关系蕴含在其存储位置中 浪费空间，适于存满二叉树和完全二叉树浪费空间，适于存满二叉树和完全二叉树abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11数数 据据 结结 构构 测测 绘绘 学学 院院二、二叉树的链式存储表示二、二叉树的

20、链式存储表示1. 1. 二叉链表二叉链表2三叉链表三叉链表数数 据据 结结 构构 测测 绘绘 学学 院院ADEBCF rootlchild data rchild结点结构结点结构:1. 1. 二叉链表二叉链表数数 据据 结结 构构 测测 绘绘 学学 院院typedef struct BiTNode / 结点结构结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针左右孩子指针 BiTNode, *BiTree;lchild data rchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下: :数数 据据 结结

21、 构构 测测 绘绘 学学 院院ADEBCF root 2三叉链表三叉链表parent lchild data rchild结点结构结点结构:数数 据据 结结 构构 测测 绘绘 学学 院院 “遍历遍历”是任何类型均有的操作，对线性结是任何类型均有的操作，对线性结构而言，只有一条搜索路径构而言，只有一条搜索路径(因为每个结点均只因为每个结点均只有一个后继有一个后继)，。而二叉树是非线性结构，。而二叉树是非线性结构，顺着顺着某一条搜索路径某一条搜索路径巡访巡访二叉树中的结点，使得每二叉树中的结点，使得每个结点个结点均被访问一次均被访问一次，而且，而且仅被访问一次仅被访问一次。6.3 遍历二叉树和线索

22、二叉树遍历二叉树和线索二叉树二叉树的遍历二叉树的遍历数数 据据 结结 构构 测测 绘绘 学学 院院 1先上后下先上后下的按层次遍历；的按层次遍历； 2先左先左（子树）（子树）后右后右（子树）的遍历；（子树）的遍历； 3先右先右（子树）（子树）后左后左（子树）的遍历。（子树）的遍历。数数 据据 结结 构构 测测 绘绘 学学 院院二、先左后右的遍历算法二、先左后右的遍历算法先先（根）序的遍历算法（根）序的遍历算法中中（根）序的遍历算法（根）序的遍历算法后后（根）序的遍历算法（根）序的遍历算法数数 据据 结结 构构 测测 绘绘 学学 院院 若二叉树为空树，则空操作；否则，若二叉树为空树，则空操作；否

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

24、 结结 构构 测测 绘绘 学学 院院ADBCL 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数数 据据 结

25、结 构构 测测 绘绘 学学 院院-+/a*b-efcd先序遍历：先序遍历：中序遍历：中序遍历：后序遍历：后序遍历：- +a * b - c d / e f-+a*b-cd/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);BTApr

26、intf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回返回T左是空返回左是空返回pre(T R);T左是空返回左是空返回T右是空返回右是空返回T左是空返回左是空返回T右是空返回右是空返回pre(T R);先序序列：先序序列：A B D C数数 据据 结结 构构 测测 绘绘 学学 院院下面我们再给出两种遍历二叉树的方法：下面我们再给出两种遍历二叉树的方法： （1）对一棵二叉树中序遍历时，若我们将二叉树严）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树格地按左子树的所有结点位于根结点的

27、左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列。顺序就是该二叉树的中序遍历序列。数数 据据 结结 构构 测测 绘绘 学学 院院D G B A E C H F G HD E FB CA数数 据据 结结 构构 测测 绘绘 学学 院院 （2）任何一棵二叉树都可以将它的外部轮廓用）任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍

28、历过程很有用。这条包线对于理解二叉树的遍历过程很有用。G HD E FB CA数数 据据 结结 构构 测测 绘绘 学学 院院 由此可以看出：（由此可以看出：（1）遍历操作实际）遍历操作实际上是将非线性结构线性化的过程，其结上是将非线性结构线性化的过程，其结果为线性序列，并根据采用的遍历顺序果为线性序列，并根据采用的遍历顺序分别称为先序序列、中序序列或后序序分别称为先序序列、中序序列或后序序列；（列；（2）遍历操作是一个递归的过程，）遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递因此，这三种遍历操作的算法可以用递归函数实现。归函数实现。数数 据据 结结 构构 测测 绘绘 学学 院院

29、1）先序遍历递归算法）先序遍历递归算法 void PreOrder(BTree BT) if (BT) Visit(BT); PreOrder(BT-Lchild); PreOrder(BT-Rchild); 数数 据据 结结 构构 测测 绘绘 学学 院院（2）中序遍历递归算法）中序遍历递归算法void InOrder(BTree BT) if (BT) InOrder(BT-Lchild); Visit(BT); InOrder(BT-Rchild); 数数 据据 结结 构构 测测 绘绘 学学 院院（3）后序遍历递归算法）后序遍历递归算法void PostOrder(BTree BT) if

30、 (BT) PostOrder(BT-Lchild); PostOrder(BT-Rchild); Visit(BT); ;数数 据据 结结 构构 测测 绘绘 学学 院院遍历算法应用遍历算法应用1 按先序遍历序列建立二叉树的二叉链表，已知先按先序遍历序列建立二叉树的二叉链表，已知先序序列为：序序列为： A B C # # D E # G # # F # # #ABCDEFG A B C D E F G 数数 据据 结结 构构 测测 绘绘 学学 院院 为了保证唯一地构造出所希望的二叉树，在键为了保证唯一地构造出所希望的二叉树，在键入这棵树的先序序列时，需要在所有空二叉树的入这棵树的先序序列时，需

31、要在所有空二叉树的位置上填补一个特殊的字符，比如，位置上填补一个特殊的字符，比如，#。在算法。在算法中，需要对每个输入的字符进行判断，如果对应中，需要对每个输入的字符进行判断，如果对应的字符是的字符是#，则在相应的位置上构造一棵空二叉，则在相应的位置上构造一棵空二叉树；否则，创建一个新结点。整个算法结构以先树；否则，创建一个新结点。整个算法结构以先序遍历递归算法为基础，二叉树中结点之间的指序遍历递归算法为基础，二叉树中结点之间的指针连接是通过指针参数在递归调用返回时完成。针连接是通过指针参数在递归调用返回时完成。数数 据据 结结 构构 测测 绘绘 学学 院院 typedef struct BT

32、Node ElemType data; struct BTNode *Lchild, *Rchild; BTNode, *BTree;数数 据据 结结 构构 测测 绘绘 学学 院院BTree PreCreate_BT( ) BTree BT; getch(ch); if (ch=#) return NULL; /构造空树构造空树 /构造新结点构造新结点 BT=(BTree)malloc(sizeof(BTNode); BT-data=ch; BT-lchild =PreCreate_BT( ); /构造左子树构造左子树 BT-rchild =PreCreate_BT( ); /构造右子树构造右

33、子树 return BT;数数 据据 结结 构构 测测 绘绘 学学 院院2. 2. 计算一棵二叉树的叶子结点数目计算一棵二叉树的叶子结点数目 这个操作可以使用三种遍历顺序中的任何一种，这个操作可以使用三种遍历顺序中的任何一种，只是需要将访问操作变成判断该结点是否为叶子结点只是需要将访问操作变成判断该结点是否为叶子结点，如果是叶子结点将累加器加，如果是叶子结点将累加器加1即可。下面这个算法即可。下面这个算法是利用中序遍历实现的。是利用中序遍历实现的。数数 据据 结结 构构 测测 绘绘 学学 院院void Leaf(BTree BT, int &count) if (!BT) return

34、; Leaf(BT-Lchild, count); /计算左子树的叶子结计算左子树的叶子结点个数点个数 if (BT-Lchild=NULL&BT-Rchild=NULL) count+; Leaf(BT-Rchild, count); /计算右子树的叶子结计算右子树的叶子结点个数点个数 数数 据据 结结 构构 测测 绘绘 学学 院院3 3 求二叉树的高度求二叉树的高度 这个操作使用后序遍历比较符合人们求这个操作使用后序遍历比较符合人们求解二叉树高度的思维方式。首先分别求出左解二叉树高度的思维方式。首先分别求出左右子树的高度，在此基础上得出该棵树的高右子树的高度，在此基础上得出该棵树的

35、高度，即左右子树较大的高度值加度，即左右子树较大的高度值加1。数数 据据 结结 构构 测测 绘绘 学学 院院int hight(BTree BT) /h1和和h2分别是以分别是以BT为根的左右子树的高为根的左右子树的高度度 double h1, h2; if (BT=NULL) return 0; h1=hight(BT-Lchild); h2=hight(BT-Rchild); return max(h1,h2)+1;数数 据据 结结 构构 测测 绘绘 学学 院院6.3.2线索二叉树线索二叉树遍历二叉树的结果是，遍历二叉树的结果是， 求得结点的一个线性序列。求得结点的一个线性序列。ABCDE

36、FGHK例如例如: :先序序列先序序列: : 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数数 据据 结结 构构 测测 绘绘 学学 院院指向该线性序列中的指向该线性序列中的“前驱前驱”和和 “后继后继” 的指针，称作的指针，称作“线索线索”与其相应的二叉树，与其相应的二叉树，称作称作 “线索二叉树线索二叉树”包含包含 “线索线索” 的存储的存储结构，称作结构，称作 “线索链线索链表表”A B C D E F G H K D C B E 数数 据据 结结 构构 测测 绘绘 学学 院院对对线索

37、链表线索链表中结点的约定：中结点的约定： 在二叉链表的结点中增加两个标志域，在二叉链表的结点中增加两个标志域，并作如下规定：并作如下规定：若该结点的左子树不空，若该结点的左子树不空，则则Lchild域的指针指向其左子域的指针指向其左子树，树， 且左标志域的值为且左标志域的值为“指针指针 Link”； 否则，否则，Lchild域的指针指向其域的指针指向其“前驱前驱”， 且左标志的值为且左标志的值为“线索线索 Thread” 。数数 据据 结结 构构 测测 绘绘 学学 院院若该结点的右子树不空，若该结点的右子树不空，则则rchild域的指针指向其右子树，域的指针指向其右子树， 且右标志域的值为且右

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

39、述：的类型描述： typedef enum Link, Thread PointerThr; / Link=0:指针，指针，Thread=1:线索线索数数 据据 结结 构构 测测 绘绘 学学 院院实现实现在有在有n个结点的二叉链表中必定有个结点的二叉链表中必定有n+1个空链域个空链域在线索二叉树的结点中增加两个在线索二叉树的结点中增加两个标志域标志域ltag :若若 ltag=0, lchild 域指向左域指向左孩子；孩子；若若 ltar=1, lchild域指向其前驱域指向其前驱rtag :若若 rtag =0, rchild 域指向域指向右孩子；右孩子；若若 rtag=1, rchild域

40、指向其后继域指向其后继typedef struct node int data; int 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数数 据据 结结 构构 测测 绘绘 学学 院院AB

41、CDE A B D C ET中序序列：中序序列：BCAED中序线索二叉树中序线索二叉树0000111111数数 据据 结结 构构 测测 绘绘 学学 院院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指向遍历序列中最后一个结点指向遍历序列中

42、最后一个结点遍历序列中第一个结点的遍历序列中第一个结点的lchild域和最后域和最后一个结点的一个结点的rchild域都指向头结点域都指向头结点 A B D C ET中序序列：中序序列：BCAED中序线索二叉树中序线索二叉树0000111111数数 据据 结结 构构 测测 绘绘 学学 院院目的：在依某种顺序遍历二叉树时修改空指针，添加前驱或后继。目的：在依某种顺序遍历二叉树时修改空指针，添加前驱或后继。注解：为方便添加结点的前驱或后继，需要设置两个指针：注解：为方便添加结点的前驱或后继，需要设置两个指针： p指针指针当前结点之指针；当前结点之指针； pre指针指针前驱结点之指针。前驱结点之指针

43、。技巧：当结点技巧：当结点p的左的左/右域为空时，只改写它的左域（装入前驱右域为空时，只改写它的左域（装入前驱pre），而其右域（后继）留给下一结点来填写。），而其右域（后继）留给下一结点来填写。 或者说，当前结点的指针或者说，当前结点的指针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;

44、pre-rchild=p; /p /p存入其前驱结点存入其前驱结点prepre的右空域的右空域数数 据据 结结 构构 测测 绘绘 学学 院院void InThreading(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

45、= p; pre = p; / 保持保持 pre 指向指向 p 的前驱的前驱 InThreading(p-rchild); / 右子树线索化右子树线索化 / if / InThreading数数 据据 结结 构构 测测 绘绘 学学 院院Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) / 构建中序线索链表构建中序线索链表 if (!(Thrt = (BiThrTree)malloc( sizeof( BiThrNode) exit (OVERFLOW); Thrt-LTag = Link; Thrt-RTag =Thread;

46、Thrt-rchild = Thrt; / 添加头结点添加头结点 if (!T) Thrt-lchild = Thrt; else 数数 据据 结结 构构 测测 绘绘 学学 院院Thrt-lchild = T; pre = Thrt; InThreading(T); pre-rchild = Thrt; / 处理最后一个结点处理最后一个结点 pre-RTag = Thread; Thrt-rchild = pre; return OK; / InOrderThreading 数数 据据 结结 构构 测测 绘绘 学学 院院 算法算法遍历中序线索二叉树遍历中序线索二叉树在中序线索二叉树中找结点后继

47、的方法：在中序线索二叉树中找结点后继的方法：1）若）若rtag=1, 则则rchild域直接指向其后继域直接指向其后继2）若）若rtag=0, 则结点的后继应是其右子树的左链尾（则结点的后继应是其右子树的左链尾（ltag=1)的结点的结点在中序线索二叉树中找结点前驱的方法：在中序线索二叉树中找结点前驱的方法：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中序序列：中序序列：B

48、CAED带头结点的中序线索二叉树带头结点的中序线索二叉树 0 1数数 据据 结结 构构 测测 绘绘 学学 院院程序注解程序注解 (非递归，且不用栈非递归，且不用栈）：）：P=T-lchild; /从头结点进入到根结点；从头结点进入到根结点；while( p!=T) while(p-LTag=link)p=p-lchild; /先找到中序遍历起点先找到中序遍历起点 if(!visit(p-data) return ERROR; /若起点值为空则出错告警若起点值为空则出错告警 while(p-RTag=Thread &p-rchild!=T) p=p-rchild; Visit(p-dat

49、a); /若有后继标志，则直接提取若有后继标志，则直接提取p-rchild中线索并中线索并访问后继结点；访问后继结点；p=p-rchild; /当前结点右域不空或已经找好了后继，则一律从当前结点右域不空或已经找好了后继，则一律从结点的右子树开始重复结点的右子树开始重复 的全部过程。的全部过程。return OK;LTag=0RTag=1数数 据据 结结 构构 测测 绘绘 学学 院院6.4 树的存储结构树的存储结构 树的存储结构树的存储结构 双亲表示法双亲表示法实现：定义结构数组存放树的结点，每个实现：定义结构数组存放树的结点，每个结点含两个域：结点含两个域： 数据域：存放结点本身信息数据域：存

50、放结点本身信息 双亲域：指示本结点的双亲结点在数组双亲域：指示本结点的双亲结点在数组中位置中位置特点：找双亲容易，找孩子难特点：找双亲容易，找孩子难数数 据据 结结 构构 测测 绘绘 学学 院院abcdefhgiacdefghib012235551096012345789dataparent0号单元不用或号单元不用或存结点个数存结点个数如何找孩子结点如何找孩子结点数数 据据 结结 构构 测测 绘绘 学学 院院 typedef struct PTNode Elem data; int parent; / 双亲位置域双亲位置域 PTNode; data parent#define MAX_TREE

51、_SIZE 100结点结构结点结构:C语言的类型描述语言的类型描述: :数数 据据 结结 构构 测测 绘绘 学学 院院typedef struct PTNode nodes MAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数根结点的位置和结点个数 PTree;树结构树结构:数数 据据 结结 构构 测测 绘绘 学学 院院 孩子表示法孩子表示法多重链表：每个结点有多个指针域，分别指多重链表：每个结点有多个指针域，分别指向其子树的根向其子树的根结点同构：结点的指针个数相等，为树的度结点同构：结点的指针个数相等，为树的度D结点不同构：结点指针个数不等，为该结点的结点不同构：结

52、点指针个数不等，为该结点的度度ddata child1 child2 . childDdata degreechild child2 . childd 孩子链表：每个结点的孩子结点用单链表存储，孩子链表：每个结点的孩子结点用单链表存储，再用含再用含n个元素的结构数组指向每个孩子链表个元素的结构数组指向每个孩子链表数数 据据 结结 构构 测测 绘绘 学学 院院typedef struct CTNode int child; struct CTNode *next; *ChildPtr;孩子结点结构孩子结点结构: child nextC语言的类型描述语言的类型描述: :数数 据据 结结 构构 测测

53、 绘绘 学学 院院 typedef struct Elem data; ChildPtr firstchild; / 孩子链的头指针孩子链的头指针 CTBox;双亲结点结构双亲结点结构 data firstchild数数 据据 结结 构构 测测 绘绘 学学 院院typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 结点数和根结点的位置结点数和根结点的位置 CTree;树结构树结构:数数 据据 结结 构构 测测 绘绘 学学 院院abcdefhgi6012345789acdefghibdata fc 2 3 4 5 9 7 8 6如何找双亲结点如

54、何找双亲结点数数 据据 结结 构构 测测 绘绘 学学 院院带双亲的孩子链表带双亲的孩子链表612345789acdefghibdatafc 2 3 4 5 9 7 8 6012235551parentabcdefhgi数数 据据 结结 构构 测测 绘绘 学学 院院 孩子兄弟表示法（二叉树表示法）孩子兄弟表示法（二叉树表示法）实现：用二叉链表作树的存储结构，链表中每个实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点下一个兄弟结点特点特点 1 操作容易操作容易 2 破坏了树的层次破坏了树的层次abcdefh

55、gi a b c d e f g h i数数 据据 结结 构构 测测 绘绘 学学 院院typedef struct CSNode Elem data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;C语言的类型描述语言的类型描述: :结点结构结点结构: firstchild data nextsibling数数 据据 结结 构构 测测 绘绘 学学 院院 树与二叉树转换树与二叉树转换ACBED树树ABCDE二叉树二叉树 A B C D E A B C D E A B C D E 对应对应存储存储存储存储解释解释解释解释数数 据据

56、 结结 构构 测测 绘绘 学学 院院 将树转换成二叉树将树转换成二叉树加线：在兄弟之间加一连线加线：在兄弟之间加一连线抹线：对每个结点，除了其左孩子外，去除其与其抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系余孩子之间的关系旋转：以树的根结点为轴心，将整树顺时针转旋转：以树的根结点为轴心，将整树顺时针转45ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI树转换成的二叉树其右子树一定为空树转换成的二叉树其右子树一定为空数数 据据 结结 构构 测测 绘绘 学学 院院 将将二叉二叉树转换成树树转换成树加线：若加线：若p结点是双亲结点的左孩子，则

57、将结点是双亲结点的左孩子，则将p的右的右孩子，右孩子的右孩子，孩子，右孩子的右孩子，沿分支找到的所有右沿分支找到的所有右孩子，都与孩子，都与p的双亲用线连起来的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构调整：将结点按层次排列，形成树结构ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI数数 据据 结结 构构 测测 绘绘 学学 院院 森林转换成二叉树森林转换成二叉树 将各棵树分别转换成二叉树将各棵树分别转换成二叉树 将每棵树的根结点用线相连将每棵树的根结点用线相连 以

58、第一棵树根结点为二叉树的根，再以根结点为轴以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构心，顺时针旋转，构成二叉树型结构ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ数数 据据 结结 构构 测测 绘绘 学学 院院 二叉树转换成森林二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线，及沿右分支抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树二叉树还原：将孤立的二叉树还原成树还原：将孤立的二叉树还原成树ABCDEFGHIJABCDE

59、FGHIJABCDEFGHIJABCDEFGHIJ数数 据据 结结 构构 测测 绘绘 学学 院院树和森林的遍历树和森林的遍历 树的遍历树的遍历 遍历遍历按一定规律走遍树的各个顶点，且使按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排律的走法，以得到树中所有结点的一个线性排列列 常用方法常用方法先根（序）遍历：先访问树的根结点，然后先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树依次先根遍历根的每棵子树后根（序）遍历：先依次后根遍历每棵子树后根（序）遍历：先依次后根遍历每棵子树，

60、然后访问根结点，然后访问根结点按层次遍历：先访问第一层上的结点，然后按层次遍历：先访问第一层上的结点，然后依次遍历第二层，依次遍历第二层，第第n层的结点层的结点数数 据据 结结 构构 测测 绘绘 学学 院院ABCDEFGHIJKLMNO先序遍历：先序遍历：后序遍历：后序遍历：层次遍历：层次遍历：ABEF I GCDHJ KLNOMEIFGB CJKN OLMHD AAB CDE FGH I J KL MNO数数 据据 结结 构构 测测 绘绘 学学 院院讨论：若采用讨论：若采用“先转换，后遍历先转换，后遍历”方式，结果是否一样？方式，结果是否一样？abdec先序遍历：先序遍历：后序遍历：后序遍历：中序遍历：中序遍历：d e c b aabdeca b c d eb d c e a1