61树和二叉树

1、第六章 树和二叉树 主要内容 n树和二叉树定义 n二叉树性质，存贮结构，遍历算法 n遍历二叉树和线索二叉树 n二叉树和树，树和森林关系 nHuffman树与Huffman编码 树例与特征 n1.社会的组织结构 n2.家族的族谱 n3.C语言中的结构的描述 n4.计算机中的目录组织 n描述层次结构，是一种一 对多的逻辑关系 树定义 n树(Tree)是n(n=0)个 结点的有限集。n=0时 称为空树。 n有且仅有一个称为根的 结点（Root）； nn1时，其余结点可分为 m(m0)个互不相交的有 限集T1Tm,其中每个 集合又是一棵树，称为 子树(SubTree) A B CD E H FG I

2、1 2 3 4 树定义 A CB GFEHIJ D MKL A T1T2T3 n结点：一个数据元素及若干指向其子树 的分支； n结点的度：结点拥有的子树的数目。 Degree； n叶子（终端结点）：度为0的结点；Leaf n分支结点（非终端结点）：度不为0的结 点；除根结点外，也称内部结点； n树的度：树内各结点的度的最大值； 概念_1 概念_2 n孩子，双亲，兄弟：结点的子树称为该结点的 孩子；该结点称为孩子的双亲；同一个双亲的 孩子之间互称兄弟（Sibling）,Child, Parent n祖先：从根结点到该结点所经分支上的所有结 点。 n子孙：以某结点为根的子树中的任一结点都称 为该结

3、点的子孙。 n层次：结点在树结构中的层 n堂兄弟：双亲在同一层的结点互为堂兄弟； 概念_3 n深度：树中结点的最大层次称为树的深 度；Depth n有序树：结点的子树在树中的位置固定， 不能互换，称有序树 n无序树：可以互换 n森林：m(m0)棵互不相交的树的集合。 n对于树中的一个结点，其子树即为森林。 概念示例 n结点 n结点的度(Degree) n叶子（Leaf)或终端结点 n分支结点或非终端结点 n树的度 n层次(Level) n树的深度(Depth) n孩子（child) n双亲（Parent) n兄弟(Sibling) n堂兄第 A CB GFEHIJ D MKL n祖先 n子孙

4、树的其它表示方式 A CB GFEHIJ D MKL A J I M H D G C F L K E B 凹入表示 A B F E K L G C D H M I J 嵌套集合 (A(B(E(K,L),F),C(G),D(H(M),I,J) 广义表 树和二叉树的关系 n任何一棵树是一个二元组Tree = ( root, F )，其中： root是数据元素，称为树的根结点；F是m( m= 0 )棵 树的森林，F = ( T1, T2, Tm )，其中Ti = ( ri, Fi ) 称为树根root的第 i 棵子树; 当m != 0时，在树根和其 子树森林之间存在下列关系： RF = | i =

5、1,2,m, m 0 ADT表示1 ADT Tree n数据对象D： nD是具有相同特性的数据元素的集合 n数据关系R： n若D为空集，则称为空树； n若D仅含一个数据元素，则R为空集，否则 R=H，H是如下二元关系： n 在D中存在唯一的称为根的数据元素root， 它在关系H下无前驱； ADT表示2 n 若D-root,则存在D-root的一个划分 D1,D2,Dm(m0)，对任意jk (1j,km) 又DjDk=,且对任意的i(1im)，唯一存 在数据元素xiDi，有H; n 对应于D-root的划分，H - , 有唯一的一个划分 H1,H2,Hm，m0，对任意jk(1j,km) 有HjH

6、k=，且对任意i（1im），Hi是 Di上的二元关系，（Di,Hi）是一棵符合本 定义的树，称为根root的子树。 ADT表示3 n基本操作： InitTree( / 初始化 DestroyTree( / 销毁 CreateTree( / 按条件definition构造树 ClearTree( / 清空 TreeEmpty( T );/ 空？ TreeDepth( T );/ 树的深度 Root( T );/ 树根 Value( T, cur_e );/ 求结点cur_e的值 Assign( T, cur_e, value );/ 赋值 ADT表示3 Parent( T, cur_e );/

7、求cur_e的双亲 LeftChild( T, cur_e );/ 求cur_e的最左孩子 RightSibling( T, cur_e );/ 求cur_e的右兄弟 / 插入c为T中p所指结点的第I棵子树 InsertChild( / 删除T中，p所指结点的第I个子树 DeleteChild( TraverseTree( T, visit() );/遍历 /ADT Tree 二叉树（Binary Tree） n最简单的树 n特征： n1.每个结点最多只有两棵子树 n2.子树有左右之分，其次序不能任意颠倒，是 一个有序树 二叉树的ADT表示 ADT BinaryTree 数据对象D：D是具有相

8、同特性的数据元素的集合； 数据关系R: 若D = ，则 R = ， 称BinaryTree为空二叉树； 若D ，则 R = H , H是如下的二元关系： (1) 在D中，存在唯一的称为根的数据元素 root, 它在关系H下无前驱； (2) 若D root , 则存在D-root = Dl, Dr, 且 Dl Dr = ； 二叉树的ADT表示 (3) 若Dl , 则Dl中存在唯一的元素xl, H, 且存在Dl上的关系 Hl H；若Dr , 则 Dr中存在唯一的元素xr, H, 且存 在Dr上的关系Hr H； H = , Hl, Hr; (4) ( Dl, Hl)是一棵符合本定义的二叉树，称为根

9、的左子树；( Dr, Hr)是一棵符合本定义的二叉 树，称为根的右子树； 基本操作： InitBiTree( / 初始化 DestroyBiTree( / 销毁 二叉树的ADT表示 CreateBiTree( / 创建二叉树 ClearBiTree( / 清空 BiTreeEmpty( T );/ 空？ BiTreeDepth( T );/ 深度 Root( T );/ 根 Value( T, e );/ 求e的值 Assign( T, / 赋值 Parent( T, e );/ 求双亲 LeftChild( T, e );/ 左孩子 RightChild( T, e );/ 右孩子 Left

10、Sibling( T, e) ;/ 左兄弟 二叉树的ADT表示 RightSibling( T, e );/ 右兄弟 InsertChild( T, p, LR, c );/ 插入 DeleteChild( T, p, LR );/ 删除 PreOrderTraverse( T, Visit( );/ 先序遍历 InOrderTraverse( T, Visit( );/ 中序遍历 PostOrderTraverse( T, Visit( );/ 后序遍历 LeverOrderTraverse( T, Visit( );/ 层序遍历 / ADT BinaryTree 二叉树的五种形态 n有且仅

11、有： 空/仅有根/仅有左子树/完整的是树/仅有右子树 (a)(a) (b)(b) (c)(c) (d)(d) (e)(e) 二叉树的性质 1.二叉树第i层上，最多有2i-1个结点（i=1） 证明：i = 1, 只有根结点，显然成立 设i = k时成立，最多有2k-1 当i= k+1时，最多的结点个数： 2k-1 * 2 = 2k-1+1 = 2k = 2( k+1)-1 2. 深度为k的二叉树，最多有2k-1个结点。 证明：二叉树的结点个数为： 1 + 2 + + 2k-1= 2k-1 二叉树的性质 3.对任何一棵二叉树T，如果其终端结点数为n0， 度为2的结点数为n2，则n0 = n2 +1

12、; 证明： 设n1为T中度为1的结点数，则总结点数： n = n0 + n1 + n2 另：除根结点外，所有结点都有且仅有一个双亲结点， 也就是仅有一个分支进入，若B为分支数，则 B = n1 + 2 * n2 = n - 1； n1 + 2 * n2 = n0 + n1 + n2 1; n0 = n2 + 1; 定义：满二叉树 n满二叉树：深度为k 且有2k-1个结点的二 叉树。 n考虑到有序性，任一 结点在树中都有确切 的位置，因此可以对 满二叉树进行编号。 编号方式为：从上到 下，从左到右。 1 89101112131415 45 2 67 3 满二叉树 完全二叉树 n完全二叉树：深度为

13、k，有n 个结点的二叉树，当且仅当 其每一个结点都与深度为k的 满二叉树编号从1到n的结点 一一对应时，成为完全二叉 树。 n特征： n1.叶子结点只可能在层次 最大的两层上出现 n2.任一结点，若其右分支 下的子孙的最大层次为l， 则其左分支下的最大层次 为l或l+1. 1 89101112 45 2 67 3 完全二叉树 完全二叉树的特性 1.具有n个结点的完全二叉树的深度k = Log2n +1 （x表示不大于x的最大整数） 证明：设树的深度为k，则： 2k-1 1 n 2k 1 2k-1 n 2k k-1 log2n 1，则其双亲是i/2; n2。如果2i n ，则结点i 无左孩子，否

14、则其左孩子 是2i n3。如果2i +1 n，则结点i 无右孩子，否则其右孩 子是2i+1 示意图 2i2i2i+12i+1 i i 2i+22i+2 2i+32i+3 i+1i+1 i/2i/2 j层 1 2 j i j+1层 i j 222 1 示意图 2i2i+1 i 2i+2 2i+3 i+1 i/2 LCHILD(i)LCHILD(i+1) RCHILD(i)RCHILD(i+1) 2i+2 2i+3 i+1 2i2i+1 i . . 二叉树的存贮结构 n顺序存贮结构 n链式存贮结构 n考虑数据元素和数据元素之间的关系 二叉树的顺序存贮结构 n考虑 n采用顺序存贮结构，实际要求对非线

15、性的结构线性 化； n树是一个层次结构 n二叉树是有序树 n整个二叉树可以按照从上到下，从左到右的顺序排 序，做标号； n对于满/完全二叉树，可以从根结点开始按序号存放 n对于一般的二叉树，可以参照满二叉树的编码方法 进行编码，位置空的结点空置。 二叉树的顺序存贮结构_C表示 #define MAX_TREE_SIZE100 / 0号单元存放根结点； typedef TElemType sqBiTreeMAX_TREE_SIZE; SqBiTree bi; 顺序存贮结构举例 123456789 10 11 12 1 89101112 45 2 67 3 完全二叉树 顺序存贮结构举例 12345

16、 67 1 67 45 23 非完全二叉树 12345000067 X 二叉树的链式存贮结构 n考虑： n二叉树的数据元素之间的关系 n任一个结点，最多有两个孩子（直接后继元 素） n二叉链表 pLChilddatapRChild data pLChild pRChild 找孩子容易，但不例于找双亲 二叉树的链式存贮结构 n除根结点外，所有结点都有一个双亲结点 （直接前驱元素）； n三叉链表 pLChilddatapRChild data pLChild pRChild 找孩子容易，但不利于找双亲 pParent pParent 二叉链表的C表示 typedef struct BiTNode

17、TElemTypedata; struct BiTNode *pLChild, *pRChild; BiTNode, *BiTree; 链式存贮结构例 A B CD EF G A? B C?D E?F? G? 算法-写出用二叉链表表示给定二叉树的叶结点总数的算法 #include #include typedef char Datatype;/以下为二叉链表的结构定义 typedef struct node Datatype data; node *lchild; node *rchild; BinTreeNode; 算法-写出用二叉链表表示给定二叉树的叶结点总数的算法 typedef Bin

18、TreeNode *BinTree; void CreatBinTree(BinTree *T) /构造二叉链表。T是指向根的指针，故修改了*T就修改了实参 char ch; if (ch=getchar()= ) *T=NULL; else /读入非空格 *T=(BinTreeNode *)malloc(sizeof(BinTreeNode);/生成结点 (*T)-data=ch; CreatBinTree( /构造左子树 CreatBinTree( /构造右子树 算法-写出用二叉链表表示给定二叉树的叶结点总数的算法 /*以下为题目要求算法*/ int GetLeaves( BinTree

19、root) /求叶结点总数 static int leaf=0;/此l用于记叶结点数，注意用静态变量 if(root) /递归计算叶结点数 if(!(root-lchild|root-rchild) leaf+; /如果该结点无左右孩子，则叶子数加1 GetLeaves(root-lchild);/算左子数的叶结点数 GetLeaves(root-rchild);/算右子树的叶结点数 return leaf;/返回结果 /*算法结束*/ 算法-写出用二叉链表表示给定二叉树的叶结点总数的算法 void main() /以下为验证程序 BinTree root; CreatBinTree( int

20、 leaves=GetLeaves(root); printf(Total leaves=%d,leaves); 树的存贮结构 n考虑存贮结构时，主要考虑表示逻辑结 构： n数据元素 n数据元素之间的关系 n树的存贮结构： n顺序存贮结构 n链式存贮结构 树的存贮结构 A B E C D F 1. 除根外的任一个数据元素，都有且仅有一个双亲_ 从纵向，向上描述树； 2. 任一数据元素，有0个或多个孩子_从纵向，向下描 述树 ； 3. 任一数据元素，纵向有孩子，横向有兄弟；_从纵 向和横向描述树 双亲表示法 n一个静态数组，存放所有的结点 n数组的每个数据元素，包括两部 分：数据元素，整数表示该

21、结点 的双亲结点在数组中的位置；根 结点的整数为-1。 n特点： n1. 方便找结点的双亲； n2. 顺序存贮结构； A B C D E F -1 0 0 0 2 2 双亲表示法_C表示 / 树的双亲表示法的存贮结构 #define MAX_TREE_SIZE100 typedef struct PTNode TElemType data;/ 数据元素 int nParent;/ 双亲结点在存贮区中的位置 PTNode; typedef struct PTNode astNodes MAX_TREE_SIZE ; int n;/ 结点数 PTree; 算法：找根 / 采用遍历 Status R

22、oot( PTree i T.n; i+ ) if( T.astNodesi.nParent = -1 ) root = T.astNodesi.data; return OK; return ERROR;/ 存贮结构有错误 / Root 算法：找根 / 找根：考虑树的层次结构 Status Root( PTree k = 0; while( k+ T.n if( k T.n ) root = r.data; return OK; return ERROR; /Root 孩子表示法 n任一数据元素，有0个或多个孩子； n因此可以设计一个链式存贮结构，其结点除放 置数据元素外，还可以放置若干指针

23、，分别用 来指示该结点的所有孩子结点在存贮空间中的 位置。 孩子表示法 n方法1 n根据结点的度，设置结点的指针个数，比如若结点 的度为d: datapChild1pChild2pChildd 问题： n不同的数据元素，结点构造不同； n操作不方便 孩子表示法 n方法2_对方法1的改进 n按照树的度定义结点。若树的度为d n定义degree，表示该结点的度，指针 pChild1 pChildm非空，其他为空 datapChild1pChild2pChildddegree 问题： n因d为树的度，是所有结点的最大的度，因此 树中有相当部分的指针域为空，浪费空间。 n有n个结点的树的度为k，空指针

24、域有n(k-1)+1个 空链域 孩子表示法 n有n个结点的树的度为k，空指针域有n(k-1)+1 个空链域 n证明： nn个结点的树，除根结点外，每个结点有一个双亲， 也就是树中有n-1个分支，即有n-1个链域（指针） n而按该结点定义，n个结点总的指针域有：nk个。 n因此空链域： nk (n-1) = n ( k - 1 ) + 1 n一个静态数组，存放所有的结点 n数组的每个数据元素，包括两部分：数据元素，指针；指针指向 一个链表，链表结点的数据域是一个整数，表示该结点的孩子在 数组中的位置； n特点： n顺序+链式存贮结构； n找孩子容易，找双亲难； A B C D E F 123 4

25、5 孩子表示法孩子表示法 孩子表示法 n在静态数组的的结点增加一个域，表示 该结点的双亲在该树组中的位置。 n有利于寻找双亲结点。 A B C D E F -1 0 0 0 2 2 123 45 孩子表示法_C表示 / 树的孩子表示法 typedef struct CTNode intnChild;/ 该孩子在顺序表中的位置 struct CTNode *pNext; CTNode, *ChildPtr;/ 链表结点 typedef struct TElemType data; ChildPtrpFirstChild;/第一个孩子 CTBox;/ 顺序表的数据元素 孩子表示法_C表示 type

26、def struct CTBox astNodes MAX_TREE_SIZE ; int n, r;/ 结点数和根的位置 CTree;/ 定义整个顺序表 孩子兄弟表示法 n从向下的纵向和横向描述树； n考虑定义结点，除放数据元素外，放两 个指针，一个指向该结点的第一个孩子， 另一个指向该结点的下一个兄弟； 孩子兄弟表示法 typedef struct CSNode TElemTypedata; struct CSNode *pFirstChild; struct CSNode *pNextSibling; CSNode, *CTree; 该表示方法又称二叉树表示法，或二叉链表表示法 data

27、pFirstChildpNextSibling 孩子兄弟表示法 A CBD EF 树和二叉树的关系 n若树采用孩子兄弟表示法，二叉树采用 二叉链表表示，则从存贮结构上看，结 点定义完全相同。因此，在使用该存贮 结构下，树和二叉树是等价的，树可以 转化为二叉树。 npFirstChild pLChild; npNextSibling pRChild; 树和二叉树转化例 A CBD EF A B C DE F 树和二叉树转化例 A B C DE F A B C ED F 树和二叉树转化特征 n从树转化为二叉树，前提： n树采用孩子兄弟表示法； n二叉树采用二叉链表表示法； n从树转化的二叉树，一定

28、没有右子树 n因为树的根结点没有兄弟结点，其 pNextSibling = NULL ，即二叉树的pRChild = NULL; n二叉树不一定能转换为树 森林和二叉树的转换 n若树采用孩子兄弟表示法，二叉树采用二叉链 表表示，则： n任一棵树，都可以找到唯一的一棵二叉树和它对应， 而且该二叉树没有右子树。(因此一棵二叉树，不 一定保证能转换为一棵树) n若把森林中的第二棵树的根结点，看成是第一棵树 的根结点的兄弟结点，则这两棵树可以转换为一棵 二叉树（该二叉树的右子树没有右子树）。 n依次类推，可以认为森林和二叉树是一一对应的， 从而得到二叉树和森林的转换规则 森林和二叉树的转换 n森林到二

29、叉树的转换方法： n如果F = T1, T2, Tm是森林，则 B= (root, LB, RB ). n1.若F为空，即m = 0 ， 则B为空树； n2.若F非空，即m != 0; 则B的根就是ROOT( T1 )； LB是从T1中根结点的子树森林F1 = T11, T12, T1m1转换成的二叉树； RB是森林F = T2, T3, , Tm转换成的二叉树。 森林到二叉树的转换_例 A BCD E F G HI J A B C D E F G H I J A B C D E F G H I J 森林和二叉树的转换 n二叉树到森林的转换方法： nB= (root, LB, RB ). F

30、= T1, T2, Tm: n1. 若B空，则F为空； n2. 若B非空，则F中T1的根ROOT(T1)就是B的根 root，T1中根结点的子树森林F1就是B的LB转换 而成的森林，F中除T1之外其余树组成的森林 F=(T2, T3, Tm)是由B的RB转换成的森林。 二叉树到森林的转换_例 A BC DE F H K JI G A BC DE F H K JI G 二叉树到森林的转换_例 A BC DE F H K JI G A B D EG CF HJ IK 二叉树到森林的转换_例 A BC DE F H K JI G A B D EG CF HJ IK 遍历二叉树遍历二叉树 n顺序存贮结

31、构：容易 n链式存贮结构：不容易 A B E C D F 遍历二叉树遍历二叉树(Traversing Binary Tree) n遍历：按某条搜索路径寻访树中的每个结点， 使每个结点均被访问一次，而且仅被访问一次。 n实际上也就是把树中的结点进行一次排队。 n也就是要把一个非线性结构的树转化为一个线 性结构； n若二叉树采用顺序存贮结构，没有问题，因为 已经线性化了； n若二叉树采用非顺序存贮结构，则必须考虑算 法。 遍历二叉树遍历二叉树 n从树的定义看：递归。 n若有算法M可以遍历二叉树T：M(T)，则 M可以描述为： n对Root( T )访问； n对T的左子树LT，利用方法M访问：M(L

32、T); n对T的右子树RT，利用方法M访问：M(RT); n因此：可以使用递归方法遍历二叉树。 遍历二叉树遍历二叉树 n若以LDR分别表示遍历左子树，访问根结 点，遍历右子树，则可以有方法： nDLR，LDR，LRD，DRL，RDL，RLD n考虑到二叉树有序： nDLR：先（根）序遍历； nLDR：中（根）序遍历； nLRD：后（根）序遍历； 先序遍历二叉树先序遍历二叉树 n具体描述：DLR: n若二叉树为空，则空操作；否则： n1.访问根结点； n2.先序遍历左子树； n3.先序遍历右子树； 中序遍历二叉树中序遍历二叉树 n具体描述：LDR: n若二叉树为空，则空操作；否则： n1. 中序

33、遍历左子树； n2. 访问根结点； n3. 中序遍历右子树； 后序遍历二叉树后序遍历二叉树 n具体描述：LRD: n若二叉树为空，则空操作；否则： n1. 后序遍历左子树； n2. 后序遍历右子树； n3. 访问根结点； 遍历二叉树遍历二叉树 DLR：先（根）序遍历； A B E C D F LDR：中（根）序遍历； LRD：后（根）序遍历； A B D G C E F D G B A E C F G D B E F C A G 先序遍历二叉树算法先序遍历二叉树算法 / 先序遍历二叉树 Status PreOrderTraverse( BiTree T, status ( * visit)(T

34、ElemType e) if( T ) if( (*Visit)(T-data ) if( PreOrderTraverse( T-pLChild, visit ) if( PreOrderTraverse( T-pRChild, visit ) return OK; return ERROR; 先序遍历二叉树算法先序遍历二叉树算法 else return OK; / PreOrderTraverse 中序遍历二叉树算法中序遍历二叉树算法 / 中序遍历二叉树 Status InOrderTraverse( BiTree T, status ( * visit)(TElemType e) if(

35、 T ) if(InOrderTraverse( T-pLChild, visit ) if( (*Visit)(T-data ) if( InOrderTraverse( T-pRChild, visit ) return OK; return ERROR; 中序遍历二叉树算法中序遍历二叉树算法 else return OK; / InOrderTraverse 后序遍历二叉树算法后序遍历二叉树算法 / 后序遍历二叉树 Status PostOrderTraverse( BiTree T, status (* visit)(TElemType e) if( T ) if( PostOrder

36、Traverse( T-pLChild, visit ) if( PostOrderTraverse( T-pRChild, visit ) if( (*Visit)(T-data ) return OK; return ERROR; 后序遍历二叉树算法后序遍历二叉树算法 else return OK; / PostOrderTraverse 二叉树的遍历过程二叉树的遍历过程 - * ab c - - * ab c - *c ba * ab c - * ab c b a 算法分析算法分析 n若不考虑visite()语句，则三种遍历方法 完全相同。 n是递归算法： n树的定义本身就是递归的； n

37、递归和栈密切联系：递归过程实际就是对栈 的操作过程 n可以直接通过对栈的操作，来把递归算法写 为非递归算法 算法分析算法分析 n在中序遍历中，递归工作栈： n栈数据元素： n语句编号：函数返回后，下一条语句的执行地址； n入口参数：BiTree T, 指向（子）树的指针； n访问（子）树执行过程： n左子树-根结点-右子树，。，在此过程中，程序 只是做了压栈操作，直到最左下角的结点为止。因此最 先被执行的是（子）树的最左下的结点，该结点的 pLChild = NULL（否则要继续遍历左子树），因此当栈 的栈顶元素=NULL时，则该节点没有左子树，此时访问 根结点，即出栈（NULL指针），然后访

38、问根结点（栈顶 元素存放的就是根结点）； n开始访问右子树。访问该子树的方法同上：入栈pRChild， 再从1开始。当该子树访问结束后，当前子树执行结束， 需要继续出栈。直到栈空为止。 非递归算法非递归算法 n初始化栈 n根指针入栈（树入栈） n若栈非空： n把左子树入栈，直到最左下角； nNULL指针出栈； n若非空： n（子树）根指针出栈； n访问（子树）根结点； n把右子树入栈（此时采用同一种方法，遍历右子树） 非递归程序非递归程序 / 中序遍历的非递归算法 Status InOrderTraverse( BiTree T, status (*visit)(TElemType e ) I

39、nitStack( S ); Push( S, T );/ 根指针进栈 while( ! StackEmpty( S ) while( GetTop( S, p ) /向左，直到最左下角 Pop( S, p );/ NULL退栈 非递归程序非递归程序 if( !StackEmpty( S) Pop( S, p );/ 根退出 if( ! ( *Visit)(p-data) ) return ERROR; Push( S, p-pRChild ); / if / while return OK; / InOrderTraverse 非递归程序非递归程序 / 中序遍历的非递归算法 Status I

40、nOrderTraverse( BiTree T, status (*visit)(TElemType e ) InitStack( S ); p = T; while( p | !StackEmpty( S ) if( p )/ 根指针进栈，遍历左子树 Push( S, p ); p = ppLChild; 非递归程序非递归程序 else / 根指针出栈，访问根结点，遍历右子树 Gettop ( S, p ); Pop( S, p ); if( !(*Visit)( p-data) return ERROR; p = p-pRChild;/ 右子树 / else / while return

41、 OK; / InOrderTraverse 建立树建立树 n根据一个输入序列，可以构建一棵树吗？ n例：先序序列：ABDCEF，则树=? n根A，B? n加条件：中序序列：DBAECF，则树： n根A,左？DB,右：ECF nB左根 nC右根 建立树建立树 A BC DEF 先序：ABDCEF 后序：DBEFCA A根，其他B和C不等，因此A有两棵 子树，B和C为根，且BD为一棵左子 树，CEF为右子棵。 1。单独一个遍历序列，无法建立树（唯一确定一棵树）； 2。若把树中终端结点的信息补上，则可以通过一个序列 确定一课树 中序：DBAECF 后序：DBEFCA 根：A 左：DB,右：ECF

42、建立树算法建立树算法 / 根据先序序列，创建一棵二叉树 Status CreateBiTree( BiTree if( ch = ) T=NULL; else 建立树算法建立树算法 if( ! (T=(BiTNode *)malloc(sizeof(BiTNode) exit( OVERFLOW ); T-data = ch; CreateBiTree( T-pLChild ); CreateBiTree( T-pRChild ); return OK; / CreateBiTree; 先序建立树示例先序建立树示例 A B C D E G F A B C D E G F A B CD E G

43、F 遍历二叉树遍历二叉树 遍历二叉树，就是按照一定的顺序，访问 结点，实际上就是把非线性的树结构线 性化。 如果在实际应用中，需要反复执行遍历操 作。就有必要保存这种线性化后的结果。 方法？ 遍历二叉树遍历二叉树 n开一个数组，保存遍历的结果； n增加空间开销 n元素之间的关系丢失； n每个结点增加（一）两个指针域，分别 放遍历后结点的直接前驱和直接后继元 素 n增加空间开销 n使用二叉链表中原有的空间。 遍历二叉树遍历二叉树 n二叉链表的特点： nn个结点的二叉树中，存在n+1个空链域， 放NULL指针。 n定义结点： pLChildlTagdataRTag pRChild 遍历二叉树遍历二

44、叉树 nlTag: n0：表示pLChild指示结点的左孩子； n1：表示pLChild指示结点的前驱； nRtag： n0：表示pLChild指示结点的右孩子； n1：表示pLChild指示结点的后继； 遍历二叉树遍历二叉树 nC表示： ntypedef enum n nLink,/指针 nThread/线索 nPointerTag; 遍历二叉树遍历二叉树 ntypedef struct BiThrNode n nTElemTypedata; nStruct BiThrNode *plChild, *pRChild; nPointerTaglTag, Rtag; nBiThrNode, *B

45、iThrTree; 线索二叉树线索二叉树 n以BiThrNode为结点的二叉链表作为二叉 树的存贮结构，叫做线索链表； n指向结点前驱和后继的指针，叫做线索； n加上线索的二叉树，称谓线索二叉树 （Threaded Binary Tree） 。 n对二叉树以某种次序遍历使其变为线索 二叉树的过程叫线索化。 线索二叉树线索二叉树 A BC D E G F 中序遍历：D B F E G A C 00A 00BC 1 D00E FG 1 1111 11 01 线索二叉树线索二叉树 n为方便，在二叉树的线索链表上增加一 个头结点， n其pLChild指向二叉树的根结点，pRChild指 向中序遍历时访

46、问的最后一个结点； n二叉树中序遍历中的第一个结点的pLChild指 向该头结点； n二叉树中序遍历中的最后一个结点的 pRChild指向该头结点； 线索二叉树线索二叉树 n中序遍历的特征： n对任一棵二叉树（子树），最先访问的结点是该树 的最左下角的结点； n所有的非终端结点，下一个结点一定是右子树的第 一个被访问的结点（右子树的最左下角的结点）； n对任一棵二叉树（子树），最后一个被访问的结点 是该树的最右下角的结点； n所有的非终端结点，上一个结点一定是左子树的最 后一个被访问的结点（左子树的最右下角的结点）； 线索二叉树线索二叉树 n线索化后：任一结点： n直接前驱： n若lTag = 0，左子树的最右下角的结点； n若lTag = 1, plChild就指向其直接前驱； n直接后继： n若RTag = 0，右子树的最左下角的结点； n若RTag = 1, pRChild就指向其直接后继； 线索二叉树的遍历线索二叉树的遍历 / 遍历一棵线索二叉树： Status InOrderTraverse_Thr(BiThrTree T,status (*Visit)(TElemType