湘潭大学 数据结构 课件 ppt Ch04 Trees

第四章树§1预备知识客观世界中许多事物存在层次关系◦人类社会家谱◦社会组织结构◦图书信息管理哲学宗教文学医药卫生农业科学工业技术哲学理论世界哲学欧洲哲学宗教宗教分析研究宗教理论与概况佛教宗教与社会政治宗教与科学破除迷信综合电工技术计算机建筑科学水利工程………一般性技术计算机软件电子模拟计算机微型计算机计算机的应用图书……软件工程程序语言编译程序操作系统………§1预备知识【定义】树是一些节点的集合。这个集合可以是空集；若非空，则树包含：(1)一个被称为根的特殊节点r;(2)以及0个或多个非空（子）树T1,,Tk，每一棵子树的根都被来自根r的一条有向边（edge）所连接。Note:子树是不相交的。因此树中的每一个节点都是一棵子树的根。一棵有N个节点的树中有条边。根节点通常画在上方。N1ACBDGFEHIJMLK节点的度（Degree）::=节点的子树个数。例如,degree(A)=3,degree(F)=0.树的度::=例如,degreeofthistree=3.)node(degreemaxtreenode叶节点（leaf）:=度为0的节点(没有孩子)。父节点（Parent）::=有子树的节点是其子树根节点的父节点。子节点（Child）::=若A节点是B节点的父节点，则B节点是A节点的子节点，也叫孩子节点。兄弟节点（sibling）::=具有同一父节点的各节点彼此是兄弟节点。§1预备知识1.术语§1预备知识ACBDGFEHIJMLK祖先结点(Ancestor)::=沿树根到某一结点路径上的所有结点都是这个结点的祖先结点。子孙结点(Descendant)::=某一结点的子树中的所有结点是这个结点的子孙。ni的深度::=从根到ni唯一的路径的长度。Depth(root)=0.ni的高度::=从ni到一片叶子的最长路径的长度。Height(leaf)=0,height(D)=2.树的高度（深度）::=height(root)=depth(deepestleaf).从n1到nk的路径::=从结点n1到nk的路径被定义为一个结点序列n1,n2,…,nk，对于1ik,ni是ni+1的父结点。路径长度::=一条路径的长度为这条路径所包含的边（分支）的个数。2.树的实现链表表示法ACBDGFEHIJMLKABCDEFGHIJKLM因此，每个节点的大小取决于子树数目。噢，这样并不太好！§1预备知识儿子-兄弟表示法FirstChildNextSiblingElementACBDGFEHIJMLKNACBNDENKNNFNNGHNINNJNNLNNMNote:这种表示法并非唯一的，因为树的节点的孩子顺序是不固定的。§1预备知识树的遍历——访问每个节点恰好一次前序遍历voidpreorder(tree_ptrtree){if(tree){visit(tree);for(eachchildCoftree)preorder(C);}}〖例1〗列出分级文件系统中的目录。输出格式:深度为di的文件的名字将被di次跳格(tab)缩进后打印出来。/usrmarkalexbillbookcoursehw.chw.ccourseworkch1.cch2.cch3.ccop3530fall96spr97sum97syl.rsyl.rsyl.rcop3212fall96fall97gradesgradesp1.rp2.rp1.rp2.rUnixdirectory/usrmarkbookCh1.cCh2.cCh3.ccoursecop3530fall96syl.rspr97syl.rsum97syl.rhw.calexhw.cbillworkcoursecop3212fall96gradesp1.rp2.rfall97p2.rp1.rgradesstaticvoidListDir(DirOrFileD,intDepth){if(Disalegitimateentry){PrintName(D,Depth);if(Disadirectory)for(eachchildCofD)ListDir(C,Depth+1);}}Note:深度(Depth)是一个内部簿记变量，而不是主调例程能够期望知道的那种参数，因此，驱动例程ListDirectory用于将递归例程和外界连接起来。voidListDirectory(DirOrFileD){ListDir(D,0);}T(N)=O(N)后序遍历voidpostorder(tree_ptrtree){if(tree){for(eachchildCoftree)postorder(C);visit(tree);}}〖例2〗计算一个目录的大小。/usrmarkalexbillbookcoursehw.chw.ccourseworkch1.cch2.cch3.ccop3530fall96spr97sum97syl.rsyl.rsyl.rcop3212fall96fall97gradesgradesp1.rp2.rp1.rp2.rUnixdirectorywithfilesizes11111111111111132468152341279staticintSizeDir(DirOrFileD){intTotalSize;TotalSize=0;if(Disalegitimateentry){TotalSize=FileSize(D);if(Disadirectory)for(eachchildCofD)TotalSize+=SizeDir(C);}/*endifDislegal*/returnTotalSize;}T(N)=O(N)层序遍历voidlevelorder(tree_ptrtree){enqueue(tree);while(queueisnotempty){visit(T=dequeue());for(eachchildCofT)enqueue(C);}}245367111232453674567§2二叉树【定义】一棵二叉树T是一个有穷的结点集合。这个集合可以为空，若不为空，则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。可见左子树和右子树还是二叉树。二叉树具体五种基本形态（1）空二叉树；（2）只有根结点的二叉树；（3）只有根结点和左子树TL的二叉树；（4）只有根结点和右子树TR的二叉树；（5）具有根结点、左子树TL和右子树TR的二叉树。ФTLTRTLTR(a)(b)(c)(d)(e)递归的定义形式二叉树与树不同，除了每个结点至多有两棵子树外，子树有左右顺序之分。例如，下面两个树按一般树的定义它们是同一个树；而对于二叉树来讲，它们是不同的两个树。16特殊二叉树二叉树的深度小于结点数N，可以证明平均深度是)NO(“完美二叉树(PerfectBinaryTree)”。（也称为满二叉树）。BACD13765410982ABCDEHIJFG一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为“完全二叉树(CompleteBinaryTree)”。1211KL151413MNO“斜二叉树(SkewedBinaryTree)”（也称为退化二叉树）；13765410982ABCDEHKJFG§2二叉树17二叉树的几个重要的性质一个二叉树第i层的最大结点数为：2i-1，i1。对任何非空的二叉树T，若n0表示叶结点的个数、n2是度为2的非叶结点个数，那么两者满足关系n0=n2+1。深度为k的二叉树有最大结点总数为：2k-1，k1。ABCDEKJFHn0=4，n1=2n2=3n0=n2+1证明:设n1是度为1结点数,n是总的结点数.那么n=210nnn设B是全部分枝数.则n~B?n=B+1.因为所有分枝都来自度为1或2的结点,所以B~n1&n2?B=n1+2n2.123n0=n2+1n个结点的完全二叉树的深度为k为：§2二叉树18二叉树的存储结构1.顺序存储结构完全二叉树最适合这种存储结构。n个结点的完全二叉树的结点父子关系，简单地由序列号决定：(b)完全二叉树(a)相应的顺序存储结构1、非根结点（序号i1）的父结点的序号是i/2;2、结点（序号为i）的左孩子结点的序号是2i，（若2i=n，否则没有左孩子）;3、结点（序号为i）的右孩子结点的序号是2i+1，（若2i+1=n，否则没有右孩子）。数据ABOCSMQWK编号123456789§2二叉树19ABOMC137654982ABOM13111012C数据ABO∧∧M∧∧∧∧∧∧C编号12345678910111213(a)一般二叉树(b)对应(a)的完全二叉树造成空间严重浪费！一般二叉树采用这种结构将造成空间浪费§2二叉树202.二叉树的链表存储typedefstructTreeNode*BinTree;typedefBinTreePosition;structTreeNode{ElementTypeData;BinTreeLeft;BinTreeRight;}；LeftDataRightdataLeftRightHEDFGIACBFCBDGIHEA§2二叉树§2二叉树表达式树(语法树)〖例1〗一棵表达式树：A+BCD+ADBC树叶是操作数，而其他结点是操作符。表达式树的构造〖例〗给定中缀表达式:现在从对应的后缀表达式构建语义树ab+cde+**abT2aT1b+cdec+T1T2de+abc+deT1T2*+abc+deT1T2**〖Example〗(a+b)*(c*(d+e))=§2二叉树voidinorder(tree_ptrtree){if(tree){inorder(tree-Left);visit(tree-Element);inorder(tree-Right);}}中序遍历IterativeProgramvoiditer_inorder(tree_ptrtree){StackS=CreateStack(MAX_SIZE);for(;;){for(;tree;tree=tree-Left)Push(tree,S);tree=Top(S);Pop(S);if(!tree)break;visit(tree-Element);tree=tree-Right;}}二叉树的遍历voidpreorder(tree_ptrtree){if(tree){visit(tree-Element);preorder(tree-Left);preorder(tree-Right);}}先序遍历voidpostorder(tree_ptrtree){if(tree){postorder(tree-Left);postorder(tree-Right);visit(tree-Element);}}后序遍历〖例〗对表达式树进行遍历:A+BCD+ADBC中序遍历A+BCD后序遍历ABCD+先序遍历+ABCD§3查找树ADT–二叉查找树【定义】二叉查找树是一棵二叉树。可能为空，若非空，则满足以下性质：(1)每个结点有一个整数关键字，且关键字互异。(2)非空左子树上的结点关键字的值必须小于子树的根结点的关键字值。(3)非空右子树上的结点关键字的值必须大于子树的根结点的关键字值。(4)左右子树也是二叉查找树。305240201512251022607080651.定义§3二叉查找树2.ADT数据元素集:一个有0个或多个元素的有穷结点集合。操作集:SearchTreeMakeEmpty(SearchTreeT);PositionFind(ElementTypeX,SearchTreeT);PositionFindMin(SearchTreeT);Po