第6部分树与二叉树.ppt

第6章 树与二叉树,6.1 树的概念和运算,6.2 二叉树,6.3 树和森林,6.4 树的典型应用,6.5 本章小结,6.1 树的概念和运算,树形结构是线性结构的拓广。 除了首元（唯一存在，在树形结构中称为“根”节点）没有前驱元素以外，树中其他所有元素（节点）都有且只有一个直接前驱元素（父节点）；直接后继元素则没有限制：没有直接后继元素的节点（叶节点）可以有多个；存在直接后继元素的节点，其直接后继元素的个数也可以有多个。,6.1.1 树的定义与表示,树的定义： 树的逻辑结构可以这样描述： 树是包含N(N0)个节点的有穷集合D，且在D上定义了一个关系R，关系R满足以下条件：,(1) 有且仅有一个节点e0D，它对于关系R来说没有前驱，节点e0称作树的根。,(2) 除节点e0外，D中的每个节点对于关系R来说都有且仅有一个前驱。,(3) 除节点e0外的任何节点eS，都存在一个节点序列(e0,e1,em)，其中e0就是树根，且em=e，有序对R（1im）。这样的节点序列称为从根到节点e的一条路径。,树的递归定义：,树是由一个或多个节点组成的有限集T，它满足下面两个条件： (1)有一个特定的节点称之为根; (2)其余的节点分成m(m0)个互不相交的有限集T1，T2，Tm，其中每个集合本身又是一棵树，称T1，T2，Tm为根的子树。,递归是树的固有属性,树的表示：,体现树形结构中分支和层次的特性 。,本书中描述树形结构 的方式,6.1.2 树的基本术语,节点 节点的度 叶子或终端节点 非终端节点或分支节点 内部节点 树的度,孩子 双亲 兄弟 祖先 子孙,节点的层次 树的深度或高度,有序树 无序树,森林,6.1.3 树的ADT,ADT Tree 数据对象为D: D是具有相同特性的数据元素的集合 数据间的关系R: (1) 若D为空集,则称为空树; (2) 若D为非空集且仅含有一个数据元素,则R为空集,树只包含一个根节点;,允许空树（即树中没有一个节点的树）存在,(3) 若D为非空集且含有不止一个数据元素,则R=H,H是同时满足如下条目的二元关系:,(3.1) D中存在唯一的一个称为根的数据元素r,它在关系H下无前驱;,(3.2) D-r,存在D-r的一个划分D1,D2,Dm(m0),对任意jk(1j,km)有DjDk=,且对任意的i(1im),惟一存在数据元素xiDi有H;,(3.3) 对应于D-r的划分,H-,有惟一的一个划分H1,H2,Hm(m0),对任意jk(1j,km)有HjHk=,且对任意的i(1im),Hi是Di上的二元关系,(Di,Hi)是一棵符合本定义的树,称为根r的子树。,几种基本操作: treeCreate(&tree) treeDestroy (&tree) treeClear(&tree) treeEmpty(tree) treeWidth(tree),创建一棵树tree,销毁一棵已有的树tree,创建一棵树tree,判树是否为空,求树的度,treeDepth(tree) treeRoot(tree) treeInsert(&tree,elem) treeDelete(&tree,elem),求树的高度(深度),求树的根,在树tree中,按照某种规则将元素elem插入到树中合适位置,在树tree中,按照某种规则将树中元素elem删除,treeTraverse(tree, visit) treeGetParent(tree,elem,&parent) treeGetChild(tree,parent,order,&child),遍历树tree各元素，并用visit代表的操作处理元素数据,在树tree中求节点elem的父节点，并将结果放入parent中,说明:在树tree中求节点parent的第order个子节点，并将结果放入child中,treeSetChild(tree,parent,order,child) ,在树tree中设置节点parent的第order个子节点，待设置的值已经放入child中,6.2 二叉树,6.2.1 二叉树的定义与基本运算 二叉树是一个集合T；它可以是空集，也可以是一个由节点组成的有限集。同时，集合T具有下列的性质： (1) 如果T是空集，则称T是空的二叉树。 (2) 如果T是有限集，则T由一个特定的、称之为根的节点，以及称为该根的两个互不相交的左子树和右子树构成，同时这两棵子树亦是二叉树。,递归定义,二叉树可以有5种基本形态，,二叉树的基本运算,与树的基本运算相类似 详见二叉树的ADT说明,6.2.2 二叉树的性质,性质(1)：在二叉树的第i层上至多有2i-1个节点（i1）。,性质(2)：深度为k的二叉树至多有2k-1个节点（k 1）。,性质(3)：对任何一棵二叉树T，如果其叶节点数为n0，度为2的节点数为n2，则n0=n2+1。,特殊形态的二叉树：,完全二叉树和满二叉树。,满二叉树： 一棵深度为k且有2k-1个节点的二叉树。 特点：每一层上的节点数都达到了最大节点数。,完全二叉树： （1）叶子节点只可能在层次最大的两层上出现； （2）对任一节点，若其右分支下的子孙节点的最大层次为k，则其左分支下的子孙的最大层次不小于k。,满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。,完全二叉树的两个重要特性：,性质(4)：具有n个节点的完全二叉树的深度为log2n+1。,性质(5)：如果对一棵有n个节点的完全二叉树（其深度为 log2n +1）的节点按层序编号（从第1层到第 log2n +1层，每层从左到右），则对任一节点i（1in），有： 如果i = 1，则节点i是二叉树的根，无双亲；如果i 1，则其双亲PARENT (i) 是节点 i/2 。 如果2i n，则节点i无左孩子（节点i是叶子节点）；否则其左孩子LCHILD(i)是节点2i 。 如果2i+1n，则节点i无右孩子；否则其右孩子RCHILD(i) 是节点2i+1。,6.2.3 二叉树的存储结构,顺序存储 以节点在向量中的相对位置来表示节点间的关系。 不足：一般的二叉树也必须按完全二叉树的形式来存储，势必会造成存储的浪费。,链式存储,单叉链表,三叉链表,二叉链表,常用链式存储结构：二叉链表,6.2.4 二叉树操作的实现,遍历（周游）算法 深度优先遍历： 先序遍历：若二叉树为空，则空操作；否则 (1)访问根节点； (2)先序遍历左子树； (3)先序遍历右子树。,中序遍历：若二叉树为空，则空操作；否则 (1)中序遍历左子树； (2)访问根节点； (3)中序遍历右子树。,后序遍历：若二叉树为空，则空操作；否则 (1)后序遍历左子树； (2)后序遍历右子树； (3)访问根节点。,二叉树遍历的典型应用表达式树,先序遍历此二叉树，得到的二叉树的先序序列为：*a-bc；,中序遍历此二叉树，得到该二叉树的中序序列为：a*b-c；,后序遍历此二叉树，得到该二叉树的后序序列为：abc-*；,前缀表示（波兰式）,后缀表示（逆波兰式）,中缀表示（中缀式）,非递归实现树的深度优先遍历 利用栈,非递归实现树的广度优先遍历 利用队列,遍历算法时间复杂度：O(N) 遍历算法空间复杂度：至多为O(N),6.3 树和森林,6.3.1 树的存储结构 三种典型的表示法： 第一种是双亲表示法。 第二种是孩子表示法。 第三种是孩子兄弟表示法。,6.3.2 树、森林与二叉树的转换,森林转换成二叉树 如果F=T1,T2,Tm是森林，则按如下规则转化成一棵二叉树B=(root,lb,rb)。 若F为空，即m=0，则B为空二叉树； 若F非空，即m0，则B的根root即为森林中第一棵树的根root(T1)；B的左子树lb是从T1中根节点的子树森林F1=T11,T12,T1k转化而成的二叉树；其右子树rb是从森林F=T2,T3,Tm转化而成的二叉树。,二叉树转化成森林 如果B=(root,lb,rb)是一棵二叉树，则可按如下规则转化成森林F=T1,T2, ,Tm 若B为空，则F为空； 若B不空，则F中第一棵树T1的根root(T1)即为二叉树B的根root；T1中根节点的子树森林F1是由B的左子树lb转换而成的森林；F中除T1之外其余树组成的森林F=T2,T3,Tm是由B的右子树rb转换而成的森林。,6.3.3 树的遍历,树的遍历 先根（次序）遍历：先访问树的根节点，然后按照从左至右的次序先根遍历根的每棵子树 后根（次序）遍历：先按照从左至右的次序后根遍历每棵子树，然后访问根节点。,森林的两种遍历方法：,(1)先序遍历森林 若森林非空，则可按下述规则遍历之： 访问森林中第一棵树的根节点； 先序遍历第一棵树中根节点的子树森林； 先序遍历除去第一棵树之后的树构成的森林。,(2)后序遍历森林 若森林非空，则可按下述规则遍历之： 后序遍历森林中第一棵树的根节点的子树森林； 访问第一棵树的根节点； 按后根次序遍历除去第一棵树之后的其余树构成的森林。,6.4 树的典型应用,6.4.1 回溯法中的解空间树与0-1背包问题 0-1背包问题: 给定n种物品和一个背包。物品i的重量是wi，其价值为pi，背包的容量为C。问：应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？,要求：对物品i只有两种选择：要么全部装入背包，要么全都不装入背包,借助树形结构组织问题的解空间，以便能用回溯法搜索整个解空间。,从根结点到叶节点的一个路径就对应着解空间的一个解,搜索最优解：回溯法,1. 从开始节点（根节点）出发，以深度优先方式搜索整个解空间。这个开始节点成为活节点，同时也成为当前的扩展节点。,2. 在当前扩展节点处，搜索向纵深方向移至一个新节点。该新节点成为新的活节点，并成为当前扩展节点。,3. 如果在当前扩展节点处不能再向纵深方向移动，则当前扩展节点就成为死节点。,往回移动（回溯）至最近的活节点处，并使这个活节点成为当前扩展节点。,以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活节点时为止。,注：为了避免无效搜索，可使用剪枝函数把不需要的子树剪去；使用限界函数剪去得不到最优解的子树,从而提高回溯法的搜索效率。,具体到0-1背包问题： 预处理 ：按各物品单位重量所包含的价值从大到小进行排列物品。 设计预估函数，其返回值说明右子树中是否存在一个比当前解更优的解决方案。以此作为剪枝的依据。,预估函数的作用： 能够估计出最优解的上界。,0-1背包问题的回溯法效率分析： 预估函数需要O(N)时间，其中N为物品种类的数量。在最坏情况下，有O(2N)个右子节点都需要进行预估，故求解0-1背包问题的回溯法时间复杂度为O(N*2N)。,6.4.2 哈夫曼树与贪心算法,相关概念： 从树中一个节点到另一个节点之间的分支构成这两个节点之间的路径； 路径上的分支数目称作路径长度。,考虑节点带权的树： 节点的带权路径长度为从该节点到树根之间的路径长度与节点上权的乘积。,树的带权路径长度为树中所有叶子节点的带权路径长度之和，记作：,试构造一棵有N个叶子结点的二叉树，则其中带权路径长度WPL最小的二叉树称作最优二叉树或哈夫曼（Huffman）树。,构造哈夫曼树思想： (1)根据给定的N个权值w1,w2,wN构成N棵二叉树的集合F =T1,T2,TN，其中每棵二叉树Ti中只有一个带权为wi的根节点，其左右子树均空；,(2)在F中选取两棵根节点权值最小的子树，分别做为左右子树来构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左右子树上根节点的权值之和；,(3)在F中删除这两棵树，同时将新得到的二叉树加入F中；,(4)重复(2)、(3)，直到F仅含一棵树为止。,贪心算法,贪心算法并不从整体最优的角度来考虑问题。它所做出的选择只是在某种意义上的局部最优选择。,哈夫曼树应用： 哈夫曼编码电文的二进制前缀编码,6.5 本章小结,基本内容： 1. 树的基本概念 2. 二叉树的定义、性质和存储结构；二叉树的遍历和线索化以及遍历算法的各种描述形式； 3. 树和森林与二叉树的转换、树和森林的遍历； 4.树的典型应用；回溯法与贪心算法。,基本要求： 熟练掌握二叉树的结构特性，了解相应的证明方法。 熟悉二叉树的各种存储结构的特点及适用范围。 熟练掌握各种遍历策略的递归算法，了解遍历过程中“栈”的作用和状态，而且能灵活运用遍历算法实现二叉树的其他操作。层次遍历是按另一种搜索策略进行的遍历。,熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。掌握各种建立二叉树和树的存储结构的方法。 学会编写实现树的各种操作的算法。 掌握建立哈夫曼编码的方法。 学习并使用贪心算法与回溯法的思想。,