数据结构PPT树和二叉树PPT学习教案

1、会计学1数据结构数据结构PPT树和二叉树树和二叉树 引 言第1页/共188页第2页/共188页6.1 树的定义树的定义 和基本术语和基本术语第3页/共188页 树的定义第4页/共188页第5页/共188页数据对象数据对象 D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。 若若D为空集，则称为空树为空集，则称为空树 。 否则否则: (1) 在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root； (2) 当当n1时，其余结点可分为时，其余结点可分为m (m0)个互个互 不相交的有限集不相交的有限集T1, T2, , Tm，其中每一，其中每一 棵子集本身又是一

2、棵符合本定义的树，棵子集本身又是一棵符合本定义的树， 称为根称为根root的子树。的子树。 数据关系数据关系 R：ADT Tree第6页/共188页 基本操作：基本操作：查查 找找 类类 插插 入入 类类删删 除除 类类第7页/共188页 Root(T) / 求树的根结点求树的根结点 查找类：查找类：Value(T, cur_e) / 求当前结点的元素值求当前结点的元素值 Parent(T, cur_e) / 求当前结点的双亲结点求当前结点的双亲结点LeftChild(T, cur_e) / 求当前结点的最左孩子求当前结点的最左孩子 RightSibling(T, cur_e) / 求当前结点

3、的右兄弟求当前结点的右兄弟TreeEmpty(T) / 判定树是否为空树判定树是否为空树 TreeDepth(T) / 求树的深度求树的深度TraverseTree( T, Visit() ) / 遍历遍历第8页/共188页InitTree(&T) / 初始化置空树初始化置空树 插入类：插入类：CreateTree(&T, definition) / 按定义构造树按定义构造树Assign(T, cur_e, value) / 给当前结点赋值给当前结点赋值InsertChild(&T, &p, i, c) / 将以将以c为根的树插入为结点为根的树插入为结点p的第的第i棵子树棵子树第9页/共188

4、页 ClearTree(&T) / 将树清空将树清空 删除类：删除类：DestroyTree(&T) / 销毁树的结构销毁树的结构DeleteChild(&T, &p, i) / 删除结点删除结点p的第的第i棵子树棵子树第10页/共188页 树的表示形式树的表示形式第11页/共188页ABCDEFGHIJMKLA( B(E, F(K, L), C(G), D(H, I, J(M) )T1T3T2树根例如例如: :第12页/共188页第13页/共188页基基 本本 术术 语语第14页/共188页结点结点: :结点的度结点的度: :树的度树的度: :叶子结点叶子结点: :分支结点分支结点: :数据

5、元素及若干指向子树的分支拥有的子树数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM第15页/共188页(从根到结点的)路径：路径：结点的层次结点的层次: :树的深度：树的深度： 由从根根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次孩子结点：结点子树的根双亲结点：孩子结点的直接前驱兄弟结点：同一双亲的孩子间堂兄弟：双亲在同一层的结点祖先结点：从根到该结点所经分支的所有结点子孙结点：以某结点为根的子树中的任一结点第16页/共188页() 有确定的根；() 树根和子树根之间为有向关系。有向树

6、：有向树：有序树：有序树：子树之间存在确定的次序关系。无序树：无序树：子树之间不存在确定的次序关系。第17页/共188页任何一棵非空树是一个二元组 Tree = （root，F）其中：root 被称为根结点 F 被称为子树森林森林：森林：是m（m0）棵互不相交的树的集合ArootBCDEFGHIJMKLF第18页/共188页对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点第19页/共188页线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多

7、个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )第20页/共188页6.2 二二 叉叉 树树第21页/共188页6.2.1 二叉树的定义二叉树的定义 二叉树（二叉树（Binary Tree）或为空树，或是由一个）或为空树，或是由一个根结点加上两棵分别称为根结点加上两棵分别称为左子树左子树和和右子树右子树的、的、互不相交的互不相交的二叉树组成。二叉树组成。ABCDEFGHK根结点左子树右子树第22页/共188页二叉树的五种基本形态：二叉树的五种基本形态：N空树空

8、树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均不树均不为空树为空树第23页/共188页第24页/共188页二叉树的主要基本操作二叉树的主要基本操作：查查 找找 类类插插 入入 类类删删 除除 类类第25页/共188页 Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Vi

9、sit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit();第26页/共188页 InitBiTree(&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);第27页/共188页ClearBiTree(&T); DestroyBiTree(&T);DeleteChild(T, p, LR);第28页/共188页6.2.2 二叉树二叉树 的性质的性质第29页/

10、共188页用归纳法证明用归纳法证明： 归纳基归纳基： 归纳假设：归纳假设： 归纳证明：归纳证明：i = 1 层时，只有一个根结点： 2i-1 = 20 = 1；假设对所有的 j，1 j i，命题成立；二叉树上每个结点至多有两棵子树，则第 i 层的结点数 = 2i-2 2 = 2i-1 。第30页/共188页证明：证明： 基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+ +2k-1 = 2k-1 。第31页/共188页证明：证明：设设 二叉树上结点总数 n = n0 + n1 + n2又又 二叉树上分支总数 b = n1+2n2 而 b = n-1 = n0 + n1 + n2

11、 - 1由此，由此， n0 = n2 + 1 。第32页/共188页两类两类特殊特殊的二叉树：的二叉树：满二叉树满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树完全二叉树：树中所含的 n 个结点和满二叉树中编号编号为为 1 至至 n 的结点的结点一一对应。123456789 10 11 12 13 14 15abcdefghij第33页/共188页 性质性质 4 ： 具有 n 个结点的完全二叉树的深度深度为 log2n +1 。证明：证明：设设完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子， 否则，编号为 2i 的

12、结点为其左孩子左孩子结点；(3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子右孩子结点。第35页/共188页第36页/共188页6.2.3 二叉树的存储结构二叉树的存储结构二、二叉树的链式二、二叉树的链式 存储结构存储结构一、一、 二叉树的顺序二叉树的顺序 存储结构存储结构第37页/共188页#define MAX_TREE_SIZE 100 / 二叉树的最大结点数typedef TElemType SqBiTreeMAX_ TREE_SIZE; / 0号单元存储根结点SqBiTree bt;一、一、 二叉树的顺序存储结构二叉树的顺序存储结构第38页/共18

13、8页个足以反映整个二叉树结构的线性个足以反映整个二叉树结构的线性序列，如下图所示。序列，如下图所示。二叉树的顺序存储结构二叉树的顺序存储结构第39页/共188页第40页/共188页第41页/共188页第42页/共188页练习练习:ABCDEF A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 131401326第43页/共188页二、二叉树的链式存储表示二、二叉树的链式存储表示1. 1. 二叉链表二叉链表2三叉链表三叉链表3 3双亲链表双亲链表4线索链表线索链表第44页/共188页ADEBCF rootlchild data rchild结点结构结点结构:1.

14、1. 二叉链表二叉链表二叉链表二叉链表第45页/共188页ABCDEF二叉树二叉树第46页/共188页typedef struct BiTNode / 结点结构结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;lchild data rchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下: :第47页/共188页ADEBCF root 2三叉链表三叉链表parent lchild data rchild结点结构结点结构:第48页/共188页 typedef struct

15、 TriTNode / 结点结构结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct TriTNode *parent; /双亲指针 TriTNode, *TriTree;parent lchild data rchild结点结构结点结构:C 语言的类型描述如下语言的类型描述如下: :第49页/共188页0123456B2C0A -1D2E3F4 data parent结点结构结点结构:3 3双亲链表双亲链表LRTagLRRRL第50页/共188页 typedef struct BPTNode / 结点结构

16、结点结构 TElemType data; int *parent; / 指向双亲的指针 char LRTag; / 左、右孩子标志域 BPTNode typedef struct BPTree / 树结构树结构 BPTNode nodesMAX_TREE_SIZE; int num_node; / 结点数目 int root; / 根结点的位置 BPTree第51页/共188页6.3.1二叉树的遍历二叉树的遍历6.3 遍历二叉树和遍历二叉树和线索二叉树线索二叉树第52页/共188页一、问题的提出一、问题的提出二、先左后右的遍历算法二、先左后右的遍历算法三、算法的递归描述三、算法的递归描述四、中

17、序遍历算法的非递归描述四、中序遍历算法的非递归描述五五、遍历算法的应用举例遍历算法的应用举例第53页/共188页 如何按着某条搜索路径如何按着某条搜索路径巡访巡访二叉二叉树中的每个结点，使得每个结点树中的每个结点，使得每个结点均被均被访问一次访问一次，而且，而且仅被访问一次仅被访问一次。一、问题的提出一、问题的提出“访问访问”的含义可以很广，如：输出结的含义可以很广，如：输出结点的信息等。点的信息等。第54页/共188页 “遍历遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构， 每个结点有两个后继每个结点有两个后

18、继，则存在如何遍历存在如何遍历即按什么样的搜索搜索路径路径遍历的问题。第55页/共188页二叉树的遍历方法二叉树的遍历方法 二叉树由根、左子树、右子树三部分组成 二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树令：令：L L：遍历左子树 D D：访问根结点 R R：遍历右子树 有六种遍历方法： D DL LR R，L LD DR R，L LR RD D， D DR RL L，R RD DL L，R RL LD D 约定先左后右,有三种遍历方法： D DL LR R、L LD DR R、L LR RD D ，分别称为 先序遍历、中序遍历、后序遍历 A A F F G G E E D D C

19、 C B B第56页/共188页58 先序遍历（先序遍历（ D DL LR R ） 若二叉树非空若二叉树非空 （1 1）访问根结点；）访问根结点； （2 2）先序遍历左子树；）先序遍历左子树； （3 3）先序遍历右子树）先序遍历右子树； 先序遍历序列：先序遍历序列： A A F F G G E E D D C C B B例：先序遍历右图所示的二叉树例：先序遍历右图所示的二叉树 （1 1）访问根结点）访问根结点A A （2 2）先序遍历左子树：即按先序遍历左子树：即按D DL LR R的顺序遍历的顺序遍历左子树左子树 （3 3）先序遍历右子树：即按）先序遍历右子树：即按D DL LR R的顺序遍

20、历的顺序遍历右子树右子树A BCDFGE二、先左后右的遍历算法二、先左后右的遍历算法第57页/共188页59中序遍历（中序遍历（ L LD DR R ）若二叉树非空若二叉树非空（1 1）中序遍历左子树）中序遍历左子树（2 2）访问根结点）访问根结点（3 3）中序遍历右子树）中序遍历右子树 中序遍历序列： A A F F G G E E D D C C B B例：中序遍历右图所示的二叉树例：中序遍历右图所示的二叉树 （1 1）中序遍历左子树：即按）中序遍历左子树：即按L LD DR R的顺序遍历的顺序遍历左子树左子树 （2 2）访问根结点）访问根结点 A A （3 3）中序遍历右子树：即按中序遍

21、历右子树：即按L LD DR R的顺序遍历的顺序遍历右子树右子树D BCGFAE第58页/共188页60后序遍历（后序遍历（L LR RD D）若二叉树非空若二叉树非空（1 1）后序遍历左子树）后序遍历左子树（2 2）后序遍历右子树）后序遍历右子树（3 3）访问根结点）访问根结点 后序遍历序列：例：后序遍历右图所示的二叉树例：后序遍历右图所示的二叉树 （1 1）后序遍历左子树：即按）后序遍历左子树：即按L LR RD D的顺序遍历的顺序遍历左子树左子树 （2 2）后序遍历右子树：即按）后序遍历右子树：即按L LR RD D的顺序遍历的顺序遍历右子树右子树 （3 3）访问根结点）访问根结点 A

22、A A A F F G G E E D D C C B BD GCEAFB第59页/共188页61 e e d d c c b b f f a a + + * * / / - - - - 后序遍历序列： 中序遍历序列： 先序遍历序列：例：先例：先中序遍历序遍历、中序遍历、中序遍历序遍历、中序遍历、后后序遍历下图所示的二叉树序遍历下图所示的二叉树前缀表达式前缀表达式中缀表达式中缀表达式后缀表达式后缀表达式- + a * b - c d /e fa + b * c - d - e /fa b c d -* + e f /-第60页/共188页R A DE C HF GBK练习：求下列二叉链表和二叉

23、树的三种遍历次序练习：求下列二叉链表和二叉树的三种遍历次序ABCDEFGHK第61页/共188页这实际上是这实际上是先序遍历的递归定义，先序遍历的递归定义，我们知道递归定义包括两个部分：我们知道递归定义包括两个部分：1 1）基本项基本项（也叫终止项）；（也叫终止项）； 2 2）递归项递归项 若二叉树非空若二叉树非空 （1 1）访问根结点；）访问根结点； （2 2）先序遍历左子树）先序遍历左子树 （3 3）先序遍历右子树；）先序遍历右子树；先序遍历递归定义先序遍历递归定义递归项递归项上面介绍了三种遍历方法，显然是用递归的方式给出的三种遍历方上面介绍了三种遍历方法，显然是用递归的方式给出的三种遍历

24、方法，以先序为例：法，以先序为例：先序遍历（先序遍历（D DL LR R）的定义：）的定义：该定义隐含着该定义隐含着若二叉树为空，结束若二叉树为空，结束 三、算法的递归描述三、算法的递归描述第62页/共188页上面先序遍历的定义等价于：上面先序遍历的定义等价于：若二叉树为空，结束若二叉树为空，结束 基本项基本项（也叫终止项）（也叫终止项）若二叉树非空若二叉树非空 递归项递归项 （1 1）访问根结点；）访问根结点； （2 2）先序遍历左子树）先序遍历左子树 （3 3）先序遍历右子树；）先序遍历右子树； 下面给出下面给出先序、中序、后序遍历递归算法，为了增加算法的先序、中序、后序遍历递归算法，为了

25、增加算法的可读性，这里对书上算法作了简化，没有考虑访问结点出错的可读性，这里对书上算法作了简化，没有考虑访问结点出错的情况（即我们假设调用函数情况（即我们假设调用函数visit( )visit( )访问结点总是成功的。访问结点总是成功的。第63页/共188页1先序遍历递归算法先序遍历递归算法 void PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e) /采用二叉链表存贮二叉树，采用二叉链表存贮二叉树， visit( )是访问结点的函数。本算法是访问结点的函数。本算法/先序遍历以为根结点指针的二叉树，对每个数据元素调用函数先序遍历以为根

26、结点指针的二叉树，对每个数据元素调用函数/Visit( ) if (T) /若二叉树为空，结束返回若二叉树为空，结束返回 / 若二叉树不为空，访问根结点；遍历左子树，遍历右子树若二叉树不为空，访问根结点；遍历左子树，遍历右子树 Visit(T-data)； PreOrderTraverse(T-lchild, Visit); PreOrderTraverse(T-rchild, Visit); /PreOrderTraverse最简单的最简单的Visit函数是：函数是： Status PrintElement(TElemType e) /输出元素输出元素e的值的值 printf(e); ret

27、urn OK; D D A A B B C C E E FFT T第64页/共188页2 中序遍历递归算法中序遍历递归算法 void InOrderTraverse(BiTree T, Status(*Visit)(TElemType e) /采用二叉链表存贮二叉树，采用二叉链表存贮二叉树， visit( )是访问结点的函数。本算法中是访问结点的函数。本算法中序遍历以为根结点指针的二叉树，对每个数据元素调用函数序遍历以为根结点指针的二叉树，对每个数据元素调用函数Visit( ) if (T) /若二叉树为空，结束返回若二叉树为空，结束返回 / 若二叉树不为空，遍历左子树，访问根结点，遍历右子树

28、若二叉树不为空，遍历左子树，访问根结点，遍历右子树 InOrderTraverse(T-lchild, Visit); Visit(T-data)； InOrderTraverse(T-rchild, Visit); / InOrderTraverse 你能写出你能写出后序遍历递归算法了吧后序遍历递归算法了吧?第65页/共188页3 后序遍历递归算法后序遍历递归算法 void PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e) /采用二叉链表存贮二叉树，采用二叉链表存贮二叉树， visit( )是访问结点的函数。本算法中是访问结点的

29、函数。本算法中序遍历以为根结点指针的二叉树，对每个数据元素调用函数序遍历以为根结点指针的二叉树，对每个数据元素调用函数Visit( ) if (T) /若二叉树为空，结束返回若二叉树为空，结束返回 / 若二叉树不为空，遍历左子树，遍历右子树，访问根结点若二叉树不为空，遍历左子树，遍历右子树，访问根结点 PostOrderTraverse(T-lchild, Visit); PostOrderTraverse(T-rchild, Visit); Visit(T-data)； /PostOrderTraverse 第66页/共188页G HD E FB CA第67页/共188页四、中序遍历算法的非

30、递归描述四、中序遍历算法的非递归描述Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 采用二叉链表存储结构，采用二叉链表存储结构，Visit是对数据元素操作的应用是对数据元素操作的应用/函数函数.中序遍历二叉树中序遍历二叉树T的非递归算法，对每个数据元素调的非递归算法，对每个数据元素调/用函数用函数Visit。 InitStack(S); Push(S, T); / 根指针进栈根指针进栈 while (!StackEmpty(S) while (GetTop(S, p) & p) Push(S, p-lchild); /

31、向左走到尽头向左走到尽头 Pop(S, p); / 空指针退栈空指针退栈 if (!StackEmpty(S) / 访问结点，向右一步访问结点，向右一步 Pop(S, p); if (!Visit(p-data) return ERROR; Push(S, p-rchild); return OK; / InOrderTraverse第68页/共188页Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 采用二叉链表存储结构，采用二叉链表存储结构，Visit是对数据元素操作的应用是对数据元素操作的应用/函数。中序遍历二叉树函

32、数。中序遍历二叉树T的非递归算法，对每个数据元素调的非递归算法，对每个数据元素调/用函数用函数Visit。 InitStack(S); p = T; while (p | !StackEmpty(S) if (p) Push(S, p); p = p-lchild; / 非空指针进栈，继续左进非空指针进栈，继续左进 else /上层指针退栈，访问其所指结点，再向右进上层指针退栈，访问其所指结点，再向右进 Pop(S, p); if (!Visit(p-data) return ERROR; p = p-rchild; return OK; / InOrderTraverse第69页/共188页

33、ABCDGEFABCNULLSGetToplchild)& (!T-rchild) count+; / 对叶子结点计数 CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / if / CountLeaf第73页/共188页2、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)算法基本思想算法基本思想: : 从二叉树深度的定义可知，二叉树的二叉树的深度应为其左、右子树深度的最大值加深度应为其左、右子树深度的最大值加1 1。由此，需先分别求得左、右子树的深度，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、求得左、

34、右子树深度的最大值，然后加右子树深度的最大值，然后加 1 1 。 首先分析二叉树的深度二叉树的深度和它的左左、右子右子树深度树深度之间的关系。第74页/共188页int Depth (BiTree T ) / 返回二叉树的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval;第75页/共188页3、复制二

35、叉树、复制二叉树其基本操作为：生成一个结点。其基本操作为：生成一个结点。根元素根元素T左子树左子树右子树右子树根元素根元素NEWT左子树左子树右子树右子树左子树左子树右子树右子树(后序遍历后序遍历)第76页/共188页BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ) if (!(T = (BiTNode*)malloc(sizeof(BiTNode) exit(OVERFLOW); T- data = item; T- lchild = lptr; T- rchild = rptr; return T; 生

36、成一个二叉树的结点生成一个二叉树的结点(其数据域为其数据域为item,左指针域为左指针域为lptr,右指针域为右指针域为rptr)第77页/共188页BiTNode *CopyTree(BiTNode *T) if (!T ) return NULL; if (T-lchild ) newlptr = CopyTree(T-lchild);/复制左子树 else newlptr = NULL; if (T-rchild ) newrptr = CopyTree(T-rchild);/复制右子树 else newrptr = NULL; newT = GetTreeNode(T-data, ne

37、wlptr, newrptr); return newT; / CopyTree第78页/共188页ABCDEFGHK D C B H K G F E A例如：下列二叉例如：下列二叉树的复制过程如树的复制过程如下：下：newT第79页/共188页 为二叉树建立二叉链表为二叉树建立二叉链表 输入：输入：二叉树的先序序列二叉树的先序序列 结果：结果：二叉树的二叉链表二叉树的二叉链表 遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。是否可在利用。是否可在利用遍历，建立遍历，建立二叉链表的所有结点并完成相应结点二叉链表的所有结点并完成相应结

38、点的链接？的链接？基本思想基本思想：输入（输入（在空子树处添加在空子树处添加* *的二叉树的）先序序列（设每的二叉树的）先序序列（设每个元素是个元素是一个字符）按先序遍历的顺序，建立二叉链表的所有结点一个字符）按先序遍历的顺序，建立二叉链表的所有结点并完成相应结点的链接并完成相应结点的链接第80页/共188页 D D A A B B C C E E F F T T 先序序列：A B D F C E（在空子树处添加（在空子树处添加* *的二叉树的）先序序列：的二叉树的）先序序列： A B D A B D * * F F * * * * * *C E C E * * * * * * A A F F

39、 E E D D C C B B* A A F F E E D D C C B B第81页/共188页Status CreateBiTree(BiTree &T) /输入（在空子树处添加*的二叉树的）先序序列（设每个元/素是一个字 符）按先序遍历的顺序，建立二叉链表，并将/该二叉链表根结点指针赋给T scanf (&ch); if (ch= = * )T=NULL; / 若ch= = * 则T=NULL返回 else / 若ch! = * if (! (T=(BiTNode * )malloc(sizeof(BiTNode) exit(OVERFLOW); T-date = ch; / 建立（

40、根）结点 CreateBiTree(T-lchild); /构造左子树 CreateBiTree(T-rchild); /构造右子树 return OK;/CreateBiTree第82页/共188页84分析：若二叉树的任意两个结点的值都不相同，则二叉树的前序序列和中序序列能唯一确定一棵二叉树。另外，由前序序列和中序序列的定义可知，前序序列中第一个结点必为根结点，而在中序序列中，根结点刚好是左、右子树的分界点，因此，可按如下方法建立二叉树：由二叉树的先序和中序序列建立二叉树由二叉树的先序和中序序列建立二叉树二叉树的先序序列二叉树的中序序列左子树左子树左子树左子树 右子树右子树右子树右子树根根根

41、根第83页/共188页851.1.用前序序列的第一个结点作为根结点用前序序列的第一个结点作为根结点; ;2.2.在中序序列中查找根结点的位置，并以此为界将中序序在中序序列中查找根结点的位置，并以此为界将中序序列划分为左、右两个序列列划分为左、右两个序列( (左、右子树左、右子树););3.3.根据左、右子树的中序序列中的结点个数，将前序序根据左、右子树的中序序列中的结点个数，将前序序列去掉根结点后的序列划分为左、右两个序列，它们分别是列去掉根结点后的序列划分为左、右两个序列，它们分别是左、右子树的前序序列左、右子树的前序序列; ;4.4.对左、右子树的前序序列和中序序列递归地实施同样方对左、右

42、子树的前序序列和中序序列递归地实施同样方法，直到所得左、右子树为空。法，直到所得左、右子树为空。假设前序序列为假设前序序列为ABDGHCEFIABDGHCEFI，中序序列为中序序列为GDHBAECIFGDHBAECIF， 则得到的二叉树如下页所则得到的二叉树如下页所示示第84页/共188页861. 1. A A为根结点为根结点A BDGH CEFI GDHB A ECIF BDGHCEFIA2. 2. B B为左子树的根结为左子树的根结点点B DGHGDH BCEFIDHGBA3. 3. D D为左子树的左子树为左子树的左子树的根结点的根结点 A B G H D C E F I 第85页/共1

43、88页87 A B G H D C FI E 4. 4. C C为右子树的根结点为右子树的根结点 A B G H D C F I E 5. 5. F F为右子树的右为右子树的右子树的根结点子树的根结点C E FIE C IF第86页/共188页a b c d e f gc b d a e g f例如例如: :aab bccddeeffggabcdefg先序序列中序序列第87页/共188页ACBEDFGABCDEFGABCFDEG第88页/共188页第89页/共188页遍历二叉树的结果是， 求得结点的一个线性序列。ABCDEFGHK例如:先序先序序列: A B C D E F G H K中序中序

44、序列: B D C A H G K F E后序后序序列: D C B H K G F E A一、一、线索二叉树的定义线索二叉树的定义第90页/共188页在这样的线性序列中，很容易求得某个结点在某种在这样的线性序列中，很容易求得某个结点在某种遍历下的直接前驱和后继。然而，有时我们希望不进行遍历下的直接前驱和后继。然而，有时我们希望不进行遍历就能快速找到某个结点在某种遍历下的直接前驱和遍历就能快速找到某个结点在某种遍历下的直接前驱和后继，这样，就应该把每个结点的直接前驱和直接后继后继，这样，就应该把每个结点的直接前驱和直接后继记录下来。为了做到这一点，可以在原来的二叉链表结记录下来。为了做到这一点

45、，可以在原来的二叉链表结点中，再增加两个指针域，一个指向前驱，一个指向后点中，再增加两个指针域，一个指向前驱，一个指向后继，但这样做将会浪费大量存贮单元，存贮空间的利用继，但这样做将会浪费大量存贮单元，存贮空间的利用率相当低率相当低( (一个结点中有一个结点中有4 4个指针，个指针，1 1个指左孩子，个指左孩子，1 1个指个指右孩子，右孩子，1 1个指前驱，个指前驱，1 1个指后继个指后继) )，而原来的左、右孩子，而原来的左、右孩子域有许多空指针又没有利用起来。为了不浪费存贮空间，域有许多空指针又没有利用起来。为了不浪费存贮空间，我们利用原有的孩子指针为空时来存放直接前驱和后继，我们利用原有

46、的孩子指针为空时来存放直接前驱和后继，这样的指针称为这样的指针称为“线索线索”，加线索的过程称为，加线索的过程称为线索化线索化，加了线索的二叉树，称为加了线索的二叉树，称为线索二叉树线索二叉树，对应的二叉链表，对应的二叉链表称为称为线索二叉链表线索二叉链表。一、一、线索二叉树的定义线索二叉树的定义第91页/共188页指向该线性序列中的“前驱”和 “后继” 的指针指针，称作“线索线索”加了线索的二叉树，称作 “线索二叉树线索二叉树”包含 “线索” 的二叉链表，称作 “线线索链表索链表”A B C D E F G H K D C B E 第92页/共188页在线索二叉树中，由于有了线索，无需遍历二

47、叉在线索二叉树中，由于有了线索，无需遍历二叉树就可以得到任一结点在某种遍历下的直接前驱和后树就可以得到任一结点在某种遍历下的直接前驱和后继。但是，我们怎样来区分孩子指针域中存放的是左、继。但是，我们怎样来区分孩子指针域中存放的是左、右孩子信息还是直接前驱或直接后继信息呢右孩子信息还是直接前驱或直接后继信息呢? ?为此，为此，在二叉链表结点中，还必须增加两个标志域在二叉链表结点中，还必须增加两个标志域ltagltag、rtagrtag。 ltag和rtag定义如下： 0 lchild域指向结点的左孩子域指向结点的左孩子 ltag= 1 lchild域指向结点在某种遍历下的直接前域指向结点在某种遍

48、历下的直接前驱驱 0 rchild域指向结点的右孩子域指向结点的右孩子 rtag= 1 rchild域指向结点在某种遍历下的直接后域指向结点在某种遍历下的直接后继继 第93页/共188页这样，二叉链表中每个结点还是有这样，二叉链表中每个结点还是有5个个域，但其中只有域，但其中只有2个指针，较原来的个指针，较原来的4个指个指针要方便。增加线索后的二叉链表结点结针要方便。增加线索后的二叉链表结点结构可描述如下：构可描述如下： lchild ltag data rtag rchild 第94页/共188页typedef struct BiThrNod TElemType data; struct B

49、iThrNode *lchild, *rchild; / 左右指针 PointerThr LTag, RTag; / 左右标志 BiThrNode, *BiThrTree;二、线索的描述：1、类型定义：、类型定义： typedef enum Link, Thread PointerThr; / Link=0:指针，Thread=1:线索第95页/共188页2线索的画法线索的画法在二叉树或二叉链表中，若左孩子为空，则在二叉树或二叉链表中，若左孩子为空，则画出它的直接前驱，右孩子为空时，则画出它的画出它的直接前驱，右孩子为空时，则画出它的直接后继，左右孩子不为空时，不需画前驱和后直接后继，左右孩子

50、不为空时，不需画前驱和后继。这样就得到了线索二叉树或线索二叉链表。继。这样就得到了线索二叉树或线索二叉链表。第96页/共188页 A D C B 0 A 0 1 B 1 0 C 1 root 1 D 1 A D C B NULL (a) 二叉树 (b)先序线索二叉树 (c)先序线索二叉链表 图 先序线索示意图 先序序列为：ABCD第97页/共188页 A D C B NULL NULL （a）中序二叉树 （b） 中序线索二叉链表 图 中序线索示意图 0 A 0 root 1 D 1 0 C 1 1 B 1 中序序列为：BADC第98页/共188页 C 0 A 0 1 B 1 0 C 1 1 D

51、 1 root D B A NULL (a)后序线索二叉树 (b)后序线索二叉链表 图 后序线索示意图 后序序列为：BDCA第99页/共188页ABCDE第100页/共188页ABCDE A B D C ET先序序列：ABCDE先序线索二叉链表00001111 11第101页/共188页ABCDE A B D C ET中序序列：BCAED中序线索二叉链表0000111111第102页/共188页ABCDE A B D C ET后序序列：CBEDA后序线索二叉链表0000111111第103页/共188页ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：BCAE

52、D带头结点的中序线索二叉链表 0 1头结点：ltag=0, lchild指向根结点rtag=1, rchild指向遍历序列中最后一个结点遍历序列中第一个结点的lchild域和最后一个结点的rchild域都指向头结点 A B D C ET中序序列：BCAED中序线索二叉链表0000111111第104页/共188页 建立线索二叉树，或者说对二叉树线索化，实质上就建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前结点的左、右指针域是否为空，如果为空，将检查当前结点的左、右指针域是否为空，如果为空，将

53、它们改为指向前驱结点或后继结点的线索。为实现这一它们改为指向前驱结点或后继结点的线索。为实现这一过程，设指针过程，设指针pre始终指向刚刚访问过的结点，即若指针始终指向刚刚访问过的结点，即若指针p指向当前结点，则指向当前结点，则pre指向它的前驱，以便增设线索。指向它的前驱，以便增设线索。 此外，在对一棵二叉树加线索时，必须首先申请一个此外，在对一棵二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间二叉树线索化后，还需建立最后一个结点与头结点之间的线索。的线索。 三、建

54、立线索二叉树三、建立线索二叉树第105页/共188页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 = p; pre = p; / 保持 pre 指向 p 的前驱 InThreading(p-rchild); / 右子树线索化 / if / InTh

55、reading第106页/共188页Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) / 构建中序线索链表 if (!(Thrt = (BiThrTree)malloc( sizeof( BiThrNode) exit (OVERFLOW); Thrt-LTag = Link; Thrt-RTag =Thread; Thrt-rchild = Thrt; / 添加头结点 return OK; / InOrderThreading 第107页/共188页if (!T) Thrt-lchild = Thrt; else Thrt-lchil

56、d = T; pre = Thrt; InThreading(T); pre-rchild = Thrt; / 处理最后一个结点 pre-RTag = Thread; Thrt-rchild = pre; 第108页/共188页四、四、 线索二叉树上的运算线索二叉树上的运算1线索二叉树上的查找线索二叉树上的查找 （1）查找指定结点在中序线索二叉树中的的直接后继）查找指定结点在中序线索二叉树中的的直接后继若所找结点右标志若所找结点右标志rtag=1，则右孩子域指向中序后继，则右孩子域指向中序后继，否则，中序后继应为否则，中序后继应为遍历右子树时的第一个访问结点遍历右子树时的第一个访问结点,即右即

57、右子树中最左下的结点子树中最左下的结点（参见下图）。从下图中可知，（参见下图）。从下图中可知，x的后的后继为继为xk 。 X X1 X2 XK P X 0 P 0 x1 0 x2 1 xk 图 求中序后继示意图 第109页/共188页（2）查找指定结点在中序线索二叉树中的的直接）查找指定结点在中序线索二叉树中的的直接前驱前驱若所找结点左标志若所找结点左标志ltag=1，则左孩子域指向中序前驱，则左孩子域指向中序前驱，否则，中序前驱应为否则，中序前驱应为遍历左子树时的最后一个访问结点，即遍历左子树时的最后一个访问结点，即左子树中最右下的结点左子树中最右下的结点（参见下图）。从下图中可知，（参见下

58、图）。从下图中可知，x的的前驱为前驱为xk 。 X X1 X2 xk P 0 X P x1 0 x2 0 xk 1 图 求中序前驱示意图 第110页/共188页(3) 查找指定点在先序线索二叉树中的直接后继查找指定点在先序线索二叉树中的直接后继先序后继的查找比较方便，若无左孩子，右先序后继的查找比较方便，若无左孩子，右孩子为后继，否则左孩子为后继。孩子为后继，否则左孩子为后继。 (4) 查找指定结点在后序线索二叉树中的直接前查找指定结点在后序线索二叉树中的直接前驱驱后序前驱的查找也比较方便，若左孩子为空，后序前驱的查找也比较方便，若左孩子为空，左链指前驱，否则，若右子树为空，左孩子为前驱，左链

59、指前驱，否则，若右子树为空，左孩子为前驱，否则右孩子为前驱。否则右孩子为前驱。 求后序后继和先序前驱都比较麻烦，在此不再求后序后继和先序前驱都比较麻烦，在此不再作进一步介绍。作进一步介绍。第111页/共188页2线索二叉树上的遍历线索二叉树上的遍历 遍历某种次序的线索二叉树，只要从该次序下遍历某种次序的线索二叉树，只要从该次序下的开始结点出发，反复找到结点在该次序下的后继，的开始结点出发，反复找到结点在该次序下的后继，直到后继为空。这对于中序线索和前序线索二叉树直到后继为空。这对于中序线索和前序线索二叉树很方便，但对于后序线索二叉树较麻烦很方便，但对于后序线索二叉树较麻烦(因求后序因求后序后继

60、较麻烦后继较麻烦)。故后序线索对于遍历没有什么意义。故后序线索对于遍历没有什么意义。第112页/共188页中序线索链表的遍历算法中序线索链表的遍历算法 中序遍历的第一个结点中序遍历的第一个结点 ？ 在中序线索化链表中结点的后继在中序线索化链表中结点的后继 ？左子树上处于“最左下最左下”（没有左子树）的结点。若若无右子树，则为则为后继线索后继线索所指结点；否则为否则为对其右子树右子树进行中序遍历遍历时访问的第一个结点。第一个结点。第113页/共188页void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e) p = T-lc