第4章 树-36 - v2

null第4章 树第4章 树张成文 北京邮电大学计算机学院 本章要点本章要点熟练掌握二叉树的结构特性； 熟悉二叉树的各种存储结构的特点及适用范围； 熟练掌握二叉树各种遍历策略的算法； null 树的定义与基本术语1.定义: 树是n(n≥0)个结点的有限集合T。当n=0时,称为空树;当n>0时,该集合满足如下条件: (1) 其中必有一个称为根(root)的特定结点,它没有直接前驱,但有零个或多个直接后继。 (2) 其余n-1个结点可以划分成m(m≥0)个互不相交的有限集T1,T2,T3,…,Tm,其中Ti又是一棵树,称为根root的子树。每棵子树的根结点有且仅有一个直接前驱,但有零个或多个直接后继。 一、树(tree)的基本概念:nullABCDEFGHIJMKLA( B(E, F(K, L)), C(G), D(H, I, J(M)) )T1T3T2树根例如:null线性结构树型结构第一个数据元素 (无前驱) 根结点 (无前驱)最后一个数据元素 (无后继)多个叶子结点 (无后继)其它数据元素 (一个前驱、 一个后继)其它数据元素 (一个前驱、 多个后继)对比树型结构和线性结构的结构特点null结点(node):树的度:叶子结点(leaf) :分支结点:数据元素+若干指向子树的分支树各结点的度的最大值度为零的结点度大于零的结点DHIJM2.树的相关术语结点的度(degree):结点拥有的子树数结点的层次: (level)假设根结点的层次为1,第l 层的结点的子树根结点的层次为l+1树的深度(depth):叶子结点所在的最大层次分支(branch):示数据元素与它的子树的关系null路径(path):常用家族树的术语表示结点关系 孩子(child) 结点 双亲(parent)结点 兄弟结点由根到该结点所经的分支和结点构成树的结点数n和分支数b的关系是: b=n-1null二叉树1 二叉树的定义与基本操作定义： 满足以下两个条件的树称做二叉树(Binary Tree): （1）每个结点的度都不大于2； （2）每个结点的孩子结点次序不能任意颠倒。null 二叉树或为空树, 或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。注意:二叉树是有序树,它的子树有左右之分。二叉树的度数不超过二,但度数不超过二的树未必是二叉树。ABCDEFGHK根结点左子树右子树null二叉树的五种基本形态:N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均非空树null用归纳法证明: 归纳基: 归纳假设: 归纳证明:i = 1 层时,只有一个根结点: 2i-1 = 20 = 1 命成立;假设 i-1 命题成立,即: 第i-1层至多有结点= 2i-1-1 = 2i-2 个; 二叉树每个结点至多有两棵子树,则 第i 层至多有结点 = 2i-2 2 = 2i-1 个。2 二叉树的重要特性性质1 :二叉树第 i 层上至多有2i-1 个结点。null证明: 基于性质1, 深度为 k 的二叉树上的结点总数的最大值是将二叉树每层上结点的最大值相加，所以深度为 k 的二叉树上含 结点数至多为： 20+21+       +2k-1 = 2k-1 性质 2 : 深度为 k 的二叉树上至多含 2k-1 个结点(k≥1)。null证明:设 二叉树上结点总数： n = n0 + n1 + n2 再根据树的性质： b = n-1 = n0 + n1 + n2 - 1 由有二叉树分支总数： b = n1+2n2 两式右边相等得: n0 = n2 + 1 。性质 3 : 对任何一棵二叉树,若它含有n0 个叶子结点、n2 个度为 2 的结点, 则必存在关系式:n0 = n2+1。也可以用归纳法证明null可用一维数组存储: bt[n] 顺序: 完全二叉树中将编号i的结点存在bt[i]中。 一、 二叉树的顺序存储 3 二叉树的存储结构 二叉树是非线性结构，结点最多有两个后继。存储结构有两种：顺序存储结构和链式存储结构。null例如: A B D C E F1 2 3 4 5 6 7 8 9 10 11 12 13 14 一般二叉树，按完全二叉树结点的编号存放, 无结点的单元存放空元素。会造成空间浪费null二、二叉树的链式存储表示 二叉链表 每个结点包括两个指针域：指向左孩子和右孩子二叉树T二叉链表结点结构:nulllchild data rchild结点结构:二叉链表结点的结构用C语言描述为 ： typedef struct Node { DataType data; strct Node * LChild; struct Node * RChild; }BiTNode, *BiTree; null一、问题的提出二、先左后右的遍历算法三、算法描述二叉树的遍历null “遍历”: 沿某条搜索路径巡访二叉树的结点, 使每个结点均被访问一次, 且仅被访问一次。一、问题的提出“访问”: 的含义很广, 如:输出结点信息等。 “遍历”是任何类型均有的操作, 对线性结构而言, 只有一条搜索路径(因为每个结点只有一个后继), 故不需要另加讨论. “二叉树”由三部分组成：根结点、左子树和右子树。若能依次遍历这三部分，就遍历了整个二叉树。 用L、D、R表示遍历左子树、访问根结点、遍历右子树，则有8种遍历二叉树： 二叉树是非线性结构, 每个结点有两个后继, 则存在按什么样的搜索路径遍历的问题。 “二叉树”由三部分组成：根结点、左子树和右子树。若能依次遍历这三部分，就遍历了整个二叉树。 用L、D、R表示遍历左子树、访问根结点、遍历右子树，则有8种遍历二叉树方案：先左后右：DLR、LDR、LRD、按层次 先右后左：DRL、RDL、RLD 、按层次null二、先左后右的遍历算法先序的遍历算法DLR中序的遍历算法LDR后序的遍历算法LRDDLRnull 若二叉树为空树,则空操作;否则, (1)访问根结点; (2)先序遍历左子树; (3)先序遍历右子树。先序的遍历算法:DLRnullD L R先序遍历序列：A B D C先序遍历:null 若二叉树为空树,则空操作;否则, (1)中序遍历左子树; (2)访问根结点; (3)中序遍历右子树。中序的遍历算法:DLRnullL D R中序遍历序列：B D A C中序遍历:null 若二叉树为空树,则空操作;否则, (1)后序遍历左子树; (2)后序遍历右子树; (3)访问根结点。后序的遍历算法:DLRnull L R D后序遍历序列： D B C A后序遍历:nullabcdefghij例如:先序序列: a b d h i e j c f g中序序列: h d i b j e a f c g后序序列: h i d j e b f g c a利用遍历结果确定二叉树问题利用遍历结果确定二叉树问题利用遍历结果确定二叉树问题 先序序列+中序序列 中序序列+后序序列 先序序列+后序序列 (x) 先序序列: ABCDEFGH 中序序列: BDCEAFHGABFCGDEHnull用二叉树表示表达式-+/a*efb-cd先序: -+a*b-cd/ef 中序: a+b*c-d-e/f 后序: abcd-*+ef/-三个序列恰好为它的 前缀中缀后缀表示式原式:a+b*(c-d)-e/fnull三、算法的递归描述1) 先序遍历 void PreOrder(BiTree bt) /*先序遍历,根指针为bt的二叉树*/ { if(bt!=NULL) { Visit(bt->data); //访问根结点 PreOrder(bt->LChild); //遍历左子树 PreOrder(bt->RChild); //遍历右子树 } }null2) 中序遍历 void InOrder(BiTree bt) /*中序遍历根指针为bt的二叉树*/ { if(bt!=NULL) { InOrder(bt->LChild); //遍历左子树 Visit(bt->data); //访问根结点 InOrder(bt->RChild); //遍历右子树 } } null3) 后序遍历 void PostOrder(BiTree bt) /* 后序遍历根指针为bt的二叉树 */ { if(bt!=NULL) { PostOrder(bt->LChild); //遍历左子树 PostOrder(bt->RChild); //遍历右子树 Visit(bt->data); //访问根结点 } } null 仅知二叉树的先序序列"abcdefg"不能唯一确定一棵二叉树,如果同时已知二叉树的中序序列"cbdaegf",则会如何？ 4)由先序和中序序列确定二叉树二叉树的先序序列二叉树的中序序列左子树左子树右子树右子树根根nulla b c d e f gc b d a e g f例如:aab bccddeeffggabcdefg^^^^^^^^先序序列中序序列小结树 二叉树 二叉树的遍历 中序遍历 先序遍历 后序遍历 小结