《算法与数据结构》第4章 树与二叉树ppt.ppt

算法与数据结构 第4章 树与二叉树 树和二叉树 n在前两章讨论的数据结构都属于线性结构。线性结构的逻 辑结构简单，易于实现各种运算和操作，主要用于描述客观 世界中具有单一前趋和单一后继的数据关系。 n然而，客观世界中的许多事物的关系并非如此简单，如人 类社会中的族谱、各种社会组织机构、交通道路和通讯网络 等，其中的联系都是较为复杂的非线性关系，宜用非线性结 构来描述其数据关系。 n树与二叉树中，每个数据元素至多只有一个前趋，但可以 有多个后继；数据元素间的关系是一对多的层次关系，主要 用于描述客观世界中具有层次结构的数据关系。 第4章 树与二叉树 4.1 树的基本概念 4.2 二叉树 4.3 二叉树的遍历 4.4 线索二叉树 4.5 树和森林 4.6 哈夫曼树 4.1 树的基本概念 4.1.1 树的定义及表示 4.1.2 树的常用术语及运算 树的定义及表示 n客观世界中的许多事物的关系可以用树来描述，如人类 社会中家族成员之间的血缘关系，以英国女王家族为例可 表示成如下图所示。 n上图看上去很像一棵倒置的树，树型结构便由此而得名 。 树的递归定义 n树（tree）是n（n0）个结点的有限集合T。 n当n=0时称为空树，否则称为非空树。 n在任一非空树中，有且仅有一个称为树的根的结点； 除根结点之外的其余结点可分为m（m0）个互不相 交的集合T1，T2，Tm，其中每个集合本身又都是一 棵树，并且称为根的子树。 n这是一个递归定义，即在树的定义中又用到了树 这个术语，它反映了树的固有特性： n即一棵树由若干棵子树构成，而每棵子树又都分别由若 干棵更小的子树构成。 树的递归定义（续） n这个树的递归定义可以从如下三点来理解： n没有任何结点的树称为空树，这是树的特例。 n非空树中至少有一个结点，只有一个结点时它就是树的 根，只有根结点的树称为最小非空树。 n在含有多个结点的树中，除根结点外其余结点构成若干 棵子树，且各子树间互不相交。 树的示例 n下图中，(a)是只有一个根结点的树。(b)是有六个 结点的一般树，其中A是根，其余结点分成三个互 不相交的子集：T1=B，T2=C，E，F，T3=D ；T1、T2和T3是A的子树，且其本身也都是一棵树 ；其中，T1的根为B其子树为空树，T3的根为D其子 树为空树，T2的根为C剩余结点分成两个互不相交 的子集T21=E和T22=F，T21和T22都是C的子树。 树的非递归定义 n树的非递归定义可以叙述为：称数据结构tree(D,R)为树， 则R中只有一个关系，且满足以下条件： (1) 有且仅有一个没有前趋的结点w，称为树的根； (2) 除根w外的每一个结点都有且只有一个前趋； (3) 对于除根w外的每一个结点K，都有一个从根w到k的一 个结点序列K0(w)，K1，K2，Ki-1，Ki，Kn(k)（n1 ），其中Ki是Ki-1的后继。 n这个非递归定义中的(1)和(2)容易理解；对于(3)以前一页的 图(b)中的任一结点如E说明一下，从根A到E存在一个线性序 列A、C、E，序列中后一个结点是它前面一个结点的后继， 即C是A的后继，E是C的后继。 树的表示 n通常树的表示方法有树形表示、嵌套集合表示、 凹入表示和广义表表示四种，如下图所示： 4.1 树的基本概念 4.1.1 树的定义及表示 4.1.2 树的常用术语及运算 树常用的基本术语 n树的结点：是指一个数据元素及其若干指向 其子树的分支，通常用一个记录或结构体来描 述，在树形表示中用一个圆圈及短线来表示。 n结点的度：是指结点拥有的子树数目。如右 图中，结点A的度为3，C的度为2，B、D、E、 F的度为0。 n叶子或终端结点：是指度为0的结点，如右图) 中的B、D、E、F都是叶子结点。 n分支结点或非终端结点：是指度不为0的结点 ，如右图中的A和C结点；通常又把非根的分支 结点称为内部结点，如右图中的C结点。 n树的度：是指树中各结点度的最大值，如右 图中的树的度为3。 树常用的基本术语（续） n结点的层次：从根结点开始，根为第一层 ，根的孩子为第二层，依次类推。如右上图 中的A在第一层，B、C、D在第二层，E和F 在第三层。 n树的深度或高度：是树中结点的最大层次 数。如右上图中的树高度为3。 n有序树和无序树：如果将树中结点的各子 树看成是从左到右依次有序且不能交换，则 称该树为有序树，否则称为无序树。如右下 图给出了两棵不同的有序树。 n森林：是m棵互不相交的树的集合。删除一 棵树的根就会得到由子树构成的森林；反之 ，给森林加上一个根就会变成为一棵树。 树的其它术语 n有时也引用家族树中的一些习惯用语，如 孩子、双亲、祖先、子孙、兄弟等。如称结 点的子树的根为该结点的孩子，该结点称为 孩子的双亲； n同一个双亲的孩子之间互称为兄弟；从结 点向上到达根结点所途经的所有结点称为该 结点的祖先，从结点向下所能到达的所有结 点称为该结点的子孙。如右图中，A是B、C 和D的双亲，B、C和D都是A的孩子，B、C 和D三者之间互为兄弟；A和C是E的祖先，A 的子孙是B、C、D、E和F。 树的基本运算 nsetnull(T)：置T为空树，即初始化一棵树T。 nroot(T)或root(x)：求根函数。求树T的根或求结点x所在树 的根结点，若T为空树或x不在树T中，则函数值为NULL。 nparent(T，x)：求双亲函数。求树T中结点x的双亲结点，若 x是树T的根结点或x不在树T中，则函数值为NULL。 nchild(T，x，i)：求孩子函数。求树T中结点x的第i个孩子 结点，若结点x无第i个孩子则函数值为NULL。 ncreate(x，F)：建树函数。生成一棵以x为根结点，以森林F 为子树森林的树。 nrsibling(T，x)：求右兄弟函数。求树T中结点x的右边兄弟 ，若x是其双亲的最右孩子或x不在T中，则函数值为NULL。 树的基本运算（续） naddchild(y，i，x)：插入子树操作。把以结点x为根的树 置为结点y的第i棵子树。若树中无结点y或它的子树个数小于 i-1，则为空操作。 ndelchild(x，i)：删除子树操作。删除结点x的第i棵子树 ，若无结点x或x的子树个数小于i，则为空操作。 ntraverse(T)：遍历操作。按某个次序依次访问树中各个结 点，并使每个结点只被访问一次。也就是说，遍历操作的结 果是对非线性结构树中各结点，按某个次序给出一个线性化 的结点序列。 第4章 树与二叉树 4.1 树的基本概念 4.2 二叉树 4.3 二叉树的遍历 4.4 线索二叉树 4.5 树和森林 4.6 哈夫曼树 4.2 二叉树 4.2.1 二叉树的概念 4.2.2 二叉树的性质 4.2.3 二叉树的存储结构 4.2.4 二叉树的简单运算实现 二叉树的概念 n二叉树是另一种重要的树型结构。它的特点是每个 结点至多有两棵子树，即二叉树中任何结点的度不 得大于2。 n二叉树的定义： 二叉树（binary tree）是n（n0）个结点的有限 集合，它或者（n=0时）为空树，或者（n0时）由 一个根结点及两棵互不相交的分别称为根的左子树 和右子树的二叉树组成。 二叉树的概念（续） n由定义显见二叉树的递归性质。 n应该指出的是，二叉树与树是两个不同的概念，它 不是树的特殊情况；这是因为二叉树的子树有左右 之分，而树的子树不必区分次序。 n另外二叉树与度为2的有序树也是不同的概念；因 为对于二叉树的子树而言，要么是根的左子树，要 么是根的右子树，即使只有一棵子树也要区分是左 是右；而度为2的有序树中，当一个结点有两棵子树 时有左右之分，而只有一棵子树时就无左右之分。 二叉树与度为2的普通树的区别举例 n在下图中，(a)和(b)所示的两棵二叉树虽然与(c)所 示的普通树相似，但却不等同于这棵普通树。 二叉树的五种基本形态 n二叉树可以是空树，根也可以有空的左子树、空的 右子树或左右子树均为空，因此二叉树有五种基本 形态，如下图所示： 二叉树的基本运算 n树的术语对于二叉树都适用。 n与树的基本运算类似，二叉树也有如下的一些基本 运算： n求二叉树的根root(bt)； n求二叉树中结点x的双亲parent(bt,x)； n求二叉树中结点x的左孩子或右孩子lchild(bt,x)和 rchild(bt,x)； n设置空二叉树setnull(bt)； n建立以x为根，以二叉树lbt和rbt为左右子树的一 棵二叉树create(x,lbt,rbt)； 二叉树的基本运算（续） n置以y为根的二叉树为结点x的左子树或右子树 addlchild(bt,x,y)和addrchild(bt,x,y)； n删除结点x的左子树或右子树dellchild(bt,x)和 delrchild(bt,x)； n在二叉树中查找结点x的运算search(bt,x)； n按照某种次序遍历二叉树中的所有结点 traverse(bt)。 4.2 二叉树 4.2.1 二叉树的概念 4.2.2 二叉树的性质 4.2.3 二叉树的存储结构 4.2.4 二叉树的简单运算实现 二叉树的性质 n 二叉树具有一些重要性质。 n 性质1 二叉树的第i（i1）层上至多有2i-1个结点。 n 证明：用数学归纳法证明如下： n当i=1时只有一个结点，2i-1=20=1，命题成立。 n设对于任意的j，1ji时命题成立，即第j层上至 多含有2j-1个结点。 n则由归纳假设第i-1层上至多含有2i-2个结点。由于 二叉树中每个结点至多有两个孩子，故第i层上的 最大结点数应为第i-1层上最大结点数的二倍，即 2*2i-2=2i-1成立，故命题成立。 二叉树的性质（续） n性质2 深度为k的二叉树至多有2k-1个结点（k1） 。 n证明：深度为k的二叉树最多含有的结点数应是每层含有 的最多结点数之和，由性质1应为20+21+2k-1=2k-1。 n性质3 对任意一棵二叉树，若终端结点数为n，度为 2的结点数为n2，则n0=n2+1。 n证明：设二叉树中度为1的结点数为n1，二叉树中总的结点 数为n，则有 n=n0+n1+n2 再考虑孩子结点，除根结点之外的结点都是一个结点的孩子 ，二叉树中孩子结点总数为n-1；而度为1的结点有一个孩 子，度为2的结点有两个孩子，因此二叉树中孩子结点的 总数又为n1+2n2，即 n-1=n1+2n2 联立以上二等式可得n0=n2+1，原命题得证。 二叉树的特殊形态满二叉树 n满二叉树（full binary tree）是指深度为k且有2k-1 个结点的二叉树。 n下图给出了深度为3的满二叉树。显然，满二叉树 的每层含有结点数为最大值，不存在度为1的结点， 除叶子结点外每个结点都有左右孩子，且叶子结点 全部在第k层上。 二叉树的特殊形态完全二叉树 n完全二叉树（complete binary tree）是指深度为k的、有 n个结点的二叉树，当且仅当它的每一个结点都与深度为k的 满二叉树中编号从1到n的结点一一对应。下图给出了一棵深 度为3的完全二叉树示例。 n显然，完全二叉树中前k-1层含有结点数为最大值，第k层 不一定满但全部集中在左边而空缺留在右边，叶子结点只可 能在第k层和第k-1层上出现。 n显而易见，满二叉树是完全二叉树的特殊情况，满二叉树 一定是完全二叉树，反之不然。 二叉树的性质（续） n 性质4 具有n 个结点的完全二叉树的深度为 。 n证明：设该完全二叉树的深度为k，由完全二叉树的 定义及性质2有2k-1-1n2k-1，即有 2k-1n2k 同时取对数后有 k-1log2nk 因为k为整数，故有 ，即 。 二叉树的性质（续） n性质5 对于具有n个结点的完全二叉树，如果按照自 上而下自左至右的顺序对所有结点从1到n编号，则对 于任意的序号为i的结点有： n如果i=1，则结点i是根结点，无双亲；如果i1，则结点i 的双亲结点编号为 。 n如果2in，则结点i的左孩子编号为2i；否则无左孩子。 n如果2i+1n，则结点i的右孩子编号为2i+1；否则无右孩 子。 n如果i为奇数且不为1，则结点i的左兄弟编号为i-1；否则无 左兄弟。 n如果i为偶数且小于n，则结点i的右兄弟编号为i+1；否则无 右兄弟。 4.2 二叉树 4.2.1 二叉树的概念 4.2.2 二叉树的性质 4.2.3 二叉树的存储结构 4.2.4 二叉树的简单运算实现 顺序存储结构 n二叉树的顺序存储是用一组连续的存储单元存储 二叉树中的数据元素。 n一般是按从根结点开始自上而下自左至右的顺序 来存储，然而按这种方法存储后结点在物理上的邻 接关系一般不能反映出它们在逻辑上的前趋和后继 关系。 n只有通过某种方法能够确定出结点之间的逻辑关 系，这种存储方法才有意义。 顺序存储结构（续） n由二叉树的性质5我们知道，完全二叉树以及它 的特殊形态满二叉树中的结点，可以由结点的序号 惟一确定结点之间的逻辑关系，如双亲、左孩子、 右孩子、左兄弟、右兄弟等关系； n所以可以采用一维数组a1n按结点编号依次 存储完全二叉树中各结点，这样既可用一维数组的 下标确定结点位置和结点之间的关系，又可节省存 储空间。 完全二叉树的顺序存储结构示意图 其中：a2的双亲是a1，左孩子是a4，右孩 子是a5，无左兄弟其右兄弟是a3。 一般二叉树的顺序存储结构 n对于一般的二叉树，如果仍按顺序存储依次存放 各结点于数组中，通过数组下标不能反映出结点之 间的逻辑关系；只有通过添加一些并不存在的空结 点，使之成为完全二叉树形式才行。 n显然，会造成许多存储空间的浪费，最坏情况下 是单右枝树，一棵深度为k的单右枝树，只有k个结 点却需分配2k-1个存储单元。 n所以，不宜用顺序存储结构存储一般的二叉树。 一般二叉树的顺序存储结构示意图 单右枝二叉树顺序存储结构示意图 链式存储结构 n二叉树的链式存储结构是指用链表来存储二叉树 ，用链指针来指示元素间的逻辑关系。 n常用的链式存储方法有双链法和三链法两种。 n所谓双链法即二叉链表表示法，它为每一个结点 设置两个指针域，分别指向该结点的左子树和右 子树；当无左子树或右子树时，其指针域值为 NULL（或）。其结点结构如下： n其中：data域存放结点的数据信息，lchild域存放指向 左孩子的指针，rchild域存放指向右孩子的指针。 二叉树的二叉链表表示示意图 二叉链表的类型定义 n显然，二叉链表表示法是存储二叉树的最自然的 方法，对于要经常做插入或删除运算的二叉树尤 为合适。 n二叉链表表示法的类型定义为 typedef struct btnode elemtype data; /*数据域*/ struct btnode *lchild,*rchild; /*左、右孩子域*/ bitnode; typedef bitnode *bitree; n二叉链表表示法便于从根往下查找，即便于查找 孩子或子孙。 二叉树的三叉链表表示 n若需要频繁查找双亲或祖先，二叉链表就不太方 便，需要由根结点开始向下查找，其效率较低。 n解决这一类问题的办法是采用三链法，即三叉链 表表示法，增加一个指针域用来指向双亲结点。 其结点结构如下： n其中：parent是存放指向双亲结点的指针域。 n三叉链表表示法既便于查找孩子结点，又便于查 找双亲结点，这种方便是以增加存储开销为代价 的。 二叉树的三叉链表表示示意图 4.2 二叉树 4.2.1 二叉树的概念 4.2.2 二叉树的性质 4.2.3 二叉树的存储结构 4.2.4 二叉树的简单运算实现 二叉树的基本运算实现 n二叉树基本运算的实现算法，依赖于具体的存储结 构；采用不同的存储结构，二叉树的基本运算实现的 算法是不同的。这里我们讨论的运算实现算法，是以 二叉链表为存储结构的。 n求二叉树中结点x的双亲、左孩子、右孩子以及查找 结点x的运算，都涉及要按照某种次序遍历二叉树中 所有结点，在遍历的过程中完成的运算和操作；由于 二叉树的遍历运算在下一节我们专门讨论，所以这些 运算我们穿插安排在下一节讨论。 n只讨论简化了的问题，即把一个结点插入到二叉树 中作为左右孩子或删除二叉树中左右孩子的算法。 1.设置空二叉树 n设置空二叉树setnull(bt) void setnull(bitree bt) /*设置一棵空二叉树，即置头结点的左右孩子链域为空*/ bt-lchild=NULL; /*左链域置空*/ bt-rchild=NULL; /*右链域置空*/ 2.求二叉树的根 n求二叉树的根root(bt) elemtype root(bitree bt) /*该运算返回二叉树根结点的值， 当二叉树为空树时返回NULL*/ if(bt-lchild=NULL) return NULL; else return bt-lchild-data; 3.建立二叉树操作 n建立二叉树操作create(x,lbt,rbt) bitree create(elemtype x,bitree lbt,bitree rbt) /*该运算生成一棵以x为根结点， lbt和rbt分别为左右子树的二叉树*/ bitree p; p=(bitree)malloc(sizeof(bitnode); p-data=x; p-lchild=lbt; p-rchild=rbt; return p; /*返回建成的二叉树*/ 4.插入左孩子 n插入左孩子addlchild(bt,x) void addlchild(bitree bt,elemtype x) /*把元素x插入到二叉树bt中成为它的左孩子 */ bitree p; p=(bitree)malloc(sizeof(bitnode) ); p-data=x; p-lchild=NULL; p-rchild=NULL; bt-lchild=p; /*插入bt的左孩子域 */ 5.删除左孩子 n删除左孩子dellchild(bt) void dellchild(bitree bt) /*删除二叉树bt的左孩子，整个左子树全部被删除 */ bitree p; p=bt-lchild; *保存左子树指针*/ bt-lchild=NULL; free (p); /*释放左子树空间*/ 第4章 树与二叉树 4.1 树的基本概念 4.2 二叉树 4.3 二叉树的遍历 4.4 线索二叉树 4.5 树和森林 4.6 哈夫曼树 4.3 二叉树的遍历 4.3.1 遍历二叉树的递归算法 4.3.2 遍历二叉村的非递归算法 4.3.3 遍历序列与二叉树的复原 4.3.4 基于遍历的几种二叉树运算的 实现和应用举例 二叉树的遍历 n二叉树的遍历是指按照某种次序巡访二叉树中的每 个结点，使得每个结点都被访问一次且只被访问一次 。遍历是二叉树中经常要用到的一种操作。在许多实 际应用问题中，常常需要查找具有某一特征的结点， 或者对二叉树中每个结点逐个访问，在访问的过程中 对某些结点或全部结点进行相应的处理。 n遍历对于线性结构来说是非常简单的，只需顺序扫 描每个数据元素一次即可。由于二叉树是一种非线性 结构，每个结点都有可能有两棵子树，这就需要寻找 一种规律，使二叉树中结点信息由非线性排列变成为 某种意义上的线性排列次序序列。 n所以我们可以说，遍历操作的实质就是使非线性结 构线性化。 二叉树的遍历（续） n由二叉树的定义分析二叉树的结构特征可知，一棵 非空的二叉树是由根结点（D）、左子树（L）和右子 树（R）三个基本部分组成的。 n只要依次遍历这三个部分，就可以遍历整个二叉树 ；而对这三个部分的遍历有六种可能的次序，即DLR 、DRL、LDR、RDL、LRD和RLD。 n如果限定先左后右则只有三种情况，即DLR、LDR和 LRD三种，分别称为前序遍历、中序遍历和后序遍历 。 1.前序遍历 n前序遍历（preorder traversal） n前序遍历二叉树的递归定义为：若二叉树为空树则 遍历结束，否则 n访问根结点； n前序遍历根结点的左子树； n前序遍历根结点的右子树； n例如对下图的二叉树，前序遍历得到的结点序列为 ABDFCEG。 前序遍历的递归算法描述 void preorder(bitree bt) if(bt=NULL) return ; /*递归结束条件*/ else printf(“%dt”,bt-data); preorder(bt-lchild); /*前序遍历左子树*/ preorder(bt-rchild); /*前序遍历右子树*/ 2.中序遍历 n中序遍历（inorder traversal） n中序遍历二叉树的递归定义为：若二叉树为空树则 遍历结束，否则 n中序遍历根结点的左子树； n访问根结点； n中序遍历根结点的右子树； n例如对下图的二叉树，中序遍历得到的结点序列为 BFDAEGC。 中序遍历的递归算法描述 void inorder(bitree bt) if(bt=NULL) return ; /*递归结束条件*/ else inorder(bt-lchild); /*中序遍历左子树*/ printf(“%dt”,bt-data); /*访问根结点*/ inorder(bt-rchild); /*中序遍历右子树*/ 3.后序遍历 n后序遍历（postorder traversal） n后序遍历二叉树的递归定义为：若二叉树为空树则 遍历结束，否则 n后序遍历根结点的左子树； n后序遍历根结点的右子树； n访问根结点； n例如对下图的二叉树，后序遍历得到的结点序列为 FDBGECA。 后序遍历的递归算法描述 void postorder(bitree bt) if(bt=NULL) return ; /*递归结束条件*/ else postorder(bt-lchild); /*后序遍历左子树*/ postorder(bt-rchild); /*后序遍历右子树*/ printf(“%dt”,bt-data); /*访问根结点*/ 二叉树的遍历（续） n二叉树的前序、中序和后序三种次序遍历，都是从 根结点开始的，并且在遍历过程中所经过的结点路线 也是相同的，仅仅只是访问的时机不同而已。 n如左下图所示的二叉树，其三种遍历的巡访路线和 访问时机可示意如右下图所示。 二叉树的遍历举例 巡访路线 前序序列：- + a * b c / d e * *中序序列：a * + * b * * * c * - * d * / * e 后序序列：a b c * + d e/ 4.3 二叉树的遍历 4.3.1 遍历二叉树的递归算法 4.3.2 遍历二叉村的非递归算法 4.3.3 遍历序列与二叉树的复原 4.3.4 基于遍历的几种二叉树运算的 实现和应用举例 遍历二叉树的非递归算法 n递归算法简洁精练、可读性好、易理解，但其执行效率较低 ；另外，并非所有程序设计语言都提供递归的功能设施。所 以，我们有必要讨论遍历二叉树的非递归算法。 n我们注意观察前面给出的三种次序的巡访路线，它是从根结 点开始沿左子树深入直到最左下端时，返回进入刚刚遇到结 点的右子树； n在右子树中，也是先深入到它的最左下结点时返回刚遇到结 点的右子树，如此深入和返回，直到从根结点的右子 树返回到根结点时止。 n在这一过程中，返回结点的顺序恰与深入结点的顺序相反， 先深入的后返回，正好符合栈的特点。 n所以我们可以用栈来保存遍历过程中的结点信息来实现遍历 二叉树的非递归算法，并且假定栈空间足够大不会发生栈上 溢以简化算法。 1.前序遍历二叉树的非递归算法 n前序遍历二叉树的非递归算法思想是：从二叉树的 根结点开始，沿左子树一直深入到最左下结点时止 ，在深入的过程中访问所遇到的结点，并把所遇到 结点的非空右孩子进栈；当左子树结点全部处理完 之后，从栈顶退出当前最近访问过结点的右孩子， 再按上述过程遍历该结点的右子树；如此重复，直 到栈空时为止。 n在下面的算法中，二叉树以二叉链表存储，用一维 数组stackMAXSIZE作为栈来保存结点的右孩子信 息，top为栈顶指针，p始终指向巡访过程中当前要 处理的结点。 前序遍历的非递归算法描述 #define MAXSIZE 100 void nrpreorder(bitree bt) bitree stackMAXSIZE,p; int top=0; p=bt; do while(p!=NULL) printf(“%dt”,p-data); if(p-rchild!=NULL) /*如果右子树不空*/ stack+top=p-rchild; /*右孩子进栈*/ p=p-lchild; if(top0) p=stacktop-; while(top0); /*当栈不空时继续遍历*/ 2.中序遍历二叉树的非递归算法 n中序遍历二叉树的非递归算法，其基本思想与前 序遍历类同，只是沿左子树向下搜索的过程中先将 所遇结点进栈，待遍历完左子树返回时从栈顶退出 结点并访问，然后再遍历右子树。 中序遍历的非递归算法描述 #define MAXSIZE 100 void nrinorder(bitree bt) bitree stackMAXSIZE,p; int top=0; p=bt; do while(p!=NULL) stack+top=p; /*所遇结点进栈*/ p=p-lchild; /*继续搜索p的左子树*/ if(top0) p=stacktop-; /*出栈一个结点*/ printf(“%dt”,p-data); /*访问结点*/ p=p-rchild; /*继续搜索右子树*/ while(top0); 3.后序遍历二叉树的非递归算法 n后序遍历二叉树的非递归算法要比前序和中序遍 历稍复杂些。 n在后序遍历中，当搜索指针指向一个结点时不能 马上访问，需要先遍历左子树，所以结点需要进栈 保存； n当遍历完左子树返回再次搜索到该结点时还不能 进行访问，还需要遍历其右子树，所以结点需要再 次进栈保存；即一个结点在两次进栈两次出栈之后 才能访问。 后序遍历二叉树的非递归算法续 n为了区别某一结点指针的两次出栈，需设置一标 志flag同结点同时进出栈，flag定义如下： n栈中数据类型可定义为指向结点的指针和flag组成 的结构体类型： typedef struct stackelem bitree link; int flag; stackelemtype; 后序遍历的非递归算法描述 #define MAXSIZE 100 void nrpostorder(bitree bt) stackelemtype stackMAXSIZE; /*定义栈*/ bitree p; int top=0,sign; p=bt; /*巡访指针指向二叉树的根结点*/ do while(p!=NULL) stack+top.link=p; /*结点第一次入栈*/ stacktop.flag=0; /*置标志为0*/ p=p-lchild; /*遍历左子树准备*/ 后序遍历的非递归算法描述续 if(top0) sign=stacktop.flag; /*标志出栈存于sign*/ p=stacktop-.link; if(sign=0) /*flag为0，是第一次出栈*/ stack+top.link=p; stacktop.flag=1; /*置标志为1*/ p=p-rchild; else /*flag为1，是第二次出栈*/ printf(“%dt”,p-data); p=NULL; while(top0); 4.二叉树的层次遍历 n所谓层次遍历（levelorder traversal ）是指从二叉树的根结点开始从上到 下逐层遍历该二叉树，在同一层次中 从左到右依次访问各个结点。例如对 右图的二叉树，按层次遍历得到的结 点序列为ABCDEFG。 n由层次遍历的定义可知，层次遍历是从根结点开始 访问，然后访问它的左孩子和右孩子，接下来是它左 孩子的左孩子和右孩子，右孩子的左孩子和右孩子， 。即在访问完某个结点后，一般不能马上访问它 的左孩子和右孩子（除根结点等特殊情况外），需要 把它的左右孩子信息保存起来。 二叉树的层次遍历（续） n这种方式正好与队列的操作特点吻合，所以可利 用一个队列结构来实现层次遍历，其做法是： (1) 首先将根结点入队列； (2) 当队列不空，从队列中取出队头结点访问它，并在其 左右孩子非空时，把它的左孩子和右孩子结点依次入队列； (3) 反复执行(2)，直到队列为空时止。 n 在下面的层次遍历算法中，二叉树以二叉链表存 储，用一维数组queueMAXSIZE实现循环队列，变 量front和rear为分别表示队头指针和队尾指针的指示 器变量，并假定队列有足够空间不会发生上溢。 二叉树的层次遍历算法描述 #define MAXSIZE 100 void levelorder(bitree bt) bitree queueMAXSIZE; int front,rear; if(bt=NULL) return; front=0; rear=0; queue+rear=bt; /*根结点入队列*/ while(front!=rear) front=(front+1)%MAXSIZE; printf(“%dt”,queuefront-data); 二叉树的层次遍历算法描述续 if(queuefront-lchild!=NULL) rear=(rear+1)%MAXSIZE; /*修改队尾指针*/ queuerear=queuefront-lchild; if(queuefront-rchild!=NULL) rear=(rear+1)%MAXSIZE; queuerear=queuefront-rchild; 4.3 二叉树的遍历 4.3.1 遍历二叉树的递归算法 4.3.2 遍历二叉村的非递归算法 4.3.3 遍历序列与二叉树的复原 4.3.4 基于遍历的几种二叉树运算的 实现和应用举例 二叉树的复原 n由前面的讨论可知，任意一棵二叉树中结点的前 序、中序、后序和层次遍历次序都是惟一的。 n反过来讲，由一种遍历次序能否惟一确定一棵二 叉树呢？回答是否定的。 n然而，我们可以由两种遍历次序惟一确定一棵二 叉树，这就是二叉树的复原问题。 1.利用前序序列和中序序列恢复二叉树 n 二叉树的前序遍历是先访问根结点，再按前序遍 历方式遍历根结点的左子树和右子树，即由前序序 列可以确定二叉树的根结点。 n另一方面，中序遍历是先中序遍历左子树，然后 访问根结点，最后中序遍历右子树；根结点在中序 序列中必然将结点分割成为两个子序列，根结点前 的子序列是其左子树的中序序列，而根结点后的子 序列是其右子树的中序序列。 利用前序序列和中序序列恢复二叉树续 n现在可以根据这两个子序列在前序序列中找到对 应的左子序列和右子序列，两个子序列在前序中的 第一个结点分别是根结点的左孩子和右孩子结点， 即左子树和右子树的根结点；此时左右子树的根结 点又分别把左右子序列各划分成两个子序列。 n如此一直做下去，由前序序列确定各级子树的根 结点，由中序序列确定隶属于各级子树的左右子树 中的结点，当取尽前序序列中的所有结点时，各级 子树中的左右孩子都惟一确定了，二叉树也就恢复 了；而且这种恢复是惟一的。 利用前序、中序序列恢复二叉树举例 n已知一棵二叉树的前序序列为ABDCEFG，中序 序列为DBAFEGC，其二叉树的恢复过程是： n先由前序序列知A为根结点，由中序序列知DB为左子树 而FEGC为右子树，如下图(a)； n其次由前序序列确定左右子树的根结点为B和C，由中序 序列知D为B的左孩子B无右孩子，FEG为C的左子树C无 右子树，如上图(b)； 利用前序、中序序列恢复二叉树举例续 n现在由前序序列确定C的左子树的根结点为E，由中序序 列知F为E的左孩子而G为E的右孩子，这样就得到了最终 恢复的二叉树，如下图(c)。 2.利用后序序列和中序序列恢复二叉树 n同利用前序序列和中序序列恢复二叉树的道理一 样，利用后序序列和中序序列也可以惟一确定一棵 二叉树。 n在恢复二叉树的过程中，后序序列的作用如同前 面的前序序列一样是确定各级子树的根结点；无非 是前序序列中第一个结点为根结点而后序序列中最 后一个结点为根结点。 n中序序列的作用仍然是确定隶属于各级子树的左 右子树中的结点，当各级子树中的左右孩子都惟一 确定时，二叉树就完全恢复了。 利用后序、中序序列恢复二叉树举例 n对于后序序列DBFGECA和中序序列BDAFEGC，可以 这样恢复二叉树： n首先由后序序列知A为根结点，由中序序列知BD和FEGC 分别为左右子树，如下图(a)； n其次由后序序列知B和C为左右子树的根结点，由中序序 列知D为B的右孩子B无左孩子，FEG为C的左子树C无右子 树，如上图(b)； 利用后序、中序序列恢复二叉树举例续 n现在由后序序列确定C的左子树的根结点是E，由中序序 列知F为E的左孩子而G为E的右孩子，最后得到的二叉树 ，如下图(c)。 3.利用层次序列和中序序列恢复二叉树 n利用层次序列和中序序列也可以惟一确定（或恢 复）一棵二叉树。 n层次遍历是从上到下处于不同层次的各级子树根 结点的前后顺序排列，在同层中是从左到右依次顺 序排列的。 n先由层次序列知其第一个结点为二叉树的根结点 ，由中序序列区分隶属于左右子树中的结点序列； 这样的过程一直进行下去，直到其每一级子树的孩 子结点都惟一确定，二叉树就恢复了。 利用层次、中序序列恢复二叉树举例 n设有层次序列ABCDEFGH和中序序列BDAFEHGC，恢 复过程： n由层次序列知根结点为A，由中序序列知其左子树为BD 而右子树为FEHGC，如下图(a)； n再由层次序列知B为A的左孩子而C为A的右孩子，由中 序序列知D为B的右孩子而B无左孩子，FEHG为C的左子 树而C无右子树，如下图(b)； 利用层次、中序序列恢复二叉树举例续 n现在由层次序列可知FEG的根为E即E为C的左孩子，由中 序序列知F是E的左孩子而HG是E的右子树，如下图(c)； n最后由层次序列知G是HG的根结点即G是E的右孩子，由中 序序列知H是G的左孩子，即为所求的二叉树，如下图(d) 。 二叉树的复原（续） n在上面讨论的二叉树的恢复过程中，中序序列所 起作用是很重要的，只有利用中序序列才能区分各 级子树中隶属于左右子树中的各结点，而前序序列 、后序序列或层次序列的作用仅在于确定各级子树 的根结点。 n所以，利用前序、后序和层次序列中的任何两种 序列或三种序列全用都不能惟一确定（或恢复）一 棵二叉树，这是因为只知根结点而无法区分左右子 树之缘故。 4.3 二叉树的遍历 4.3.1 遍历二叉树的递归算法 4.3.2 遍历二叉村的非递归算法 4.3.3 遍历序列与二叉树的复原 4.3.4 基于遍历的几种二叉树运算的 实现和应用举例 1.查找结点x的运算 n查找二叉树bt中的结点x，可以结合在四种遍历算法中的任 何一个算法中进行。在此我们以前序遍历来实现查找运算的 递归算法。 bitree search(bitree bt,elemtype x) if(bt!=NULL) if(bt-data=x) return bt; search(bt-lchild,x); /*在左子树中查找*/ search(bt-rchild,x); /*在右子树中查找*/ else return NULL; 2.求二叉树中的叶子结点数目 n二叉树中叶子结点即终端结点，它的度为0或者说左子树和右 子树均为空。可以利用任一种遍历方法，在遍历过程中对所遇 结点判断是否为叶子结点，若是则统计变量加1，直到遍历完 所有结点，叶子结点总数即可求得。下面给出利用中序遍历求 叶子结点数的递归算法： int countleaf(bitree bt) int num=0; if(bt!=NULL) if(bt-lchild=NULL) else num=countleaf(bt-lchild)+countleaf(bt- rchild); return num; 3.求二叉树的高度 n二叉树的高度或深度为二叉树中结点层次的最大值，由处于 第一层的根结点开始递推即可求得。可以在二叉树的前序或后 序遍历过程中求出，下面给出的算法是在后序遍历过程中求深 度的递归算法。 int treedepth(bitree bt) int h,lh,rh; if(bt=NULL) h=0; else lh=treedepth(bt-lchild); /*左子树高度赋lh*/ rh=treedepth(bt-rchild); /*右子树高度赋rh*/ if(lh=rh) h=lh+1; else h=rh+1; return h; 第4章 树与二叉树 4.1 树的基本概念 4.2 二叉树 4.3 二叉树的遍历 4.4 线索二叉树 4.5 树和森林 4.6 哈夫曼树 4.4 线索二叉树 4.4.1 线索二叉树的概念 4.4.2 线索二叉树的构造算法 4.4.3 线索二叉树上的运算实现 线索二叉树的概念 n遍历二叉树是以一定规则将二叉树中的结点排 成一个线性序列，得到二叉树中结点的某个次序 序列，如前序序列、中序序列、后序序列或层次 序列； n这种对非线性结构线性化的结果，使得除端点 外的每个结点在这个线性序列中有且仅有一个前 趋和一个后继。 n然而，用二叉链表作为存储结构时每个结点中 只有指向其左右孩子的指针，从任意一个结点出 发可以直接找到它的左右孩子，但一般不能直接 找到在某一次序序列中的前趋和后继结点。 线索二叉树的概念（续） n如果在结点中增加指向其前趋和后继的指针， 将降低存储空间的使用效率（密度）。 n大家知道，n个结点的二叉链表中必有n+1个空 指针，因此可以利用这些空指针域存放某一遍历 次序序列之下的前趋和后继指针信息。 n把这种附加的指向其前趋和后继的指针称之为 线索（thread），加上了线索的二叉链表称之为线 索链表（thread linked list），相应的二叉树称之 为线索二叉树（thread binary tree）。 线索二叉树的概念（续） n在线索链表中规定： n若结点有左子树则lchild域指向其左孩子，否则指向 其遍历序列的前趋； n若结点有右子树则rchild域指向其右孩子，否则指向 其遍历序列的后继。 n为了区别结点的链域是指向其左右孩子的指针还 是指向其前趋或后继的线索，需要在每个结点中 增加两个线索标志ltag和rtag，这两个线索标志 不需要额外的存储开销，只需利用指针域的第一 位（即符号位）便可实现。 线索二叉树的类型定义 typedef enum0, 1ptrtag; typedef struct bithnode elemtype data; struct bithnode *lchild,*rchild; ptrtag ltag,rtag; bithrnode; typedef bithrnode *bithrtree; n其中： 线索二叉树举例 n下图是一棵二叉树的中序线索二叉树和相应的中序线索链 表，图中的实线为指针而虚线为线索。在线索链表中增加 了头结点，其左链域lchild指向二叉树的根结点，右链域 rchild指向中序遍历时的最后一个结点。 4.4 线索二叉树 4.4.1 线索二叉树的概念 4.4.2 线索二叉树的构造算法 4.4.3 线索二叉树上的运算实现 线索二叉树的构造算法 n建立线索二叉树的过程称作对二叉树线索化，线 索化需要在遍历的过程中来实现。 n在对二叉树的某种次序遍历过程中，一边遍历一 边建立线索， n若当前访问结点的左孩子域为空则建立前趋线索， n若右孩子域为空则建立后继线索。 n为实现这一过程，可设指针pre指向刚刚访问过 的结点，指针p指向当前结点，就可以方便前趋和 后继线索的填入。 线索二叉树的构造算法（续 ） n下面给出的是中序线索二叉树线索化的递归算法， n其中：函数inorderthr处理头结点以及与头结点有关的指 针和线索，包括对于空二叉树的特殊处理；并调用函数 inthreading对非空二叉树进行中序线索化。 n算法的描述如下： bithrtree inorderthr(bithrtree t) bithrtree thrt; thrt=(bithrtree)malloc(sizeof(bithrnode); thrt-ltag=0; thrt-rtag=1; 线索二叉树的构造算法（续 ） if(t=NULL) thrt-lchild=thrt; thrt-rchild=thrt; else thrt-lchild=t; pre=thrt; inthreading(t); pre-rchild=thrt; pre-rtag=1; thrt-rchild=pre; return thrt; 线索二叉树的构造算法（续 ） void inthreading(bithrtree t) /*在中序遍历过程中线索化二叉树t*/ if(t!=NULL) inthreading(t-lchild); /*左子树线索化*/ if(t-lchild=NULL) t-ltag=1; t-lchild=pre; if(pre-rchild=NULL) pre-rtag=1; pre-rchild=p; pre=p; inthreading(t-rchild); /*右子树线索化*/ 4.4 线索二叉树 4.4.1 线索二叉树的概念 4.4.2 线索二叉树的构造算法 4.4.3 线索二叉树上的运算实现 1. 遍历中序线索二叉树 n遍历线索二叉树，只要从头结点出发反复找结 点的后继，直到又回到头结点时止。 n查找一个结点的后继有两种情况： n如果结点的右线索标志rtag=1，右指针所指即为中序 后继。 n如果结点的右线索rtag=0，该结点有右孩子，由中序 遍历定义知其后继结点应是它的右子树上的最左下结 点；即沿着它的右孩子结点的左指针链一直往下找， 当某结点左线索标志为1时，该结点就是要找的最左下 结点。 最左下结点示意图 遍历中序线索二叉树算法描述 v