第2章_数据结构与算法_第4节_树和二叉树

第1页Section4Tree&BinaryTree（树与二叉树）第2页学习内容与要求1、理解和掌握树的定义和相关术语；学习和掌握树的几种存储结构；2、学习和掌握二叉树定义、若干特性及其存储结构；3、学习和掌握二叉树的遍历方法及其递归算法实现。第3页数据对象D：D是具有相同特性的有限个数据元素的集合。若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当数据对象D中元素个数n1时，除了根之外，其余结点可分为m(m0)个互不相交的有限子集T1,T2,…,Tm，其中每一个子集本身又是一棵符合本定义的树，称为根root的子树。数据关系R：树的定义特点：（1）非线性结构，一个直接前驱，但可能有多个直接后继。（一对多或1:n）（2）树的定义具有递归性，即“树中还有树”。第4页ABCDEFGHIJMKL树的一般结构用一个圆圈表示一个结点，结点的名字（或值）写在圆圈内，以区别于其它结点；根节点与它的子树的根结点之间用连线表示它们之间的逻辑关系。第5页基本操作：查找类插入类删除类第6页Root(T)//求树的根结点查找类：Value(T,cur_e)//求当前结点的元素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历第7页InitTree(&T)//初始化，置空树插入类：CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树第8页ClearTree(&T)//将树清空删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树第9页基本术语第10页结点结点的度树的度叶子结点分支结点数据元素+若干指向其子树的分支结点挂接的分支的个数树中所有结点的度的最大值度（分支数）为零的结点度（分支数）大于零的结点ABCDEFGHIJMKL第11页(从根到结点的)路径由从根到某结点所经分支和结点构成。ABCDEFGHIJMKL•任一结点都有且只有一条到根结点的路径。双亲和孩子：结点的子树的根结点称为该结点的孩子(Child)，相应地，该结点称为孩子的双亲（parent)。兄弟和堂兄弟：同一双亲的孩子之间互为兄弟(sibling)，双亲在同一层的结点之间互为堂兄弟。祖先和孙子：结点的祖先是从根结点到该结点所经分支上的所有结点；结点的子树上的所有结点称为该结点的子孙。第12页结点的层（层次）树的深度（高度）ABCDEFGHIJMKL假设根结点的层为1，其余任一结点的层等于其双亲结点的层加1。树中各叶子结点的层的最大值。1234第13页任何一棵非空树是一个二元组:Tree=（root，F）其中root被称为根结点F被称为子树森林森林是m（m≥0）棵互不相交的树的集合ArootBCDEFGHIJMKLF第14页有序树子树之间从左至右存在确定的次序关系，不能互换（左为第一）。无序树子树之间不存在确定的次序关系，可互换位置。第15页线性结构树型结构第一个数据元素(无前驱，仅有一个后继)根结点(无前驱,可以有多个后继)最后一个数据元素(无后继，仅有一个前驱)叶子结点(多个)(无后继，仅有一个前驱)其它数据元素(仅有一个前驱、一个后继)其它数据元素(仅有一个前驱、可以有多个后继)树型结构和线性结构的结构特点对比第16页树的存储结构一、双亲数组表示法二、孩子链表表示法三、左孩子右兄弟表示法第17页G0123456ABCDEFdataparent一、双亲数组表示法–实现：定义结构数组存放树的结点，每个结点含两个域：»数据域：存放结点本身信息»双亲域：指示本结点的双亲结点在数组中位置(下标）–特点：找双亲容易，找孩子难A-1B0C0D0E2F2G501234560号单元的parent域也可不用或用于存放结点个数如何找孩子结点?第18页二、孩子链表表示法datachild1child2…….childDdatadchild1child2…….childd多重链表表示法：每个结点除数据域外，还有多个指针域，分别指向其子树的根结点（即其孩子结点）。有两种形式：各结点结构相同：各结点的指针个数相等，为树的度D。各结点结构不相同：各结点指针个数等于其结点的度d。第19页ABCDEFG多重链表表示法示例（结点结构相同）rootABCDGEF第20页ABCDEFG多重链表表示法示例（结点结构不同）rootABCE0G0F0D0213第21页ABCDEFGABCEDFGroot三、左孩子右兄弟表示法–实现：用二叉链表实现树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。–特点：操作容易，但是难易体现树的层次。datalChildrSibling第22页二叉树（BinaryTree）为何要重点研究每结点最多只有两个“叉”的树？一般树（即多叉树）的物理结构比较复杂，而且运算也很难实现。二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。1.二叉树的定义2.二叉树的性质3.二叉树的存储结构4.二叉树的遍历第23页定义：二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交叉的二叉树组成。ABCDEFGHK根结点左子树右子树第24页二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树第25页Root(T)：求二叉树T的根结点；Value(T,e)：求结点e的值；Parent(T,e)：求结点e的双亲结点；LeftChild(T,e)：求结点e的左孩子结点；RightChild(T,e)：求结点e的右孩子结点；LeftSibling(T,e)：求结点e的左兄弟结点；RightSibling(T,e)：求结点e的右兄弟结点；BiTreeEmpty(T)：判断二叉树T是否为空树；BiTreeDepth(T)：求二叉树T的深度二叉树的主要基本操作第26页InitBiTree(&T)：初始化二叉树T为空树；Assign(T,&e,value)：为结点e赋值；CreateBiTree(&T,definition)：根据定义创建二叉树；InsertChild(T,p,LR,c)：将c插入到二叉树T中成为结点p的左（或右）孩子结点；ClearBiTree(&T)：清空二叉树T；DestroyBiTree(&T)：销毁二叉树T；DeleteChild(T,p,LR)：删除二叉树T中结点p的左（或右）孩子结点第27页二叉树的遍历操作：PreOrderTraverse(T,Visit())：前序遍历InOrderTraverse(T,Visit())：中序遍历PostOrderTraverse(T,Visit())：后序遍历LevelOrderTraverse(T,Visit())：层序遍历第28页二叉树的重要性质第29页性质1（关于每层的结点数）：在二叉树的第i层上至多有2i-1个结点。(i≥1)可用归纳法证明：归纳基础：归纳假设：归纳证明：i=1层时，只有一个根结点：2i-1=20=1；假设对第i层结点，命题成立；第i层结点每个结点至多有两个孩子结点，则第i+1层的结点数≤2i-12=2i。第30页性质2（关于树的结点总数）：深度为k的二叉树上至多含2k－1个结点（k≥1）。证明：基于性质1，深度为k的二叉树上的结点数至多为20+21++2k-1=2k-1。第31页性质3（叶子结点与度为2的结点在数量上的关系）：对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1。证明：设二叉树上结点总数n=n0+n1+n2又二叉树上分支总数b=n1+2n2而b=n-1=n0+n1+n2-1由此，n0=n2+1。第32页两类特殊的二叉树：满二叉树：深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。12345678910111213141512345678910第33页满二叉树和完全二叉树有什么区别？答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前k-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。第34页性质4（完全二叉树的深度与结点总数的关系）：具有n个结点的完全二叉树的深度为log2n+1。证明：设完全二叉树的深度为k，则根据第二条性质得2k-1≤n2k即k-1≤log2nk因为k只能是整数，因此，k=log2n+1。第35页性质5：若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：(1)若i=1，则该结点是二叉树的根结点，无双亲，否则，编号为i/2的结点为其双亲结点；(2)若2in，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；(3)若2i+1n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。第36页二叉树的存储结构二、二叉树的链式存储结构一、二叉树的顺序存储结构第37页完全二叉树二叉树的顺序存储结构（示例1）注：结点从1开始编号时，从1数组单元开始存放数据（0数组单元不存放数据），编号为i的结点，其双亲结点（如果存在）编号为i/2，左孩子结点（如果存在）的编号为2i，右孩子结点（如果存在）的编号为2i+1。存储方式：按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。如何复原为二叉树？第38页一般二叉树二叉树的顺序存储结构（示例2）同样可以根据性质5用上述方法还原二叉树！问:不是完全二叉树怎么办？答：一律转为完全二叉树！方法是：将各层空缺处统统补上“虚结点”，其内容为空。第39页完全二叉树的数组表示一般二叉树的数组表示二叉树的顺序存储结构（示例3）注：结点从0开始编号时，编号为i的结点，其双亲结点（如果存在）编号为(i+1)/2-1，左孩子结点（如果存在）的编号为2i+1，右孩子结点（如果存在）的编号为2(i+1)。第40页ABCDEFABDCEF0123456789101112131401326二叉树的顺序存储结构（示例4）第41页右单支树由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，右单支树就是一个极端情况。数组大小为31，实际使用5个数组单元！第42页二叉树的另一数组表示（结构数组形式）数组中每个元素都是一个结构体类型第43页链表结点结构二叉树的链式存储结构第44页ADEBCFrootlchilddatarchild结点结构二叉链表第45页ADEBCFroot三叉链表parentlchilddatarchild结点结构第46页二叉树的链式存储结构（示例）第47页二叉树的类模板定义（二叉链表结构）第48页templateclassTypeclassBinTreeNode{private:BinTreeNodeType*LChild,*RChild;Typedata;};templateclassTypeclassBinaryTree{private:BinTreeNodeType*root;};第49页二叉树的遍历(BinaryTreeTraversal)所谓遍历，是指顺着某一条搜索路径访问（visit）二叉树中的结点，使得每个结点均被访问一次，且仅被访问一次。遍历的作用：它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。第50页“遍历”是任何数据结构均有的操作：对线性结构而言