chapter06树和二叉树.ppt

6.1 树树6.1.1 树的定义树的定义（1）定义）定义 树树（Tree）：是）：是n（n0）个结点的有限集。）个结点的有限集。 定义一：（递归定义）：定义一：（递归定义）： 在任意一棵非空树中，有且仅有一个特定的称为根（在任意一棵非空树中，有且仅有一个特定的称为根（root） 的结点；的结点； 当当n1时，其余结点可分为时，其余结点可分为m（m0）个互不相交的有限集）个互不相交的有限集 T1, T2, , Tm，其中每一个集合本身又是一棵树。并且，其中每一个集合本身又是一棵树。并且 T1, T2, , Tm，称为根的子树（，称为根的子树（SubTree）。）。 定义二：（形式定义）定义二：（形式定义）任何一棵树是一个二元组任何一棵树是一个二元组Tree = (root, F)。 其中：其中：root是数据元素，称做树的根结点；是数据元素，称做树的根结点；F是是m（m0）棵树的森林，）棵树的森林， F（T1, T2, , Tm），其中），其中Ti = (ri, Fi)称做根称做根root的第的第i棵子树；当棵子树；当m0 时，在树根和其子树森林之间存在下列关系：时，在树根和其子树森林之间存在下列关系： RF = | i = 1, 2, ,m; m 0（2）表示形式）表示形式 该树有该树有13个结点。其中，个结点。其中，A是树根，其余结点分成是树根，其余结点分成3个互不相交的子集：个互不相交的子集：T1=B, E, F, K, L，T2=C, G，T3=D, H, I, J, M; T1、T2和和T3都是都是A的子树，的子树，其本身也是一棵树。其本身也是一棵树。层次层次A 1B C D 2E F G H I J 3K L M 4 图图6.1一般的树一般的树该树又可表示为如下三种形式：该树又可表示为如下三种形式：(a) 嵌套集合表示嵌套集合表示 (c) 凹入表示法凹入表示法 (A(B(E(K, L), F), C(G), D(H(M), I, J) (b) 广义表表示广义表表示 ABCDEFGHIJKLMABCDEFGHIJKLM图图6.2树的其他树的其他3种表示法种表示法 （3）树的抽象数据类型定义）树的抽象数据类型定义 ADT Tree数据对象数据对象D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系数据关系R：若：若D为空集，则称为空树；为空集，则称为空树； 若若D仅含一个数据元素，则仅含一个数据元素，则R为空集，否则为空集，否则R=H,H是如下二元关系：是如下二元关系： （1）在）在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root，它在关系，它在关系H下无前驱；下无前驱； （2）若）若Droot，则存在，则存在Droot的一个划分的一个划分D1,D2,Dm(m0), 对任意对任意jk(1j,km)有有DjDk，且对任意的，且对任意的i(1im)，唯，唯 一存在数据元素一存在数据元素xiDi，有，有H； （3）对应于）对应于Droot的划分，的划分，H, , 有唯一有唯一 的一个划分的一个划分H1, H2, , Hm(m0)，对任意，对任意jk (1j,km)有有 HjHk，且对任意，且对任意i(1im)，Hi是是Di上的二元关系，上的二元关系， (Di, Hi)是一棵符合本定义的树，称为根是一棵符合本定义的树，称为根root的子树。的子树。基本操作：基本操作： InitTree (&T); 操作结果：构造空树操作结果：构造空树T。 DestroyTree (&T);初始条件：树初始条件：树T存在。存在。操作结果：销毁树操作结果：销毁树T。 CreateTree (&T, definition);初始条件：初始条件：definition给出树给出树T的定义。的定义。操作结果：按操作结果：按definition构造树构造树T。 ClearTree (&T);初始条件：树初始条件：树T存在。存在。操作结果：将树操作结果：将树T清为空树。清为空树。 TreeEmpty(T);初始条件：树初始条件：树T存在。存在。操作结果：若操作结果：若T为空树，则返回为空树，则返回TRUE，否则返回，否则返回FALSE。 TreeDepth(T);初始条件：树初始条件：树T存在。存在。操作结果：返回操作结果：返回T的深度。的深度。 Root(T);初始条件：树初始条件：树T存在。存在。操作结果：返回操作结果：返回T的根。的根。 Value(T, cur_e);初始条件：树初始条件：树T存在，存在，cur_e是是T中某个结点。中某个结点。操作结果：返回操作结果：返回cur_e的值。的值。 Assign(T, cur_e, value);初始条件：树初始条件：树T存在，存在，cur_e是是T中某个结点。中某个结点。操作结果：结点操作结果：结点cur_e赋值为赋值为value。 Parent(T, cur_e);初始条件：树初始条件：树T存在，存在，cur_e是是T中某个结点。中某个结点。操作结果：若操作结果：若cur_e是是T的非根结点，则返回它的双亲，否则函数值为的非根结点，则返回它的双亲，否则函数值为“空空”。 LeftChild(T, cur_e);初始条件：树初始条件：树T存在，存在，cur_e是是T中某个结点。中某个结点。操作结果：若操作结果：若cur_e是是T的非叶子结点，则返回它的最左孩子，否则返回的非叶子结点，则返回它的最左孩子，否则返回“空空”。 RightSibling(T, cur_e);初始条件：树初始条件：树T存在，存在，cur_e是是T中某个结点。中某个结点。操作结果：若操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则函数值为有右兄弟，则返回它的右兄弟，否则函数值为“空空”。 InsertChild(&T, &P, i, c);初始条件：树初始条件：树T存在，存在，p指向指向T中某个结点，中某个结点，1ip所指结点的度所指结点的度1，非空非空 树树c与与T不相交。不相交。操作结果：插入操作结果：插入c为为T中中p指结点的第指结点的第i棵子树。棵子树。 DeleteChild(&T, &P, i);初始条件：树初始条件：树T存在，存在，p指向指向T中某个结点，中某个结点，1ip指结点的度。指结点的度。操作结果：删除操作结果：删除T中中p所指结点的第所指结点的第i棵子树。棵子树。 TraverseTree(T, visit();初始条件：树初始条件：树T存在，存在，visit是对结点操作的应用函数。是对结点操作的应用函数。操作结果：按某种次序对操作结果：按某种次序对T的每个结点调用函数的每个结点调用函数visit()一次且至多一次。一次且至多一次。 一旦一旦visit()失败，则操作失败。失败，则操作失败。ADT Tree6.1.2 基本术语基本术语 结点结点：包含一个数据元素及若干指向其子树的分支。在树的：包含一个数据元素及若干指向其子树的分支。在树的图形表示中为一个圆圈。图形表示中为一个圆圈。 结点的的度度（Degree）：结点拥有的子树树。）：结点拥有的子树树。 叶子叶子（或（或终端结点终端结点）（）（Leaf）：度为）：度为0的结点。即没有子树的结点。即没有子树的结点。的结点。分支结点分支结点（或（或非终端结点非终端结点）：度不为）：度不为0的结点。的结点。内部结点内部结点：除根结点之外的分支结点。：除根结点之外的分支结点。树的的度度：树内各结点的度的最大值。：树内各结点的度的最大值。孩子孩子（Child）：结点的子树的根，称为该结点的孩子。）：结点的子树的根，称为该结点的孩子。 双亲双亲（Parent）：结点的子树的根，称为该结点的孩子，该）：结点的子树的根，称为该结点的孩子，该结点称为孩子的双亲。结点称为孩子的双亲。兄弟兄弟（Sibling）：同一个双亲的孩子之间互称为兄弟。）：同一个双亲的孩子之间互称为兄弟。子孙子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。：以某结点为根的子树中的任一结点都称为该结点的子孙。祖先祖先：从根到某结点所经分支上的所有结点，称为该结点的祖先。：从根到某结点所经分支上的所有结点，称为该结点的祖先。 森林森林（Forest）：是）：是m（m0）棵互不相交的树的集合。对树中）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。每个结点而言，其子树的集合即为森林。 层次层次（Level）：从根开始定义起，根为第一层，根的孩子为第二）：从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第层。若某结点在第k层，则其子树的根就在第层，则其子树的根就在第k1层。层。堂兄弟堂兄弟：其双亲在同一层的结点互为堂兄弟。：其双亲在同一层的结点互为堂兄弟。深度深度（高度高度）（）（Depth）：树中结点的最大层次。）：树中结点的最大层次。 有序树有序树：若将树中结点的各子树看成从左至右是有次序的（即不能：若将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。树的根称为第一个孩子，最右边的称为最后一个孩子。6.2 二叉树二叉树6.2.1 二叉树的定义二叉树的定义（1）定义）定义 二叉树二叉树（Binary Tree）：是另一种树型结构。）：是另一种树型结构。 特点：特点：每个结点至多只有两棵子树（即二叉树中不存在度大于每个结点至多只有两棵子树（即二叉树中不存在度大于2 的结点）。的结点）。 子树有左右之分，其次序不能任意颠倒。子树有左右之分，其次序不能任意颠倒。（2）图形表示）图形表示 (a) (b) (c) (d) (e)图图6.3二叉树的二叉树的5种基本形态种基本形态(a) 空二叉树空二叉树(b) 仅有根结点的二叉树仅有根结点的二叉树(c) 右子树为空的二叉树右子树为空的二叉树(d) 左、右子树均非空的二叉树左、右子树均非空的二叉树(e) 左子树为空的二叉树左子树为空的二叉树（3）二叉树的抽象数据类型定义）二叉树的抽象数据类型定义 H，且存在，且存在Dl上的关系上的关系Hr H；H = , , Hl, Hr； （4）(Dl, Hl)是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树，称为根的左子树，(Dr, Hr) 是一棵符合本定义的二叉树，称为根的右子树。是一棵符合本定义的二叉树，称为根的右子树。基本操作：基本操作： ADT BinaryTree数据对象数据对象D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系数据关系R： 若若D = ，则，则R =，称称BinaryTree为空二叉树；为空二叉树； 若若D，则，则R=H,H是如下二元关系：是如下二元关系： （1）在）在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root，它在关系，它在关系H下无前驱；下无前驱； （2）若）若Droot，则存在，则存在Droot = Dl, Dr，Dl且且Dm =； （3）若）若Dl，则，则Dl中存在唯一的元素中存在唯一的元素x1，有有H，且存在，且存在Dl 上的关系上的关系Hl H;若若 Dr,则则Dr中存在唯一的元素中存在唯一的元素xr, ,有有 InitBiTree (&T);操作结果：构造空二叉树操作结果：构造空二叉树T。 DestroyBiTree (&T);初始条件：二叉树初始条件：二叉树T存在。存在。操作结果：销毁二叉树操作结果：销毁二叉树T。 CreateBiTree (&T, definition);初始条件：初始条件：definition给出二叉树给出二叉树T的定义。的定义。操作结果：按操作结果：按definition构造二叉树构造二叉树T。 ClearBiTree (&T);初始条件：二叉树初始条件：二叉树T存在。存在。操作结果：将二叉树操作结果：将二叉树T清为空树。清为空树。 BiTreeEmpty(T);初始条件：二叉树初始条件：二叉树T存在。存在。操作结果：若操作结果：若T为空二叉树，则返回为空二叉树，则返回TRUE，否则返回，否则返回FALSE。 BiTreeDepth(T);初始条件：二叉树初始条件：二叉树T存在。存在。操作结果：返回操作结果：返回T的深度。的深度。 Root(T);初始条件：二叉树初始条件：二叉树T存在。存在。操作结果：返回操作结果：返回T的根。的根。 Value(T, e);初始条件：二叉树初始条件：二叉树T存在，存在， e是是T中某个结点。中某个结点。操作结果：返回操作结果：返回e的值。的值。 Assign(T, &e, value);初始条件：二叉树初始条件：二叉树T存在，存在， e是是T中某个结点。中某个结点。操作结果：结点操作结果：结点e赋值为赋值为value。 Parent(T, e);初始条件：二叉树初始条件：二叉树T存在，存在， e是是T中某个结点。中某个结点。操作结果：若操作结果：若e是是T的非根结点，则返回它的双亲，否则函数值为的非根结点，则返回它的双亲，否则函数值为“空空”。 LeftChild(T, e);初始条件：二叉树初始条件：二叉树T存在，存在， e是是T中某个结点。中某个结点。操作结果：返回操作结果：返回e的左孩子。若的左孩子。若e无左孩子，则返回无左孩子，则返回“空空”。 RightChild (T, e);初始条件：二叉树初始条件：二叉树T存在，存在， e是是T中某个结点。中某个结点。操作结果：返回操作结果：返回e的右孩子。若的右孩子。若e无右孩子，则返回无右孩子，则返回“空空”。 LeftSibling(T, e);初始条件：二叉树初始条件：二叉树T存在，存在， e是是T中某个结点。中某个结点。操作结果：返回操作结果：返回e的左兄弟。若的左兄弟。若e是是T的左孩子或无左兄弟，则返回的左孩子或无左兄弟，则返回“空空”。 RightSibling (T, e);初始条件：二叉树初始条件：二叉树T存在，存在， e是是T中某个结点。中某个结点。操作结果：返回操作结果：返回e的右兄弟。若的右兄弟。若e是是T的右孩子或无右兄弟，则返回的右孩子或无右兄弟，则返回“空空”。 InsertChild(T, P, LR, c);初始条件：二叉树初始条件：二叉树T存在，存在，p指向指向T中某个结点，中某个结点，LR为为0或或1，非空二叉，非空二叉 树树c与与T不相交且右子树为空。不相交且右子树为空。操作结果：根据操作结果：根据LR为为0或或1，插入，插入c为为T中中p指结点的左或右子树。指结点的左或右子树。p所指所指 结点的原有左或右子树则成为结点的原有左或右子树则成为c的右子树。的右子树。 DeleteChild(T, P, LR);初始条件：二叉树初始条件：二叉树T存在，存在，p指向指向T中某个结点，中某个结点，LR为为0或或1。操作结果：根据操作结果：根据LR为为0或或1，删除，删除T中中p所指结点的左或右子树。所指结点的左或右子树。 PreOrderTraverse (T, visit();初始条件：二叉树初始条件：二叉树T存在，存在，visit是对结点操作的应用函数。是对结点操作的应用函数。操作结果：先序遍历操作结果：先序遍历T，对每个结点调用函数，对每个结点调用函数visit()一次且仅一次。一次且仅一次。 一旦一旦visit()失败，则操作失败。失败，则操作失败。 InOrderTraverse (T, visit();初始条件：二叉树初始条件：二叉树T存在，存在，visit是对结点操作的应用函数。是对结点操作的应用函数。操作结果：中序遍历操作结果：中序遍历T，对每个结点调用函数，对每个结点调用函数visit()一次且仅一次。一次且仅一次。 一旦一旦visit()失败，则操作失败。失败，则操作失败。 PostOrderTraverse (T, visit();初始条件：二叉树初始条件：二叉树T存在，存在，visit是对结点操作的应用函数。是对结点操作的应用函数。操作结果：后序遍历操作结果：后序遍历T，对每个结点调用函数，对每个结点调用函数visit()一次且仅一次。一次且仅一次。 一旦一旦visit()失败，则操作失败。失败，则操作失败。 LevelOrderTraverse (T, visit();初始条件：二叉树初始条件：二叉树T存在，存在，visit是对结点操作的应用函数。是对结点操作的应用函数。操作结果：层序遍历操作结果：层序遍历T，对每个结点调用函数，对每个结点调用函数visit()一次且仅一次。一次且仅一次。 一旦一旦visit()失败，则操作失败。失败，则操作失败。ADT BinaryTree（4）特殊形态的二叉树）特殊形态的二叉树满二叉树满二叉树：一棵深度为：一棵深度为k且有且有2k1个结点的二叉树称为满二叉树。个结点的二叉树称为满二叉树。 特点：每一层上的结点数都是最大结点数。特点：每一层上的结点数都是最大结点数。 完全二叉树完全二叉树：深度为：深度为k的，有的，有n个结点的二叉树，当且仅当其每一个结点的二叉树，当且仅当其每一个结点都与深度为个结点都与深度为k的满二叉树中编号从的满二叉树中编号从1至至n的结点一一对应时，称的结点一一对应时，称之为完全二叉树。之为完全二叉树。特点：特点：叶子结点只可能在层次最大的两层上出现；叶子结点只可能在层次最大的两层上出现； 对任一结点，若其右分支下的子孙的最大层次为对任一结点，若其右分支下的子孙的最大层次为l， 则其左分支下的子孙的最大层次必为则其左分支下的子孙的最大层次必为l或或l1。8 9 10 11 12 13 14 15 12 34 5 6 7(a) 满二叉树满二叉树(b) 完全二叉树完全二叉树8 9 10 11 12 12 34 5 6 7图图6.4特殊形态的二叉树特殊形态的二叉树6 7 1 12 3 2 34 5 4 5 6(c) 非完全二叉树非完全二叉树 (d) 非完全二叉树非完全二叉树6.2.2 二叉树的性质二叉树的性质性质一：在二叉树的第性质一：在二叉树的第i层上至多有层上至多有2i-1个结点，个结点，(i1)。性质二：深度为性质二：深度为k的二叉树至多有的二叉树至多有2k1个结点，个结点，(k1)。性质三：对任何一棵二叉树性质三：对任何一棵二叉树T，如果其终端结点数为，如果其终端结点数为n0，度为，度为2的结的结 点数为点数为n2，则，则n0 = n2 + 1。性质四：具有性质四：具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 。1log2n）性质五：如果一棵有性质五：如果一棵有n个结点的完全二叉树（其深度为个结点的完全二叉树（其深度为的结点按层序编号的结点按层序编号(从第从第1层到第层到第 到右到右),则对任一结点则对任一结点i(1in),有有1log2n1log2n层，每层从左层，每层从左（1）如果）如果i1，则结点，则结点i是二叉树的根，无双亲；如果是二叉树的根，无双亲；如果i1， 则其双亲则其双亲PARENT(i)是结点是结点 。 2/ i（2）如果）如果2i n，则结点，则结点i无左孩子（结点无左孩子（结点i为叶子结点）；为叶子结点）； 否则其左孩子否则其左孩子LCHILD(i)是结点是结点2i。（3）如果）如果2i1 n，则结点，则结点i无右孩子；否则其右孩子无右孩子；否则其右孩子 RCHILD(i)是结点是结点2i1。6. 3 二叉树的存储结构二叉树的存储结构6.3.1 顺序存储结构顺序存储结构 /-二叉树的顺序存储表示二叉树的顺序存储表示-#defineMAX_TREE_SIZE100 /二叉树的最大结点数二叉树的最大结点数typedefTElemType SqBiTreeMAX_TREE_SIZE; /0号单元存储根结点号单元存储根结点SqBiTree bt; 用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为点元素，即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标的结点元素存储在如上定义的一维数组中下标为为i1的分量中。的分量中。 例如，图例如，图6.5所示为图所示为图6.4(b)所示完全二叉树和图所示完全二叉树和图6.4(c)所示二叉树的顺序存储所示二叉树的顺序存储结构。结构。 图图6.5二叉树的顺序存储结构二叉树的顺序存储结构1 2 3 4 5 6 7 8 9 10 11 121 2 3 4 5 0 0 0 0 6 7(a)完全二叉树完全二叉树(b)一般二叉树一般二叉树图中以图中以“0”表示表示不存在此不存在此结点结点结点结构结点结构 lchild data rchild其中，其中，data：数据域；：数据域； lchild：左指针域，指向该结点的左孩子；：左指针域，指向该结点的左孩子； rchild：右指针域，指向该结点的右孩子。：右指针域，指向该结点的右孩子。6.3.2 链序存储结构链序存储结构（1）二叉链表）二叉链表定义定义 二叉链表二叉链表：用上述结点结构所得二叉树的存储结构称之为二叉链表。：用上述结点结构所得二叉树的存储结构称之为二叉链表。图形表示图形表示 A AB BC CD DC D C DA AB BE F E F G G(a)单支树的二叉链表单支树的二叉链表 (b)二叉链表二叉链表图图6.7二叉链表存储结构二叉链表存储结构易知，在含有易知，在含有n个结点的二叉链个结点的二叉链表中有表中有n1个空链域。个空链域。typedef struct BiTNode TElemType data;struct BiTNode *lchild, *rchild;/左右孩子指针左右孩子指针 BiTNode, * BiTree二叉链表的存储表示二叉链表的存储表示Status CreateBiTree (BiTree &T);/按先后次序输入二叉树中结点的值（一个字符），空格字符表示空树，按先后次序输入二叉树中结点的值（一个字符），空格字符表示空树，/构造二叉链表表示的二叉树构造二叉链表表示的二叉树T。 Status PreOrderTraverse (BiTree T, Status ( * Visit )( TElemType e);/采用二叉链表存储结构，采用二叉链表存储结构，Visit是对结点操作的应用函数。是对结点操作的应用函数。/先序遍历先序遍历T，对每个结点调用函数，对每个结点调用函数Visit()一次且仅一次。一次且仅一次。/一旦一旦Visit()失败，则操作失败。失败，则操作失败。 Status InOrderTraverse (BiTree T, Status ( * Visit )( TElemType e);/采用二叉链表存储结构，采用二叉链表存储结构，Visit是对结点操作的应用函数。是对结点操作的应用函数。/中序遍历中序遍历T，对每个结点调用函数，对每个结点调用函数Visit()一次且仅一次。一次且仅一次。/一旦一旦Visit()失败，则操作失败。失败，则操作失败。/-基本操作的函数原型说明（部分）基本操作的函数原型说明（部分）-lchild data parent rchild Status PostreOrderTraverse (BiTree T, Status ( * Visit )( TElemType e);/采用二叉链表存储结构，采用二叉链表存储结构，Visit是对结点操作的应用函数。是对结点操作的应用函数。/后序遍历后序遍历T，对每个结点调用函数，对每个结点调用函数Visit()一次且仅一次。一次且仅一次。/一旦一旦Visit()失败，则操作失败。失败，则操作失败。 Status LevelOrderTraverse (BiTree T, Status ( * Visit )( TElemType e);/采用二叉链表存储结构，采用二叉链表存储结构，Visit是对结点操作的应用函数。是对结点操作的应用函数。/层序遍历层序遍历T，对每个结点调用函数，对每个结点调用函数Visit()一次且仅一次。一次且仅一次。/一旦一旦Visit()失败，则操作失败。失败，则操作失败。其中，其中，data：数据域；：数据域； lchild：左指针域，指向该结点的左孩子；：左指针域，指向该结点的左孩子； rchild：右指针域，指向该结点的右孩子；：右指针域，指向该结点的右孩子； parent：双亲指针域，指向该结点的双亲结点。：双亲指针域，指向该结点的双亲结点。（2）三叉链表）三叉链表结点结构结点结构定义定义 三叉链表三叉链表：用上述结点结构所得二叉树的存储结构称之为三叉链表：用上述结点结构所得二叉树的存储结构称之为三叉链表 图形表示图形表示图图6.8三叉链表存储结构三叉链表存储结构 A B C DE FGA B C DE FG6.4 二叉树的遍历与线索化二叉树的遍历与线索化6.4.1 二叉树的遍历二叉树的遍历 遍历二叉树遍历二叉树（traversing binary tree）：按某条搜索路径巡访树中的每）：按某条搜索路径巡访树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。个结点，使得每个结点均被访问一次，而且仅被访问一次。 例如，图例如，图6.9所示的二叉树表示下述表达式：所示的二叉树表示下述表达式：a + b * (cd)e / f。先序遍历：先序遍历：+ a * bc d / e f表达式的前缀表示（波兰式）表达式的前缀表示（波兰式）中序遍历：中序遍历：a + b * cde / f表达式的中缀表示表达式的中缀表示后序遍历：后序遍历：a b c d* + e f /表达式的后缀表示（逆波兰式）表达式的后缀表示（逆波兰式）层序遍历：层序遍历：+ / a * e f bcd图图6.9( a + b * (cd)e / f )表达式的二叉树表达式的二叉树- + / a * e fb -c d（1）递归算法）递归算法先序遍历先序遍历二叉树的操作定义为：二叉树的操作定义为：若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则访问根结点；访问根结点；先序遍历左子树；先序遍历左子树；先序遍历右子树。先序遍历右子树。中序遍历中序遍历二叉树的操作定义为：二叉树的操作定义为：若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则中序遍历左子树；中序遍历左子树； 访问根结点；访问根结点；中序遍历右子树。中序遍历右子树。后序遍历后序遍历二叉树的操作定义为：二叉树的操作定义为：若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则后序遍历左子树；后序遍历左子树； 后序遍历右子树；后序遍历右子树；访问根结点。访问根结点。层序遍历层序遍历二叉树的操作定义为：二叉树的操作定义为：若二叉树为空，则空操作；否则若二叉树为空，则空操作；否则按从上到下，从左到右的次序访问各结点。按从上到下，从左到右的次序访问各结点。Status PreOrderTraverse (BiTree T, Status ( * Visit )( TElemType e) /采用二叉链表存储结构，采用二叉链表存储结构，visit是对数据元素操作的应用函数。是对数据元素操作的应用函数。/先序遍历二叉树先序遍历二叉树T的递归算法，对每个数据元素调用函数的递归算法，对每个数据元素调用函数Visit。/最简单的最简单的Visit函数是：函数是：/Status PrintElement (TElemType e) /输出元素输出元素e的值的值/printf ( e );/实用时，加上格式串实用时，加上格式串/return OK;/调用实例：调用实例：PreOrderTraverse (T, PrintElement);if (T) if (Visit (Tdata) if (PreOrderTraverse (Tlchild, Visit)if (PreOrderTraverse (Trchild, Visit) return OK;return ERROR;elsereturn OK; / PreOrderTraverse若定义二叉树的存储结构为二叉链表，则有先序遍历二叉树的递归算法若定义二叉树的存储结构为二叉链表，则有先序遍历二叉树的递归算法6.1如下：如下：（2）非递归算法）非递归算法以中序遍历为例说明二叉树遍历的非递归算法。以中序遍历为例说明二叉树遍历的非递归算法。 仿照递归算法执行过程中递归工作栈的状态变化状况可直接写成相应仿照递归算法执行过程中递归工作栈的状态变化状况可直接写成相应的非递归算法：的非递归算法：工作记录中包含两项，其一是递归调用的语句编号，其二是指向根工作记录中包含两项，其一是递归调用的语句编号，其二是指向根 结点的指针，则当栈顶记录中的指针非空时，应遍历左子树，即指结点的指针，则当栈顶记录中的指针非空时，应遍历左子树，即指 向左子树树根的指针进栈；向左子树树根的指针进栈； 若栈顶记录中的指针值为空，则应退至上一层，若是从左子树返回若栈顶记录中的指针值为空，则应退至上一层，若是从左子树返回, 则应访问当前层即栈顶记录中指针所指的根结点；则应访问当前层即栈顶记录中指针所指的根结点；若是从右子树返回，则表明当前层的遍历结束，应继续退栈。若是从右子树返回，则表明当前层的遍历结束，应继续退栈。由上述分析可得两个中序遍历二叉树的非递归算法如下所示：由上述分析可得两个中序遍历二叉树的非递归算法如下所示：算法算法6.2如下：如下： Status InOrderTraverse (BiTree T, Status ( * Visit )( TElemType e) /采用二叉链表存储结构，采用二叉链表存储结构，visit是对数据元素操作的应用函数。是对数据元素操作的应用函数。/中序遍历二叉树中序遍历二叉树T的非递归算法，对每个数据元素调用函数的非递归算法，对每个数据元素调用函数Visit。InitStack (S);Push (S, T);/根指针进栈根指针进栈while (!StackEmpty (S) ) while (GetTop(S, p) & & p)Push (S, plchild);/向左走到尽头向左走到尽头Pop (S, p);if (!StackEmpty (S) ) /访问结点，向右一步访问结点，向右一步Pop (S, p);if (!Visit (pdata) )return ERROR;Push (S, prchild); / if / whilereturn OK; / InOrderTraverse算法算法6.3如下：如下： Status InOrderTraverse (BiTree T, Status ( * Visit )( TElemType e) /采用二叉链表存储结构，采用二叉链表存储结构，visit是对数据元素操作的应用函数。是对数据元素操作的应用函数。/中序遍历二叉树中序遍历二叉树T的非递归算法，对每个数据元素调用函数的非递归算法，对每个数据元素调用函数Visit。InitStack (S);P = T;while (p | |!StackEmpty (S) ) if (p) /根指针进栈，遍历左子树根指针进栈，遍历左子树Push (S, p);p = plchild; / ifelse /根指针退栈，访问根结点，遍历右子树根指针退栈，访问根结点，遍历右子树Pop (S, p);if (!Visit (pdata) )return ERROR;p = prchild); / else / whilereturn OK; / InOrderTraverse（3）二叉树的建立）二叉树的建立算法算法6.4是一个按先序序列建立二叉树的二叉链表的过程。是一个按先序序列建立二叉树的二叉链表的过程。 算法算法6.4如下：如下： Status CreateBiTree (BiTree &T) /按先序次序输入二叉树中结点的值（一个字符），按先序次序输入二叉树中结点的值（一个字符），/空格字符表示空树，构造二叉链表表示的二叉树空格字符表示空树，构造二叉链表表示的二叉树T。scanf (&ch);if (ch = = )T = NULL; else if (!(T = (BiTNode *) malloc (sizeof (BiTNode) ) ) )exit (OVERFLOW);Tdata = ch;/生成根结点生成根结点CreateBiTree (Tlchild);/构造左子树构造左子树CreateBiTree (Trchild);/构造右子树构造右子树return OK; / CreateBiTree图图6.10 二叉树二叉树例如，对图例如，对图6.10所示二叉树，按下列次序顺序读入字符：所示二叉树，按下列次序顺序读入字符：A B C D E F G A B CD EG F6.4.2 二叉树的线索化二叉树的线索化 当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在任一序列（先序、中序或后序序列）中的前驱和后继信息，这种接得到结点在任一序列（先序、中序或后序序列）中的前驱和后继信息，这种信息只有在遍历的动态过程中才能得到。为了保存这种在遍历过程中得到的信信息只有在遍历的动态过程中才能得到。为了保存这种在遍历过程中得到的信息，我们利用二叉链表中的空链域（由于结点没有左子树或右子树），来存放息，我们利用二叉链表中的空链域（由于结点没有左子树或右子树），来存放结点的前驱和后继信息。结点的前驱和后继信息。作如下规定：作如下规定： 若结点有左子树，则其若结点有左子树，则其lchild域指示其左孩子，否则令域指示其左孩子，否则令lchild域指示其前驱；域指示其前驱； 若结点有右子树，则其若结点有右子树，则其rchild域指示其右孩子，否则令域指示其右孩子，否则令rchild域指示其后继。域指示其后继。 （1）线索链表的结点结构）线索链表的结点结构lchild LTag data RTag rchild其中：其中：data：数据域；：数据域； lchild：左指针域，指向该结点的左孩子；：左指针域，指向该结点的左孩子； rchild：右指针域，指向该结点的右孩子；：右指针域，指向该结点的右孩子； 0 lchild域指示结点的左孩子域指示结点的左孩子 LTag = 1 lchild域指示结点的前驱域指示结点的前驱 0 rchild域指示结点的右孩子域指示结点的右孩子 RTag = 1 rchild域指示结点的后继域指示结点的后继（2）线索链表的定义）线索链表的定义 线索链表线索链表：以上述结点结构构成的二叉链表作为二叉树的存储结构，称之：以上述结点结构构成的二叉链表作为二叉树的存储结构，称之为线索链表。为线索链表。（3）相关术语）相关术语线索化线索化：对二叉树以某种次序遍历使其变为线性二叉树的过程。：对二叉树以某种次序遍历使其变为线性二叉树的过程。线索二叉树线索二叉树（Threaded Binary Tree）：加上线索的二叉树。）：加上线索的二叉树。线索线索：在线索链表中指向结点前驱和后继的指针。：在线索链表中指向结点前驱和后继的指针。（4）图形表示）图形表示-+ /a * e fb -c d-+ /NIL NILa * e fb -c d(a) ( a + b * (cd)e / f )表达式的二叉树表达式的二叉树(b) 中序线索二叉树中序线索二叉树图图6.11线索二叉树及其存储结构线索二叉树及其存储结构thrt 0 1bt0 0 0 0 0 / 0 1 a 1 0 * 0 1 e 1 1 f 10 01 b 11 c 11 d 1(c) 中序线索链表中序线索链表图中，实线为指针（指向左、右子树），虚线为线索（指向前驱和后继）。图中，实线为指针（指向左、右子树），虚线为线索（指向前驱和后继）。（5）C语言