2014/47 Ch.6树 数据结构 ■树形结构： ◆二叉树，树，森林等 Ch.6树 ◆结点间有分支，具有层次关系 ■特征： ·每个结点最多只有一个直接前驱，但可有多个直间后 计算机学院 继。 肖明军 。开始结点一根 ◆终端结点一叶 Email:xiaomj@ustc.edu.cn ◆其余结点一内部结点 http://staff.ustc.edu.cn/~xiaomj 应用：家谱、行政架构等，计算机系统中的文件 目录等 s6.1树的概念 S6.1树的概念 递归定义：刻画了树的固有特性：非空树由若干 ■Def:制是n(n>=O)个结点的有限集T,T为空时称为空树， 棵子树构成，子树由较小子树构成。 否测则它满足： 表示 ◆有且仅有一个特定的称为损的结点： 种解.TT 第一层 分支结点 8 子 (。树形表示法 ()数套集合表云选 (口入表表示法 (A(B(E.F(I.J)).C.D(G.HJ)) (D广义表表示法 86.1树的概念 S6.1树的概念 术语： ■术语： ①结点的度：结点拥有的子树数目（树的度） ⑧路径：道路（自上而下） ②叶子：终端结点，度为O的结点 若存在一结点序列k,k2,k,使得k是k的双亲 ③分支结点：非终端结点，度>O (1<=K=小1)，则称该序列是从k,到k的一条路径或 道路，路径长度为边数-1. ③内部结点：根之外的分支结点 ②粗先和子孙：若k到k有一路径，则k是k的粗先，k ⑤根：开始结点 是k的子孙， ⑥孩子、双亲：某结点的子树的根称为该 轴点A的祖先是从根到A的路径上所经过的所有结点 结点的孩子，该结点为孩子的双亲 结点A的于孙是以A为根的子树中的所有结点. 直接前驱（双亲）直接后继（孩子） 真祖先和真子孙不包含自身 ⑦兄弟：同一双亲的孩子互为兄弟 鲁层数从根起算（为1或0），其余结点的层数是其双 亲的层敷+1
2014/4/7 1 数据结构 Ch.6 树 1 计 算 机 学 院 肖明军 Email: xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj Ch.6 树 树形结构： 二叉树，树，森林等 结点间有分支，具有层次关系 特征： 每个结点最多只有一个直接前驱，但可有多个直间后 2 继． 开始结点 —— 根 终端结点 —— 叶 其余结点 —— 内部结点 应用：家谱、行政架构等，计算机系统中的文件 目录等 §６.１树的概念 Def: 树是n (n>=0) 个结点的有限集Ｔ，Ｔ为空时称为空树， 否则它满足： 有且仅有一个特定的称为根的结点； 其余结点可分为m (m>=0) 个互不相交的子集Ｔ1 ，Ｔ2，…Ｔm， 其中每个子集本身又是一棵树，并称之为根的子树． 3 §６.１树的概念 递归定义：刻画了树的固有特性：非空树由若干 棵子树构成，子树由较小子树构成． 表示： 4 §６.１树的概念 术语： ① 结点的度：结点拥有的子树数目（树的度） ② 叶子：终端结点，度为０的结点 ③ 分支结点：非终端结点，度＞０ ④ 内部结点：根之外的分支结点 5 ⑤ 根：开始结点 ⑥ 孩子、双亲：某结点的子树的根称为该 结点的孩子，该结点为孩子的双亲 直接前驱（双亲） 直接后继（孩子） ⑦ 兄弟：同一双亲的孩子互为兄弟 §６.１树的概念 术语： ⑧ 路径：道路（自上而下） 若存在一结点序列k1,k2,…，kj ，使得ki 是ki+1的双亲 （１<=i<=j-1），则称该序列是从k1到kj 的一条路径或 道路，路径长度为边数j-1. 6 ⑨ 祖先和子孙：若k到ks有一路径，则k是ks的祖先，ks 是k的子孙． 结点Ａ的祖先是从根到Ａ的路径上所经过的所有结点． 结点Ａ的子孙是以Ａ为根的子树中的所有结点． 真祖先和真子孙不包含自身 ⑩ 层数从根起算（为１或０），其余结点的层数是其双 亲的层数＋１
201447 86.1树的概念 86.1树的概念 ■术语： ■逻辑特征： 11高（深）度：制中结点的量大层数 √父子关系（非线性关系）：任一结点至多有一直接前 12堂兄弟：双亲在同一层的销点互为堂兄弟 驱（双亲）结点，但可有多个直接后锤（子女）结 13有序树、无序树： 点， 若每结疯的各子树香成是从左到贿有次序（不能互换） √开始结点：根 的，则称为有序制，否则为无序刺。 终结点：叶其余结点为内部结点。 √粗先与子孙关系：是对父子关系的延拓，它定义了制树 ●，●●不可的有序制，一般讨论有序制 中结点的纵向关暴。 14森林：m(m>=0)棵互不相交的树的集合 横向关系：有序树定义了同一组兄弟间的从左到右的 树和森林非常接近：去树根=>森林 长幼关系，可将其延拓到结点间的横向次序：k,和k 森林加上一根=>树 是兄弟，k,在左，则k,的任一子孙在K的任一于孙的 左边。 86.2二叉树 s6.2.1二叉树的定义 是一种特殊的树型结构，每个结点至 多只有二棵子树，一般树可转换为二叉树， 形态 计算机用途甚广. 0 O 86.2.1二叉树的定义 (a) ■Def:二叉树是n(n>=0)个结点的有限集，它或者 8花含2变的汉 是空集，或由一个根结点及两棵互不相交的，分 ■与度为2的有序树区别： 别称作根的左子树和右子树的二叉树组成 当某一结点只有 当然为长子 点只有 孩子亦需分出其名 一程者试的有树 §6.2.2二叉树的性质 §6.2.2二叉树的性质 1.性质1：二叉树的第层上至多有21个结点 (伦1，根为第1层) 2性质2.深度为h的二叉树至多有2L1个 结点(h21). pf:归纳法 ①归纳盖础：1,21-1，第1层上只有根，放成立. P叶深度一定时，仅当每层上结点达到最大时，该 ②归纳假设：设所有的j(1≤jK)命题成立.即： 树结点最多。 第j层结点数≤2H 利用性质1知，深度为h的二叉树至多有： ①归纳步骤：j=时，第1-1层结点数≤22（由归纳 20+21+.+2t-1=2h.1 假设) 因为，每个结点至多有两个孩子. 所以，第i层上结点数≤2*21-2=2-1. 2
2014/4/7 2 §６.１树的概念 术语： 11 高（深）度：树中结点的最大层数 12 堂兄弟：双亲在同一层的结点互为堂兄弟 13 有序树、无序树： 若每结点的各子树看成是从左到右有次序（不能互换） 7 的，则称为有序树，否则为无序树。 不同的有序树，一般讨论有序树 14 森林：m (m>=0) 棵互不相交的树的集合 树和森林非常接近：删去树根 ＝＞ 森林 森林加上一根 ＝＞ 树 §６.１树的概念 逻辑特征： 父子关系（非线性关系）：任一结点至多有一直接前 驱（双亲）结点，但可有多个直接后继（子女）结 点． 开始结点：根 }其余结点为内部结点 8 终端结点：叶 祖先与子孙关系：是对父子关系的延拓，它定义了树 中结点的纵向关系． 横向关系：有序树定义了同一组兄弟间的从左到右的 长幼关系，可将其延拓到结点间的横向次序：k1和k2 是兄弟，k1在左，则k1的任一子孙在k2的任一子孙的 左边． }其余结点为内部结点． §６.２二叉树 是一种特殊的树型结构，每个结点至 多只有二棵子树，一般树可转换为二叉树， 计算机用途甚广． §６.２.１二叉树的定义 9 Ｄef: 二叉树是n(n>=0)个结点的有限集，它或者 是空集，或由一个根结点及两棵互不相交的，分 别称作根的左子树和右子树的二叉树组成 §６.２.1 二叉树的定义 形态 a (b) (c) (d) (e) A A A 10 与度为２的有序树区别： ( ) ( ) ( ) ( ) a b c d e 当某一结点只有一 孩子时，有序树中它理 所当然为长子，但二叉 树中，一个结点只有一 个孩子亦需分出其左 右． §６.２.2 二叉树的性质 1. 性质１：二叉树的第i层上至多有2i-1个结点 （i≥1，根为第1层） pf：归纳法 ① 归纳基础：i=1,2i-1=1,第1层上只有根，故成立． 11 ① 归纳基础：i 1,2 1,第1层上只有根，故成立． ② 归纳假设：设所有的j（1 ≤ j<i）命题成立．即： 第j层结点数≤２j-1 ① 归纳步骤：j=i时，第i-1层结点数≤ ２i-2(由归纳 假设) 因为，每个结点至多有两个孩子． 所以，第i层上结点数≤ ２＊２i-2=2i-1． §６.２.2 二叉树的性质 2. 性质２．深度为h的二叉树至多有２h-1个 结点（h≥1). Pf: 深度一定时，仅当每层上结点达到最大时，该 12 深度 定时，仅当每层 结点达到最大时，该 树结点最多． 利用性质1知，深度为h的二叉树至多有： 20+21+…+2h-1 = 2h-1
2014/47 §6.2.2二叉树的性质 §6.2.2二叉树的性质 3. 性质3，在任一二叉树T中，设叶子数为ng,度为 4. 满二叉树：深度为h的具有2n,1个结点的二叉 2的结点数为n2:则nn2t1 树称为满二叉树。 Pt设n,为度为1的结点总数，则结点总数n等于0度， 5完全二叉树：若一二叉树至多只有最下两层上 1度和2度结点数之和 结点的度数可小于2，且最下一层上的结点都 n=ng*n+nz∥二叉制 (6.1) 集中在该层最左边的若干位置，则称为完全二 另一方面，除根外，其余结点均是其双亲的孩子，树中： 叉树。 孩子结点总数=n1+2n2中n-1=n,+2n2 某结点无左孩子，则它必为叶子 n年n,+2n2+1 (6.2) 满二叉树是完全二叉树，但反之未必成立： 由6.1和6.2：nn2+1 86.2.2二叉树的性质 S6.2.3二叉树的存储结构 1. 顺序存储结构 6. 性质4.具有n个结点的完全二叉树高为lg小+1或 如何将结点线性化，使得在线性序列中的相互位置能 g(n+1) 反映出结点间的辑关系？ pt:树高为h,则前h-1层是高为h-1的满二叉树，结点总数 若对完全二叉制自上而下，每层自左到右给所有个结 =2h1.1. 点编号，就能到一个足以反映整个二叉树结构的线性序 .∴，2h-1.1<n≤2h-1(2h-1<nt1≤2∥第h厘上重少有-↑第点 ”光全二叉树除最 2h1≤n<2h 整数 下层外，各层都充 了结点 每层结 h-1s Ign h (h-1<Ig(n+1)sh) 恰为上层的2 :h-1和h是相邻的整数 .h-1=g(h=[g(n+1)]) 从一结点填号可 推出其双亲，左右 孩子，兄第结点和 86.2.3二叉树的存储结构 S623二叉树的存储结构 ■性质5.设完全二叉树中编号为的结点简称k(1≤ n,则有： :上述关系中，编号足以反 1)若1，则结点k为根，无双亲；若>1，则k,的双亲是妇 映结点间的逻辑关系 (2)若2i≤n,则k,的左孩子为k2i:否则k,无左孩子，即它必 :.可将n个结点存储在向量 为叶子。//因此，完全二叉制中编号i》Lw对的结点必为叶子： bt[0.n可中，其中： (3)若2i+1≤n,则k,的右孩子为k2,否则k,无右孩子： bt0]一不用，或存储n (④若i为奇数且大于1，则k,的左兄弟为k,否则k无左兄 bt1n)一存储编号为1至n的结点 弟： 1 14151617 (5)若i为数且小于n,则k1的右兄弟为k,否则k,无右兄 正明从略。 3
2014/4/7 3 §６.２.2 二叉树的性质 3. 性质３．在任一二叉树Ｔ中，设叶子数为n0，度为 ２的结点数为n2．则n0=n2+1. Pf: 设n1为度为１的结点总数，则结点总数n等于０度， １度和２度结点数之和 13 n = n0+n1+n2 // 二叉树 （６.１） 另一方面，除根外，其余结点均是其双亲的孩子，树中： 孩子结点总数 = n1+2n2 n-1 = n1+2n2 n = n1+2n2+1 （６.２） 由６.１和６.２：n0=n2+1 §６.２.2 二叉树的性质 4. 满二叉树：深度为h的具有２h-1个结点的二叉 树称为满二叉树． 5. 完全二叉树：若一二叉树至多只有最下两层上 结点的度数可小于２ 且最下一层上的结点都 14 结点的度数可小于２，且最下 层上的结点都 集中在该层最左边的若干位置，则称为完全二 叉树． 某结点无左孩子，则它必为叶子 满二叉树是完全二叉树，但反之未必成立． §６.２.2 二叉树的性质 6. 性质４．具有n个结点的完全二叉树高为 或 pf: ∵树高为h，则前h-1层是高为h-1的满二叉树，结点总数 = 2h-1-1. lg 1 n + lg( 1) n + 15 ∴ 2h-1-1 < n ≤ 2h-1 (2h-1 < n+1 ≤ 2h) // 第h层上至少有一个结点 2h-1 ≤ n < 2h //整数 h-1 ≤ lgn < h (h-1 < lg(n+1) ≤ h) ∵ h-1和h是相邻的整数 ∴ h-1 = (h = ) lg n lg( 1) n + §6.2.3 二叉树的存储结构 1. 顺序存储结构 如何将结点线性化，使得在线性序列中的相互位置能 反映出结点间的逻辑关系？ 若对完全二叉树自上而下，每层自左到右给所有n个结 点编号，就能到一个足以反映整个二叉树结构的线性序 列 16 ．∵ 完全二叉树除最 下层外，各层都充 满了结点，每层结 点数恰为上层的２ 倍． ∴ 从一结点编号可 推出其双亲，左右 孩子，兄弟结点和 编号． §6.2.3 二叉树的存储结构 i/2 k n/2 性质5. 设完全二叉树中编号为i的结点简称ki (1≤ i≤ n), 则有： (1) 若i=1，则结点ki为根，无双亲；若i>1，则ki的双亲是 (2) 若2i≤n,则ki的左孩子为k2i；否则ki无左孩子，即它必 为叶子。//因此，完全二叉树中编号i> 的结点必为叶子; ( ) 若 ≤ 则 的右孩子为 否则 无右孩子 17 (3) 若2i+1≤n,则ki的右孩子为k2i+1 ,否则ki无右孩子; (4) 若i为奇数且大于1，则ki的左兄弟为ki-1，否则ki无左兄 弟; (5) 若i为偶数且小于n，则ki的右兄弟为ki+1，否则ki无右兄 弟。 证明从略。 §6.2.3 二叉树的存储结构 i / 2 ∵ 上述关系中，编号足以反 映结点间的逻辑关系 ∴ 可将n个结点存储在向量 bt[0..n]中，其中： bt[0] —— 不用 或存储n 18 bt[0] —— 不用，或存储n bt[1..n] —— 存储编号为1至n的结点
2014/47 S6.2.3二叉树的存储结构 s6.2.3二叉树的存储结构 缺点 2. 链式存储结构 。结点结构 对一般的二叉树，须按完全二叉树的编号来存储， 浪费空间，最坏情况是右单支树，k个结点需1 child 个结点空间。 右孩子 01234567 (国二叉继表中等点 )带双亲的二义战表 M3ABC ·类型定义 typedef struct node 结论 DataType data; struct node"Ichild,"rchild; 藻桨捷钩只适用于存储完全二又树，且横入和 )BinTNode;∥结点类型 typedef BinTNode"BinTree;二叉树类型 86.2.3二叉树的存储结构 S6.3遍历二叉树 在二叉树中，所有类型为BinTNode的结点，加上一个指向 1概念 根的BinTree型头指针root,就构成了二叉树的链式存储结构，称 ·定义：沿某搜索路线，依次对制中每个结点均做一次且 之为二叉雏衰 仅做一次访问。 量然，二叉链表由根指针root唯一确定， 例子 重要性：是其它运算的盖础，很多树上绿作均依赖于速 历排作，只是访问结点所做的嫌作不同。 ·如何速历？ 遍历线性结构很容易：从开始结点出发，依次访问当前 结点的后继，直至终端特点为止。遍历路线只有一条 如单链表，从头指针开始)。 ■特性 (a)二 二叉链表 空制分root=NULL 但二叉树中每个结点可能有两个后纯，故遭历路线不唯 一，须找到适用于每个结点的相同的遍历规则。 叶子÷左右指针为空 空指针数：n个结点，共有2n个指针罐，但只有n-1个结点是别 人的孩子，故空指针数为+1 22 §6.3遍历二叉树 S6.3遍历二叉树 :在二叉树的递归定义中，非空树组成为： 2逾历算法 D,L、R 以中根为例，速历二叉定义为 在任一结点上，可按某种次序执行三个操作： 计二叉制非空hen( 访问根结点(D),遍历该结点的左子树亿)，遍历该结点的右 (遍历左子制即速历二又铜 子树(R) (2)访问根 1将1(2)和(2(3)对视后为先根和后根速历 显然有六种执行次 (3)遍历右子制即流历二复制】 }Ⅱ香测为空嫌作（递归结来条件 1从左到右： DLR,LDR,LRD二者对称，只讨论前3种 void Inorder(BinTree T(HT为三叉树的头指针 2.从右到左：DRL,RDL,RLD f(可{ⅡT非空，T为空时为空操作 速历规则（从左到右） Inorder(T->Ichild); 归速历左子 printi(""%c”,T->data:∥访间损鳍点，具体问厘，此 DLR,LDR,LRD的差别是访问根的先后次序不同 作不同 ①前序（先序，先根）遍历：DLR Inorder(T->rchild); ∥邀归德历右子例 ②中序（中根）遍历：LDR ③后序（后极）遍历：LRD 。时间：O(n
2014/4/7 4 §6.2.3 二叉树的存储结构 缺点 对一般的二叉树，须按完全二叉树的编号来存储， 浪费空间，最坏情况是右单支树，k个结点需2k-1 个结点空间。 19 结论 这种结构只适用于存储完全二叉树，且插入和删 除不便。 §6.2.3 二叉树的存储结构 2. 链式存储结构 结点结构 20 类型定义 typedef struct node { DataType data; struct node *lchild, *rchild; } BinTNode; // 结点类型 typedef BinTNode *BinTree; //二叉树类型 §6.2.3 二叉树的存储结构 在二叉树中，所有类型为BinTNode的结点，加上一个指向 根的BinTree型头指针root，就构成了二叉树的链式存储结构，称 之为二叉链表 显然，二叉链表由根指针root唯一确定。 例子 21 特性 空树 root = NULL 叶子 左右指针为空 空指针数：n个结点，共有2n个指针域，但只有n-1个结点是别 人的孩子，故空指针数为n+1 §6.3 遍历二叉树 1. 概念 定义：沿某搜索路线，依次对树中每个结点均做一次且 仅做一次访问。 重要性：是其它运算的基础，很多树上操作均依赖于遍 历操作，只是访问结点所做的操作不同。 如何遍历？ 22 遍历线性结构很容易：从开始结点出发，依次访问当前 结点的后继，直至终端结点为止。遍历路线只有一条 (如单链表，从头指针开始)。 但二叉树中每个结点可能有两个后继，故遍历路线不唯 一，须找到适用于每个结点的相同的遍历规则。 §6.3 遍历二叉树 ∵ 在二叉树的递归定义中，非空树组成为： D、L、R ∴ 在任一结点上，可按某种次序执行三个操作： 访问根结点(D)，遍历该结点的左子树(L),遍历该结点的右 子树(R) 显然有六种执行次序： lim ( )/ lim(2 3 2 1)/ 2 3 3 2 3 = + + + = →∞ →∞ T n n n n n n n n lim ( )/ lim(2 3 2 1)/ 2 3 3 2 3 = + + + = →∞ →∞ T n n n n n n n n 23 遍历规则(从左到右) DLR,LDR,LRD的差别是访问根的先后次序不同 ① 前序(先序，先根)遍历：DLR ② 中序(中根)遍历：LDR ③ 后序(后根)遍历：LRD 1 DLR LDR LRD 3 DRL RDL RLD .从左到右： ， ， 二者对称，只讨论前 种 2.从右到左： ， ， §6.3 遍历二叉树 2. 遍历算法 以中根为例，遍历二叉树定义为： if 二叉树非空 then { (1) 遍历左子树 // 即遍历二叉树 (2) 访问根 // 将(1)(2)和(2)(3)对调后为先根和后根遍历 (3) 遍历右子树 //即遍历二叉树 } // 否则为空操作 (递归结束条件) 24 void Inorder(BinTree T) { // T为二叉树的头指针 if (T) { // T非空，T为空时为空操作 Inorder(T->lchild); // 递归遍历左子树 printf(“%c”, T->data)；// 访问根结点，具体问题，此 // 操作不同 Inorder(T->rchild); // 递归遍历右子树 } } 时间：O(n)
201447 §6.3遍历二叉树 s6.3遍历二叉树 3. 遍历序列 4. 通用的遍历算法 包络线是递归遍历路线 因为访问钠点的操作依输于具体问厘，故可将它作为一个函敷指针边 向下：表示递归调用，更 数放于速历算法的◆敷表中，调用时，使其指向具体的访问结点的应用西 深一层 向上：表示递归结束，返 void Inorder(BinTree T,void ("Visit)(DataType x)){ 回一层 前序序列：ABDCEF 每个结点经过3次， Inorder(T->lchild,Visit); 中序序列：DBAECF线性序列 (Visit)(T->data); 第1次经过时访问所得结 后序序列：DBEFCA Inorder(T>rchild,Visit); 点序列为前序，第2次经 1个开始结点，1个锋端结点，其余结点均 过时访问所得结点序列为 有一个童接前驱和一个直接后蛙，为区别 中序，第3次经过时访问 3种次序在前窗冠以前序 其中Vst是一西数指针，它指向形物void f(DataTyp9x)的函数，故 中序 所得结点序列为后序。 后序 【后维 可将访问销点的操作写在函仲，通过调用语句： Inorder(root,f); ▲叶子的相对次序相同 将的地址传给Vst。 §63遍历二叉树 S6.3遍历二叉树 4通用的遍历算法 5. 建立二叉链表 上述算法假定二叉链表已建立 例如，可将打印操作为 建立二叉树对应的二叉链表方法很多 void print(DataType x){ 先序遍历构造法 输入先序序列，加入应结点物入时用空格符“”) print(%c”,x: 以示空指针的位置，例如前述的二叉制，输入为： ABD中中ΦCEΦ中FΦ中 调用引Inorder(root,print),即可完成前述算法。 ▲函数名：函数代码的起址。 s6.3遍历二叉树 S6.4线索二叉树 void CreateBinTree(BinTree*T(∥注意T为指针的指针 1. 基本概念 char ch; if(eh=getchar0(=n)return;∥回车结桌输入 在一基本数据结构上常常常要扩充，增加辅助信息，其目的是： f(ch=')∥读入空格 ①开发新操作：②加速已有操作。 T=NULL:I将相应的指针置空 锐家一利用空指针(+1个存放指肉点在某种速历次序下的 ese{∥峡入的是结点数播 前厘和后维指针 *T=(BinTNode*)malloc(sizeof(BinTNode)); 线索链表—加上绒寒的二叉链表 (T->data=ch;∥生成新结点，相当于访向根节点 处常二叉树一一相应的二又制称为线家二又制 CreateBinTree(&(T>Ichild;I速历左子侧 目的：加速速历操作 CreateBinTree(&(rT->rchild):l施历右子制 加速查找任一结点在某种速历次序下的前驱和后镶操作 。如何区别结点的指针城 孩子常针：指向孩子？ 建制时调用CreateBinTree(&root),将root(BinTree类型)的 镜索指针：指向其莱种速历次序下的前里和后蛙的战索？ 地址复制给T,故修改T就相当于修改了实◆root本身。 时间：O(n 30
2014/4/7 5 §6.3 遍历二叉树 前序序列：AB CD EF 3. 遍历序列 包络线是递归遍历路线 向下：表示递归调用，更 深一层 向上：表示递归结束，返 回一层 25 D EF BA C D EF B CA 前序序列： 中序序列: 线性序列： 后序序列: 每个结点经过3次， 第1次经过时访问所得结 点序列为前序，第2次经 过时访问所得结点序列为 中序，第3次经过时访问 所得结点序列为后序。 1个开始结点，1个终端结点，其余结点均 有一个直接前驱和一个直接后继，为区别 3种次序在前面冠以 前序 前驱 中序 + 后继 后序 ▲ 叶子的相对次序相同 §6.3 遍历二叉树 4. 通用的遍历算法 因为访问结点的操作依赖于具体问题，故可将它作为一个函数指针参 数放于遍历算法的参数表中，调用时，使其指向具体的访问结点的应用函 数 void Inorder( BinTree T, void (*Visit)(DataType x) ) { if (T) { Inorder(T->lchild Visit); 26 >lchild, Visit); (*Visit)(T->data); Inorder(T->rchild, Visit); } } 其中Visit是一函数指针，它指向形如void f(DataType x)的函数，故 可将访问结点的操作写在函数f中，通过调用语句： Inorder(root, f); 将f的地址传给Visit。 §6.3 遍历二叉树 4. 通用的遍历算法 例如，可将打印操作为 void print(DataType x) { print(“%c”, x); } 27 调用Inorder(root, print)，即可完成前述算法。 ▲ 函数名：函数代码的起址。 §6.3 遍历二叉树 5. 建立二叉链表 上述算法假定二叉链表已建立 建立二叉树对应的二叉链表方法很多 先序遍历构造法 输入先序序列，加入虚结点(输入时用空格符“ ”) 以示空指针的位置，例如前述的二叉树，输入为： ABDФФФCEФФFФФ 28 ABDФФФCEФФFФФ §6.3 遍历二叉树 void CreateBinTree(BinTree *T) { // 注意T为指针的指针 char ch; if ((ch = getchar()) == ‘\n’) return; // 回车结束输入 if (ch == ‘ ’) // 读入空格 *T = NULL； // 将相应的指针置空 else { // 读入的是结点数据 *T = (BinTNode*) malloc(sizeof(BinTNode)); 29 ( ) ( ( )); (*T)->data = ch; // 生成新结点，相当于访问根节点 CreateBinTree(&(*T)->lchild); // 遍历左子树 CreateBinTree(&(*T)->rchild); // 遍历右子树 } } 建树时调用 CreateBinTree(&root), 将root(BinTree类型)的 地址复制给T，故修改*T就相当于修改了实参root本身。 时间：O(n) §6.4 线索二叉树 1. 基本概念 在一基本数据结构上常常需要扩充，增加辅助信息，其目的是： ①开发新操作；②加速已有操作。 线索 —— 利用空指针域(n+1个)存放指向结点在某种遍历次序下的 前驱和后继指针 线索链表 —— 加上线索的二叉链表 30 线索二叉树 —— 相应的二叉树称为线索二叉树 目的：加速遍历操作 加速查找任一结点在某种遍历次序下的前驱和后继操作 如何区别结点的指针域 孩子指针：指向孩子？ 线索指针：指向其某种遍历次序下的前驱和后继的线索？