树的定义和基本术语课件.ppt

1、6.1 6.1 树的定义和基本术语树的定义和基本术语6.2 6.2 二叉树二叉树6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 6.4 树和森林树和森林6.5 6.5 HuffmanHuffman树及其应用树及其应用第六章第六章 树与二叉树树与二叉树内蒙古大学内蒙古大学理工学院理工学院计算机学院计算机学院生命科学学院生命科学学院外国语学院外国语学院人文学院人文学院数数学学系系物物理理系系电电子子系系计计算算机机系系计计算算中中心心网网络络中中心心汉汉语语系系历历史史系系哲哲学学系系生生物物系系环环境境系系动动物物中中心心生生物物工工程程中中心心资资源源所所英英语语系系日日语

2、语系系 行政机构行政机构树形结构是一种非线性结构，应用十分广泛。树形结构是一种非线性结构，应用十分广泛。如：行政机构、家谱、磁盘目录等如：行政机构、家谱、磁盘目录等磁盘目录磁盘目录根根Root分枝分枝Branch叶叶Leaf根根-根结点根结点分枝分枝-分枝结点分枝结点叶叶-叶结点叶结点的定义和基本术语的定义和基本术语v树的定义树的定义：树是：树是n（n=0）结点的有限集，结点的有限集，在任意非空树中：在任意非空树中：(1)有且仅有一个特定的结点称为根（有且仅有一个特定的结点称为根（Root）的结点的结点.(2)当当n1时，其余的结点可分为时，其余的结点可分为m个互不相交的子个互不相交的子 集集

3、 T1,T2,Tm,每个子集又都是树，称为根每个子集又都是树，称为根 的的子树（子树（Sub tree）.的定义和基本术语的定义和基本术语树的定义具有递归性树的定义具有递归性Tree=D=Book,C1,C2,C3,S1.1,S1.2,S2.1,S2.2,S2.3,S2.1.1,S2.1.2 R=,Book C1 C2 C3 S1.1 S1.2 S2.1 S2.2 S2.3 S2.1.1 S2.1.2 ChapterSectionSection例例6.1的定义和基本术语的定义和基本术语v术语主要来源于家谱和树：术语主要来源于家谱和树：双亲、父母（双亲、父母（Parent）；子女、孩子（）；子女

4、、孩子（Child）：）：若若a,b R，则称则称a是是b的双亲，的双亲，b是是a 的子女的子女(孩子孩子).叶结点（叶结点（Leaf）：度为度为0的结点；的结点；分枝结点（分枝结点（Branch node）：度大于度大于0的结点；的结点；结点度（结点度（Degree）：该结点所拥有的子女数；该结点所拥有的子女数；树的度树的度：树内各结点度的最大值；：树内各结点度的最大值；结点的层次（结点的层次（Level）：设根结点的层次为设根结点的层次为1，其它任一结点，其它任一结点 所在的层次是其双亲的层次加所在的层次是其双亲的层次加1；的定义和基本术语的定义和基本术语v树是一种层次结构树是一种层次结构

5、（hiberarchy）12345的定义和基本术语的定义和基本术语堂兄弟（堂兄弟（Cousin）：双亲在同一层的结点之间互称堂兄弟；双亲在同一层的结点之间互称堂兄弟；路径（路径（Path）：如果有结点序列如果有结点序列n1,n2,n3,nk，并且前并且前1个结个结 点是后点是后1个结点的双亲；它的长度是个结点的双亲；它的长度是k-1;祖先、后代（祖先、后代（ancestor）:一个结点是它所有子树中的结点一个结点是它所有子树中的结点 的祖先，这些结点是它的后代的祖先，这些结点是它的后代(子孙子孙);有序树（有序树（Ordered tree）：每个结点的子女由左到右是有次每个结点的子女由左到右是

6、有次 序的称有序树；否则是无序树；序的称有序树；否则是无序树；的定义和基本术语的定义和基本术语ABCACB无序有序深度（深度（Depth）：树中结点的最大层次；或称为高；树中结点的最大层次；或称为高；兄弟（兄弟（Sibling)：具有同一双亲的结点互称兄弟；具有同一双亲的结点互称兄弟；ABCDEFGHIJKLM结点结点A的度：的度：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为兄弟为兄

7、弟树的度：树的度：3结点结点A的层次：的层次：1结点结点M的层次：的层次：4树的深度：树的深度：4结点结点F，G为堂兄弟为堂兄弟结点结点A是结点是结点F，G的祖先的祖先T1T2T3T4T5T6的定义和基本术语的定义和基本术语v森林（森林（Forest）：是是m(m 0)棵互不相交的树的集合棵互不相交的树的集合(例如删除例如删除树根树根后的后的子树构成一个森林子树构成一个森林)ArootBCDEFGHIJMKLF任何一棵非空树是一个二元组任何一棵非空树是一个二元组 Tree=（root，F）其中：其中：root 被称为根结点，被称为根结点，F 被称为子树森林被称为子树森林v抽象数据类型树的定义：

8、抽象数据类型树的定义：的定义和基本术语的定义和基本术语ADT Tree数据对象数据对象D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系数据关系R：若若D为空集，则称为为空集，则称为空树空树；若若D仅含一个数据元素，则仅含一个数据元素，则R为空集，否则为空集，否则R=H，H是如下是如下二元关系：二元关系：(1)在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root，它在关系它在关系H下下 无前驱；无前驱；(2)若若D-root ，则存在则存在D-root的一个划分的一个划分D1，D2，Dm，(m0)，对任意对任意jk(1j,km)有有DjDk=,且对

9、任意的且对任意的i(1im)，唯一存在数据元素唯一存在数据元素xiDi，有有H；(3)(3)对应于对应于D-rootD-root的划分，的划分，H Hroot，root 有唯一的一个划分有唯一的一个划分H H1 1,H,H2 2，H Hm m(m0)(m0)，对任意对任意jk(1jjk(1j，km)km)有有H Hj jHHk k=,=,且对任意且对任意i(1im),Hi(1im),Hi i是是D Di i上的二元上的二元 关系关系,(,(D Di i,H,Hi i)是一棵符合本定义的树是一棵符合本定义的树,称为根称为根root的子树的子树.基本操作基本操作:InitTree(&T)InitT

10、ree(&T)操作结果：构造空树操作结果：构造空树T T。DestroyTree(&T)DestroyTree(&T)初始条件：树初始条件：树T T存在。存在。操作结果，销毁树操作结果，销毁树T T。CreateTree(&TCreateTree(&T，definition)definition)初始条件：初始条件：definitiondefinition给出树给出树T T的定义。的定义。操作结果：按操作结果：按definitiondefinition构造树构造树T T。ClearTree(&T)ClearTree(&T)初始条件；树初始条件；树T T存在。存在。操作结果：将树操作结果：将树T

11、 T清为空树。清为空树。TreeEmpty(T)TreeEmpty(T)初始条件：树初始条件：树T T存在。存在。操作结果：若操作结果：若T T为空树，则返回为空树，则返回TRUETRUE，否则否则FALSEFALSE。TreeDepth(T)TreeDepth(T)初始条件：树初始条件：树T T存在。存在。操作结果；返回操作结果；返回T T的深度。的深度。基本操作基本操作:Root(T)Root(T)初始条件：树初始条件：树T T存在。存在。操作结果：返回操作结果：返回T T的根。的根。Value(TValue(T，cur_e)cur_e)初始条件：树初始条件：树T T存在，存在，cur_e

12、cur_e是是T T中某个结点。中某个结点。操作结果：返回操作结果：返回cur_ecur_e的值。的值。Assign(TAssign(T，cur_ecur_e，value)value)初始条件：树初始条件：树T T存在，存在，cur_ecur_e是是T T中某个结点。中某个结点。操作结果：结点操作结果：结点cur_e cur_e 赋值为赋值为valuevalue。Parent(TParent(T，cur_e)cur_e)；初始条件：树初始条件：树T T存在，存在，cur_ecur_e是是T T中某个结点。中某个结点。操作结果：若操作结果：若cur_ecur_e是是T T的非根结点，则返回它的双

13、亲，的非根结点，则返回它的双亲，否则返回否则返回“空空”。基本操作基本操作:LeftChild(TLeftChild(T，cur_e)cur_e)；初始条件：树初始条件：树T T存在，存在，cur_ecur_e是是T T中某个结点。中某个结点。操作结果：若操作结果：若cur_ecur_e是是T T的非叶子结点，则返回它的的非叶子结点，则返回它的 最左孩子，否则返回最左孩子，否则返回“空空”。RightSibling(TRightSibling(T，cur_e)cur_e)；初始条件：树初始条件：树T T存在，存在，cur_ecur_e是是T T中某个结点。中某个结点。操作结果：若操作结果：若c

14、ur_e有右兄弟，则返回它的右兄弟，有右兄弟，则返回它的右兄弟，否则否则返回返回“空空”。基本操作基本操作:InsertChild(&TInsertChild(&T，&P&P，i i，c)c)；初始条件：树初始条件：树T T存在存在,p p指向指向T T中某个结点，中某个结点，i i指结点的度指结点的度,非空树非空树c c与与T T不相交。不相交。操作结果：插入操作结果：插入c c为为T T中中p p所指结点的第所指结点的第i i棵子树。棵子树。DeleteChild(&TDeleteChild(&T，&p&p，i)i)；初始条件：树初始条件：树T T存在，存在，p p指向指向T T中某个结点

15、，中某个结点，i i指结点的度指结点的度,操作结果：删除操作结果：删除T T中中p p所指结点的第所指结点的第i i棵子树。棵子树。TraverseTree(T)TraverseTree(T)；初始条件；树初始条件；树T T存在。存在。操作结果：按某种次序对操作结果：按某种次序对T T的每个结点进行遍历的每个结点进行遍历。ADT Tree 基本操作基本操作:v树的表示方法：树的表示方法：1.树形表示：树形表示：的定义和基本术语的定义和基本术语ABCDEFHIJG2.括号表示括号表示(广义表表示广义表表示)：(A(B(E)(C(F)(D(G(H)(I)(J)T1T3T2树根3.凹入表表示凹入表表

16、示(目录表示法目录表示法)：ABCDEFHIJGABECFDGHIJ的定义和基本术语的定义和基本术语4.文氏图表示文氏图表示(集合表示集合表示):ABCDEFHIJGABECFDGH IJ的定义和基本术语的定义和基本术语二叉树是另一种树形结构。二叉树是另一种树形结构。6.2.1 二叉树的定义二叉树的定义二叉树：二叉树：是是n（n=0）结点的有限集，在任意非空树中：结点的有限集，在任意非空树中：(1)有且仅有一个特定的称为根（有且仅有一个特定的称为根（Root）的结点的结点;(2)当当n1时，其余的结点最多分为时，其余的结点最多分为2个互不相交的子集个互不相交的子集 T1,T2,每个又都是二叉树

17、，分别称为根的每个又都是二叉树，分别称为根的左子树左子树和和右子树右子树.例例6.2.1 二叉树的定义二叉树的定义ABCDEFGHK根结点左子树左子树右子树右子树二叉树二叉树注意：注意：二叉树不是树，它是另外单独定义的一种二叉树不是树，它是另外单独定义的一种树形结构，并非一般树的特例。它的子树有顺序树形结构，并非一般树的特例。它的子树有顺序规定，分为左子树和右子树。不能随意颠倒。规定，分为左子树和右子树。不能随意颠倒。二叉树的二叉树的5种基本形态：种基本形态：1 空空2 只有根只有根3 右子树空右子树空4 左子树空左子树空5 左、右子树非空左、右子树非空抽象数据类型二叉树的定义：抽象数据类型二

18、叉树的定义：ADT BinaryTreeADT BinaryTree数据对象数据对象D D：D D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系数据关系R R：若若D=D=，则则R=R=，称称BinaryBinary为空二叉树；为空二叉树；若若D D ，则则R=HR=H，H H是如下二元关系：是如下二元关系：(1)(1)在在D D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素rootroot，它在关系它在关系H H下无前驱；下无前驱；(2)(2)若若D-root D-root ，则存在则存在D-rootD-root的一个划分的一个划分 D Dl l，D Dr

19、 r，且且D Dl lDDr r=；(3)(3)若若D Dl l ,则则D Dl l中存在唯一的元素中存在唯一的元素x x1 1,root,x,H,H,且存在且存在D Dl l上的关系上的关系H Hl l H H,若若D Dr r ,则则D Dr r中存在唯一的元素中存在唯一的元素x xr r,root,x,H,H,且存在且存在D Dr r上的关系上的关系H Hr r H H;H=root,x;H=,H,Hl l,H,Hr r (4)(4)(D Dl l,H,Hl l)是一颗符合本定义的二叉树，称为根的左子树是一颗符合本定义的二叉树，称为根的左子树 (D Dr r,H,Hr r)是一颗符合本定

20、义的二叉树，称为根的右子树是一颗符合本定义的二叉树，称为根的右子树6.2.1 二叉树的定义二叉树的定义基本操作基本操作:InitBiTree(&T);操作结果：构造空二叉树操作结果：构造空二叉树T。DestroyBiTree(&T);初始条件：二叉树初始条件：二叉树T存在。存在。操作结果：销毁二叉树操作结果：销毁二叉树T。CreatBiTree(&T,definition);初始条件：初始条件：definition给出二叉树给出二叉树T的定义。的定义。操作结果：按操作结果：按definition构造二叉树构造二叉树T。ClearBiTree(&T)；初始条件：二叉树初始条件：二叉树T存在。存在

21、。操作结果：将二叉树操作结果：将二叉树T清为空树。清为空树。BiTreeEmpty(T)；初始条件：二叉树初始条件：二叉树T T存在。存在。操作结果：若操作结果：若T T为空二叉树为空二叉树,则返回则返回TRUE,TRUE,否则否则FALSE.FALSE.BiTreeDepth(T)；初始条件：二叉树初始条件：二叉树T T存在。存在。操作结果：返回操作结果：返回T T的深度。的深度。Root(T)；初始条件初始条件:二叉树二叉树T T存在。存在。操作结果：返回操作结果：返回T T的根。的根。Value(T，e)初始条件：二叉树初始条件：二叉树T T存在，存在，e e是是T T中某个结点。中某个

22、结点。操作结果；返回操作结果；返回e的值。的值。基本操作基本操作:Assign(T，&e，value)；初始条件；二叉树初始条件；二叉树T T存在，存在，e e是是T T中某个结点。中某个结点。操作结果：结点操作结果：结点e e赋值为赋值为valuevalue。Parent(T，e)；初始条件：二叉树初始条件：二叉树T T存在，存在，e e是是T T中某个结点。中某个结点。操作结果：若操作结果：若e e是是T T的非根结点，则返回它的双亲，否则返回的非根结点，则返回它的双亲，否则返回“空空”。LeftChild(T，e)；初始条件：二叉树初始条件：二叉树T T存在，存在，e e是是T T中某个

23、结点。中某个结点。操作结果：返回操作结果：返回e e的左孩子，若的左孩子，若e e无左孩子，则返回无左孩子，则返回“空空”。RightChild(T，e)；初始条件：二叉树初始条件：二叉树T T存在，存在，e e是是T T中某个结点。中某个结点。操作结果：返回操作结果：返回e e的右孩子的右孩子,若若e e无右孩子，则返回无右孩子，则返回“空空”。基本操作基本操作:LeftSibling(T，e)；初始条件：二叉树初始条件：二叉树T T存在，存在，e e是是T T中某个结点。中某个结点。操作结果：返回操作结果：返回e的左兄弟。若的左兄弟。若e是是T的左孩子或无左兄弟，则的左孩子或无左兄弟，则

24、返回返回“空空”。Rightsibling(T，e)；初始条件：二叉树初始条件：二叉树T T存在，存在，e e是是T T中某个结点。中某个结点。操作结果：返回操作结果：返回e e的右兄弟。若的右兄弟。若e e是是T T的右孩子或无右兄弟，的右孩子或无右兄弟，则返回则返回“空空”。基本操作基本操作:InsertChild(T，p，LR，c)；初始条件：二叉树初始条件：二叉树T T存在，存在，p p指向指向T T中某个结点，中某个结点，LRLR为为0 0或或1 1，非空二叉树非空二叉树c c与与T T不相交且右子树为空。不相交且右子树为空。操作结果：根据操作结果：根据LRLR为为0 0或或1 1，

25、插入，插入c c为为T T中中p p所指结点的左或所指结点的左或 右子树。右子树。P P所指结点的原有左或右子树则成为所指结点的原有左或右子树则成为c c 的右子树。的右子树。基本操作基本操作:DeleteChild(T，p，LR)；初始条件：二叉树初始条件：二叉树T T存在，存在，p p指向指向T T中某个结点，中某个结点，LRLR为为0 0或或1 1。操作结果：根据操作结果：根据LR为为0或或1，删除，删除T中中p所指结点的左或右子树。所指结点的左或右子树。PreOrderTraverse(T)；初始条件：二叉树初始条件：二叉树T T存在。存在。操作结果：先序遍历操作结果：先序遍历T T中

26、对每个结点一次且仅一次。中对每个结点一次且仅一次。基本操作基本操作:InOrderTraverse(T)；初始条件：二叉树初始条件：二叉树T T存在。存在。操作结果：中序遍历操作结果：中序遍历T T中每个结点一次且仅一次。中每个结点一次且仅一次。PostOrderTraverse(T)；初始条件：二叉树初始条件：二叉树T T存在。存在。操作结果：后序遍历操作结果：后序遍历T T中每个结点一次且仅一次。中每个结点一次且仅一次。基本操作基本操作:LevelOrderTraverse(T)；初始条件：二叉树初始条件：二叉树T T存在。存在。操作结果：层序遍历操作结果：层序遍历T T中每个结点一次且仅

27、一次中每个结点一次且仅一次.ADT BinaryTreeADT BinaryTree性质性质1:在二叉树的第在二叉树的第i层最多有层最多有2i-1 个结点个结点(i=1).用归纳法证明用归纳法证明：归纳基归纳基：归纳假设：归纳假设：归纳证明：归纳证明：i=1 层时，只有一个根结点，层时，只有一个根结点，2i-1=20=1；i=k时命题成立时命题成立;i=k+1时时,二叉树上每个结点至多有两棵子树，二叉树上每个结点至多有两棵子树，则第则第 i 层的结点数层的结点数=2k-1 2=2(k+1)-1=2i-1。6.2.2 二叉树的性质二叉树的性质性质性质2:深度为深度为k的二叉树最多有的二叉树最多有

28、2k 1个结点（个结点（k=1).证明：证明：基于性质基于性质1，深度为，深度为 k 的二叉树上的的二叉树上的结点数最多为结点数最多为 20+21+2k-1=2k-1 6.2.2 二叉树的性质二叉树的性质性质性质3:任一二叉树任一二叉树,若叶结点数是若叶结点数是n0,度为度为2的结点数的结点数 是是 n2,则则 n0=n2 +1证明：证明：设设 二叉树上结点总数二叉树上结点总数 n=n0+n1+n2又又 二叉树上分支总数二叉树上分支总数 b=n1+2n2 而而 b=n-1=n0+n1+n2-1由此，由此，n0=n2+16.2.2 二叉树的性质二叉树的性质满二叉树满二叉树(Full Binary

29、 Tree):每一层的结点数都达到了最每一层的结点数都达到了最 大的二叉树大的二叉树.编号的满二叉树编号的满二叉树:从根开始从根开始,由上到下由上到下,从左到右地对每个结点从左到右地对每个结点 进行编号进行编号.也就是说也就是说:根的编号是根的编号是1,一个结点一个结点,若它是双亲若它是双亲 的左子女的左子女,则它的编号是它的双亲编号的则它的编号是它的双亲编号的2倍倍;若它是双亲若它是双亲 的右子女的右子女,则它的编号是双亲编号的则它的编号是双亲编号的2倍倍+1.6.2.2 二叉树的性质二叉树的性质ABCDEFH1234567编号的满二叉树编号的满二叉树完全二叉树完全二叉树(Complete

30、Binary Tree):深度为深度为k的满二叉树的满二叉树,删去第删去第k层上最右边的层上最右边的j(0 j2k-1)个结点个结点,就得到一个深度为就得到一个深度为k的完全二叉树的完全二叉树.编号的完全二叉树编号的完全二叉树:与满二叉树编号相同与满二叉树编号相同6.2.2 6.2.2 二叉树的性质二叉树的性质1ABCE234ABCDE12345ABCEFH123456F7性质性质4:具有具有n个结点的完全二叉树个结点的完全二叉树,其深度为其深度为 。1log2n证明：证明：6.2.2 6.2.2 二叉树的性质二叉树的性质设设 完全二叉树的深度为 k 则根据性质2得 2k-1-1 n 2k-1

31、 或或者者 2k-1 n 2k 即 k-1 log2 n 1，则它的双亲是则它的双亲是（2）若）若2i n，则结点则结点i的左子女是的左子女是2i;否则无左子女；否则无左子女；（3）若）若2i+1 n，则结点则结点i的右子女是的右子女是2i;否则无右子女；否则无右子女；2i123465ii+12i2i+12i6.2.2 6.2.2 二叉树的性质二叉树的性质2i+2一一、二叉树的顺序存储、二叉树的顺序存储完全二叉树的顺序存储：完全二叉树的顺序存储：ABCEFH123456 A B C E H F 0 1 2 3 4 5 6ST 根据性质根据性质5知：知：STi 的双亲是的双亲是ST,左子女是左子

32、女是ST2*i，右子女是右子女是ST2*i+12/i一、二叉树的顺序存储一、二叉树的顺序存储 A B C E F H 0 1 2 3 4 5 6 7 8 9ST 根据性质根据性质5知：知：STi 的双亲是的双亲是ST ,左子女是左子女是ST2*i,右子女是右子女是ST2*i+1.ABCEFH1234792/i这样太浪费空间这样太浪费空间,适合完全二叉树适合完全二叉树二、二、二叉树的链式存储结构二叉树的链式存储结构(二叉链表二叉链表)typedef struct BiTNode ElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTre

33、e;ABCEFHGABCEHFG二叉链表二叉链表BTlchild data rchildLeft childRight childBiTNode:二二、二叉树的链式存储结构、二叉树的链式存储结构(三叉链表三叉链表)lchild data rchild parentLeft childRight childParenttypedef struct BiTNodeElemType data;struct BiTNode *lchild,*rchild,*parent;BiTNode,*BiTree;BiTNode:ABCEFHG二二、二叉树的链式存储结构、二叉树的链式存储结构(三叉链表三叉链表)A

34、 BCEHFG三叉链表三叉链表BT线索二叉树线索二叉树 按照某种搜索路径按照某种搜索路径访问访问二叉树中的所有结点，二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。使得每个结点被访问一次且仅被访问一次。一、遍历一、遍历“访问访问”的含义特别很广，如：输出结点的信息等。的含义特别很广，如：输出结点的信息等。因二叉树是非线性结构，因二叉树是非线性结构，每个结点可能有两个后每个结点可能有两个后继，则存在如何遍历即按什么样的搜索路径遍历的继，则存在如何遍历即按什么样的搜索路径遍历的问题。问题。前前(先先)序序 遍历遍历中序遍历中序遍历后序遍历后序遍历NLR123二、遍历方法二、遍历方法NLR

35、LNRLRNNRLRNLRLN线索二叉树线索二叉树算法思想算法思想6.1前序遍历：前序遍历：若若BT非空，则：非空，则：1.访问根结点；访问根结点；2.前序遍历左子树；前序遍历左子树；3.前序遍历右子树前序遍历右子树;算法思想算法思想6.2中序遍历：中序遍历：若若BT非空，则：非空，则：1.中序遍历左子树；中序遍历左子树；2.访问根结点；访问根结点；3.中序遍历右子树；中序遍历右子树；算法思想算法思想6.3后序遍历：后序遍历：若若BT非空，则：非空，则：1.后序遍历左子树；后序遍历左子树；2.后序遍历右子树；后序遍历右子树；3.访问结点；访问结点；线索二叉树线索二叉树ABCEFHG例例6ABC

36、EFHG前序遍历前序遍历(NLR)序列：序列：A B E H G C F中序遍历中序遍历(LNR)序列：序列：ABCEFHGE B G H A F C后序遍历后序遍历(LRN)序列：序列：ABCEFHGE G H B F C A算法思想算法思想6.1前序遍历：前序遍历：若若BT非空，则：非空，则：1.访问根结点；访问根结点；2.前序遍历左子树；前序遍历左子树；3.前序遍历右子树前序遍历右子树;线索二叉树线索二叉树算法算法 6.1 6.1Void PreOrderTraverse(BiTree BT)Void PreOrderTraverse(BiTree BT)if(BT)if(BT)visi

37、t(BT);visit(BT);PreOrderTraverse(BT-lchild);PreOrderTraverse(BT-lchild);PreOrderTraverse(BT-rchild);PreOrderTraverse(BT-rchild);/end of PreOrderTraverse/end of PreOrderTraverse请同学们自己写出请同学们自己写出InOrderTraverse(BT)InOrderTraverse(BT)和和PostOrderTraverse(BT)PostOrderTraverse(BT)建立二叉树建立二叉树建立二叉树的方法很多，我们给出建

38、立二叉树的方法很多，我们给出以前序遍历序列以前序遍历序列建建立二叉树的方法，但该序列是立二叉树的方法，但该序列是扩充二叉树扩充二叉树的前序遍历的前序遍历序列。序列。是扩充的叶结点，它代表空指针。是扩充的叶结点，它代表空指针。DBFEAC该扩充二叉树的前序遍历序列是：该扩充二叉树的前序遍历序列是：ABD*EF*C*该算法是一递归算法，递归三要素：该算法是一递归算法，递归三要素：1.递归出口：当遇到递归出口：当遇到*时，是空。时，是空。2.建立根。建立根。3.建立左子树和右子树。建立左子树和右子树。建立二叉树的算法建立二叉树的算法Status CreateBiTree(BiTree&BT)/按先序

39、次序输入二叉树中结点的值按先序次序输入二叉树中结点的值(一个字符一个字符)，空格字符表示空树，空格字符表示空树，构造二叉链表表示的二叉树构造二叉链表表示的二叉树T.scanf(&ch)；if(ch=)BT=NULL；else if(!(BT=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW)；BT-data=ch;生成根结点生成根结点 CreateBiTree(BT-lchild);构造左子树构造左子树 CreateBiTree(BT-rchild);构造右于树构造右于树return OK；CreateBiTreeA BCDABTBCD我们先观察一下三

40、种遍历行走的路线我们先观察一下三种遍历行走的路线ABCEFHGDI*前序遍历前序遍历NLR#ABCEFHGDI中序遍历中序遍历LNR&ABCEFHGDI后序遍历后序遍历LRN&ABCEFHGDI*#三种遍历的访问位置对比：三种遍历的访问位置对比：三种遍历的路线完全一样，三种遍历的路线完全一样，只是访问时间不同；只是访问时间不同；前序：第一次前序：第一次经过经过*时访问时访问中序：第二次中序：第二次经过经过#时访问时访问后序：第三次后序：第三次经过经过&时访问时访问遍历线路的核心规则是：先左后右；遍历线路的核心规则是：先左后右；我们用一个栈我们用一个栈stack记录走过的位置，以便返回；记录走过

41、的位置，以便返回；stack 中数据元素的类型：中数据元素的类型：*BiTNode(或或BiTree)函数：函数：BiTree P;push(S,p);pop(S,p);Boolean StackEmpty(S);下面给出基于逻辑下面给出基于逻辑结构的算法描述结构的算法描述非递归中序遍历二叉树的算法思想非递归中序遍历二叉树的算法思想 建立栈建立栈 stack；1.P指向根；指向根；2.当当p不空不空 且且 stack 不空时反复做：不空时反复做：若若 p不空不空,p 入入 栈栈;p指向左子女；指向左子女；否则否则：出栈顶元素到出栈顶元素到p中；中；访问访问p；p指向右子女；指向右子女；4.结束

42、结束如何进行前如何进行前序遍历？序遍历？Void lnorderTraverse(BiTree BT)采用二叉链表存储结构，中序遍历二叉树采用二叉链表存储结构，中序遍历二叉树T的非递归算法的非递归算法.InitStack(S)；p=BT；while(p|!StackEmpty(S)if(p)push(S，p)；p=p-lchild；/根指针进栈，遍历左子树根指针进栈，遍历左子树 else 根指针退栈，访问根结点，遍历右子树根指针退栈，访问根结点，遍历右子树 pop(S，p)；visit(p);p=p-rchild；/elseInOrderTraverse非递归中序遍历BT的算法:ABCDEFG

43、pi&A(1)例例ABCDEFGpi&A&B(2)例例ABCDEFGpi&A&B&C(3)例例p=NULLABCDEFGi&A&B访问：访问：C(4)例例pABCDEFGi&A访问：访问：C B(5)例例ABCDEFGi&A&D访问：访问：C Bp(6)例例ABCDEFGi&A&D&E访问：访问：C Bp(7)例例ABCDEFGi&A&D访问：访问：C B Ep(8)例例ABCDEFGi&A&D&G访问：访问：C B EP=NULL(9)例例ABCDEFGi&A&D访问：访问：C B E Gp(10)例例ABCDEFGi&A访问：访问：C B E G Dp(11)例例ABCDEFGi&A&F访

44、问：访问：C B E G Dp(12)例例ABCDEFGi&A访问：访问：C B E G D Fp=NULL(13)例例ABCDEFGi访问：访问：C B E G D F Ap(14)例例ABCDEFGi访问：访问：C B E G D F Ap=NULL(15)例例非递归后序遍历二叉树的算法思想非递归后序遍历二叉树的算法思想建立栈建立栈 stack；1.P指向根；指向根；2.当当p不空不空 且且 stack 不空时反复做：不空时反复做：若若 p不空不空：(p,L)入入 栈栈;p指向左子女；指向左子女；否则否则：出栈顶元到出栈顶元到p和和tag中；中；若若tag=R,则访问则访问p；p置空；置空

45、；否则否则（p,R）入栈；入栈；并让并让 p指向右子女；指向右子女；4.结束结束后序遍历时，访问一后序遍历时，访问一个结点的时间是：个结点的时间是：第第3次经过时或次经过时或第第2次反回时或次反回时或从右边返回时；从右边返回时；如何区分从如何区分从左左还是还是右右返回的呢？返回的呢？P入栈时带一标记入栈时带一标记:向左走时带向左走时带L向左走时带向左走时带R非递归后序遍历BT的算法非递归的后序遍历非递归的后序遍历BTBT算法算法:（基于二叉链表存储结构）基于二叉链表存储结构）void PostOrderTraverse(BiTree BT)InitStack(S)；/建立栈建立栈 p=BT;/

46、指向根指向根while(p|!StackEmpty(S)if(p)push(p,L)；/p带带L入入 栈栈p=p-lchild;/p指向左子女指向左子女else pop(p,e);/出栈顶元到出栈顶元到e中中p=e.p;tag=e.tag;if(tag=R)visite(p-data);p=NULL;/访问访问pelse push(p,R);p=p-rchild;/p指向右子女指向右子女/else /end of while /end of postOrderTraverse(bt)例例BEACStart(A,L)入栈入栈 (A,L)(B,L)入栈入栈 (A,L)(B.L)(B.L)退栈，退栈

47、，(A,L)(B,R)入栈入栈 (A,L)(B,R)(E,L)入栈入栈 (A,L)(B,R)(E,L)(E,L)退栈退栈 (A,L)(B,R)(E,R)入栈入栈 (A,L)(B,R)(E,P)(E,R)退栈退栈 (A,L)(B,R)访问访问E(B,R)退栈退栈 (A,L)访问访问B(A,L)退栈退栈(A,R)入栈入栈 (A,R)(C,L)入栈入栈 (A,R)(C,L)(C,L)退栈退栈 (A,R)(C,R)入栈入栈 (A,R)(C,R)(C,R)退栈退栈 (A,R)访问访问C(A,R)退栈退栈 访问访问A123456789101112131415161234567891011121314151

48、6课堂练习课堂练习前序遍历序列：前序遍历序列：EDACBGFEEDACBGFE中序遍历序列：中序遍历序列：ADCBEFHGADCBEFHG试画出满足以上序列的二叉树试画出满足以上序列的二叉树课堂练习课堂练习中序遍历序列：中序遍历序列：ADCBHFEGADCBHFEG后序遍历序列：后序遍历序列：ABCDEFGHABCDEFGH试画出满足以上序列的二叉树试画出满足以上序列的二叉树二、线索二叉树二、线索二叉树(Threaded Binary Tree)目的目的：利用二叉树的空指针保存遍历序列的前驱和后继。：利用二叉树的空指针保存遍历序列的前驱和后继。n个结点的二叉树个结点的二叉树,有有2n个指针个指

49、针,只用了只用了n-1个个,有有n+1个是空指。个是空指。用空的用空的左指针左指针指向某一遍历序列的指向某一遍历序列的前驱前驱.用空的用空的右指针右指针指向某一遍历序列的指向某一遍历序列的后继后继.这这两种指针两种指针称为称为线索线索(Thread)。为了区分线索与真实指针，给结点增加两个域为了区分线索与真实指针，给结点增加两个域Ltag和和Rtaglchild Ltag data Rtag rchildLtag=0:lchild 指向结点的左子女；指向结点的左子女；Ltag=1:lchild 指向指向某一遍历序列某一遍历序列前驱；前驱；Rtag=0:rchild 指向结点的右子女；指向结点的

50、右子女；Rtag=1:rchild 指向指向某一遍历序列某一遍历序列后继后继；二、线索二叉树二、线索二叉树(Threaded Binary Tree)Typedef enumLink,Thread PointerTag;Typedef struct BiThrNode ElemType data;struct BiThrNode *lchild,*rchild;PointerTag Ltag,Rtag;BiThrNode,*BiThrTree;lchild Ltag data Rtag rchild二、线索二叉树二、线索二叉树(Threaded Binary Tree)加了线索的二叉树是加了线