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

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