湘潭大学数据结构课件pptCh04Trees.ppt
《湘潭大学数据结构课件pptCh04Trees.ppt》由会员分享,可在线阅读,更多相关《湘潭大学数据结构课件pptCh04Trees.ppt(67页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第四章 树1 预备知识预备知识 客观世界中许多事物存在层次关系客观世界中许多事物存在层次关系人类社会家谱人类社会家谱社会组织结构社会组织结构图书信息管理图书信息管理哲哲学学宗宗教教文文学学医医药药卫卫生生农农业业科科学学工工业业技技术术哲哲学学理理论论世世界界哲哲学学欧欧洲洲哲哲学学宗宗教教宗宗教教分分析析研研究究宗宗教教理理论论与与概概况况佛佛教教宗宗教教与与社社会会政政治治宗宗教教与与科科学学破破除除迷迷信信综综合合电电工工技技术术计计算算机机建建筑筑科科学学水水利利工工程程一一般般性性技技术术计计算算机机软软件件电电子子模模拟拟计计算算机机微微型型计计算算机机计计算算机机的的应应用用图书
2、图书软软件件工工程程程程序序语语言言编编译译程程序序操操作作系系统统1 预备知识预备知识【定义定义】树是一些节点的集合。这个集合可以是空集;若非树是一些节点的集合。这个集合可以是空集;若非空,则树包含:空,则树包含:(1)一个被称为一个被称为根根的特殊节点的特殊节点 r;(2)以及以及0个或多个非空个或多个非空(子)树(子)树 T1,Tk,每一棵子树的根,每一棵子树的根都被来自根都被来自根 r 的一条有向边的一条有向边(edge)所连接。所连接。Note:子树是不相交的。因此树中的每一个节点都是一棵子子树是不相交的。因此树中的每一个节点都是一棵子树的根。树的根。一棵有一棵有N个节点的树中有个节
3、点的树中有 条边。条边。根节点通常画在上方。根节点通常画在上方。N 1ACBDGFEHIJMLK 节点的度(节点的度(Degree):=节点的子树个数。节点的子树个数。例如例如,degree(A)=3,degree(F)=0.树的度树的度:=例如例如,degree of this tree=3.叶节点叶节点(leaf):=度为度为0的节点的节点(没有孩子没有孩子)。父节点(父节点(Parent):=有子树的节点是有子树的节点是其子树根节点的父节点。其子树根节点的父节点。子节点(子节点(Child):=若若A节点是节点是B节点的父节点,则节点的父节点,则B节点是节点是A节点节点的子节点,也叫的子
4、节点,也叫孩子节点孩子节点。兄弟节点兄弟节点(sibling):=具有同一父节点的各节点彼此是兄弟节点。具有同一父节点的各节点彼此是兄弟节点。1 预备知识预备知识1.术语术语1 预备知识预备知识ACBDGFEHIJMLK 祖先结点祖先结点(Ancestor):=沿沿树根到某一结点路径树根到某一结点路径上的所有结点都是上的所有结点都是这个结点的祖先结点。这个结点的祖先结点。子孙结点子孙结点(Descendant):=某一结点的某一结点的子树中的所有结点子树中的所有结点是这个结是这个结点的子孙。点的子孙。ni的深度的深度:=从根到从根到ni 唯一的路径的长度。唯一的路径的长度。Depth(root
5、)=0.ni的高度的高度:=从从ni 到一片叶子的最长路径的长度。到一片叶子的最长路径的长度。Height(leaf)=0,height(D)=2.树的高度(深度)树的高度(深度):=height(root)=depth(deepest leaf).从从n1 到到 nk 的路径的路径:=从结点从结点n1到到nk的路径被定的路径被定义为一个结点序列义为一个结点序列n1,n2,nk,对于,对于1 i k,ni是是 ni+1的父结点。的父结点。路径长度路径长度:=一条路径的长度为这条路径所一条路径的长度为这条路径所包含的边包含的边(分支)的个数(分支)的个数。2.树的实现树的实现 链表表示法链表表示
6、法ACBDGFEHIJMLKABCDEFGHIJKLM因此,每个节点的大小取决于因此,每个节点的大小取决于子树数目。噢,这样并不太好!子树数目。噢,这样并不太好!1 预备知识预备知识 儿子儿子-兄弟表示法兄弟表示法FirstChild NextSiblingElementACBDGFEHIJMLKNACBNDENKN NFN NGHNIN NJN NLN NMNote:这种表示法这种表示法并非唯一并非唯一的,因为树的节点的孩子顺序的,因为树的节点的孩子顺序是不固定的。是不固定的。1 预备知识预备知识 树的遍历树的遍历 访问每个节点恰好一次访问每个节点恰好一次 前序前序遍历遍历void preo
7、rder(tree_ptr tree)if (tree)visit(tree);for(each child C of tree)preorder(C);例例1 列出分级文件系统中的目录。列出分级文件系统中的目录。输出格式输出格式:深度深度为为 di 的文件的名字将被的文件的名字将被 di 次跳格次跳格(tab)缩进后打印出缩进后打印出来。来。/usrmarkalexbillbookcoursehw.chw.ccourseworkch1.cch2.cch3.ccop3530fall96spr97 sum97syl.rsyl.rsyl.rcop3212fall96fall97gradesgrad
8、esp1.rp2.rp1.rp2.rUnix directory/usr mark bookCh1.cCh2.cCh3.c coursecop3530 fall96syl.r spr97syl.r sum97syl.r hw.c alex hw.c bill work coursecop3212 fall96gradesp1.rp2.r fall97p2.rp1.rgradesstatic void ListDir(DirOrFile D,int Depth)if (D is a legitimate entry)PrintName(D,Depth);if(D is a directory)f
9、or(each child C of D)ListDir(C,Depth+1);Note:深度深度(Depth)是一个内部簿记变量,是一个内部簿记变量,而不是主调例程能够期望知道的那种参而不是主调例程能够期望知道的那种参数,因此,驱动例程数,因此,驱动例程ListDirectory用于用于将递归例程和外界连接起来。将递归例程和外界连接起来。void ListDirectory(DirOrFile D)ListDir(D,0);T(N)=O(N)后序后序遍历遍历void postorder(tree_ptr tree)if (tree)for(each child C of tree)posto
10、rder(C);visit(tree);例例2 计算一个目录的大小。计算一个目录的大小。/usrmarkalexbillbookcoursehw.chw.ccourseworkch1.cch2.cch3.ccop3530fall96spr97sum97syl.rsyl.rsyl.rcop3212fall96fall97gradesgradesp1.rp2.rp1.rp2.rUnix directory with file sizes11111111111111132468152341279static int SizeDir(DirOrFile D)int TotalSize;TotalSiz
11、e=0;if (D is a legitimate entry)TotalSize=FileSize(D);if(D is a directory)for(each child C of D)TotalSize+=SizeDir(C);/*end if D is legal*/return TotalSize;T(N)=O(N)层序层序遍历遍历void levelorder(tree_ptr tree)enqueue(tree);while(queue is not empty)visit(T=dequeue();for(each child C of T)enqueue(C);2453671
12、112 324 536 745 6 72 二叉树二叉树【定义定义】一棵二叉树一棵二叉树T是一个有穷的结点集合。这个集合是一个有穷的结点集合。这个集合可以为可以为空空,若不为空,则它是由,若不为空,则它是由根结点根结点和称为其和称为其左子树左子树TL和和右子树右子树TR的的两个不相交的二叉树组成。可见两个不相交的二叉树组成。可见左子树和右子树还是二叉树左子树和右子树还是二叉树。二叉树具体五种基本形态二叉树具体五种基本形态(1)空空二叉树;二叉树;(2)只有根只有根结点的二叉树;结点的二叉树;(3)只有)只有根结点和左子树根结点和左子树TL的二叉树;的二叉树;(4)只有)只有根结点和右子树根结点和
13、右子树TR的二叉树;的二叉树;(5)具有)具有根结点、左子树根结点、左子树TL和右子树和右子树TR的二叉树。的二叉树。TLTRTLTR (a)(b)(c)(d)(e)递归的定义形式递归的定义形式 二叉树二叉树与树不同,除了每个结点至多有两棵子树外,与树不同,除了每个结点至多有两棵子树外,子子树树有左右顺序之分有左右顺序之分。例如,例如,下面下面两个树按一般树的定义它们是两个树按一般树的定义它们是同一个树同一个树;而对而对于二叉树来讲,它们是于二叉树来讲,它们是不同的两个树不同的两个树。16 特殊特殊二叉树二叉树 二叉二叉树树的深度小于的深度小于结结点数点数N,可以,可以证证明平均深度是明平均深
14、度是 “完美二叉完美二叉树树(Perfect Binary Tree)”。(也称。(也称为为满满二叉二叉树树)。)。BACD13765410982ABCDEHIJFG 一棵深度为一棵深度为k的有的有n个结点的二叉树,对树中的结点按从上至下、个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为从左到右的顺序进行编号,如果编号为i(1 i n)的结点与满二)的结点与满二叉树中编号为叉树中编号为 i 的结点在二叉树中的位置相同,则这棵二叉树称为的结点在二叉树中的位置相同,则这棵二叉树称为“完全二叉树完全二叉树(Complete Binary Tree)”。1211KL15141
15、3MNO “斜二叉斜二叉树树(Skewed Binary Tree)”(也称(也称为为退化二叉退化二叉树树););13765410982ABCDEHKJFG2 二叉树二叉树17 二叉树二叉树的几个的几个重要的性质重要的性质 一个二叉树第一个二叉树第 i 层的最大结点数为:层的最大结点数为:2 i-1,i 1。对任何非空的二叉树对任何非空的二叉树 T,若,若n0表示叶结点的个数、表示叶结点的个数、n2是度为是度为2的非叶结点个数,那么两者满足关系的非叶结点个数,那么两者满足关系n0=n2+1。深度为深度为k的二叉树有最大结点总数为:的二叉树有最大结点总数为:2 k-1,k 1。ABCDEKJFH
16、 n0=4,n1=2 n2=3 n0=n2+1证明证明:设设 n1 是度为是度为1结点数结点数,n 是总的结点数是总的结点数.那么那么 n=设设 B 是全部分枝数是全部分枝数.则则 n B?n=B+1.因为所有分枝都来自度为因为所有分枝都来自度为1或或2的结点的结点,所以所以 B n1&n2?B=n1+2 n2.123 n0=n2+1 n个结点的完全二叉树的深度为个结点的完全二叉树的深度为k 为为:2 二叉树二叉树18 二叉树的存储结构二叉树的存储结构1.顺序顺序存储结构存储结构 完全二叉树完全二叉树最适合这种存储结构。最适合这种存储结构。n个结点的个结点的完全二叉树的完全二叉树的结点父子关系
17、结点父子关系,简单地由,简单地由序列号序列号决定:决定:(b)完全完全二叉树二叉树(a)相应的相应的顺序顺序存储结构存储结构1、非根结点(序号、非根结点(序号 i 1)的)的父结点父结点的序号是的序号是 i/2;2、结点(序号为、结点(序号为 i)的)的左孩子左孩子结点的序号是结点的序号是 2i,(若(若2 i=n,否则没有左孩子),否则没有左孩子);3、结点(序号为、结点(序号为 i)的)的右孩子右孩子结点的序号是结点的序号是 2i+1,(若(若2 i+1Left);visit(tree-Element);inorder(tree-Right);中序中序遍历遍历Iterative Progr
18、amvoid iter_inorder(tree_ptr tree)Stack S=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;二叉树的遍历二叉树的遍历void preorder(tree_ptr tree)if (tree)visit(tree-Element);preorder(tree-Left);preorder(tree-Right);先序先序遍历遍历void
19、 postorder(tree_ptr tree)if (tree)postorder(tree-Left);postorder(tree-Right);visit(tree-Element);后序后序遍历遍历例例 对表达式树进行遍历对表达式树进行遍历:A+B C D+A DBC 中序中序遍历遍历 A+B C D 后序后序遍历遍历 A B C D +先序先序遍历遍历 +A B C D3 查找树查找树ADT 二叉查找树二叉查找树【定义定义】二叉查找树二叉查找树是一棵二叉树。可能为空,若非空,则满足以是一棵二叉树。可能为空,若非空,则满足以下性质:下性质:(1)每个结点有一个每个结点有一个整数关键
20、字,整数关键字,且关键字且关键字互异。互异。(2)非空非空左左子树上的结点关键字的值必须子树上的结点关键字的值必须小于小于子树的根结点的关键字子树的根结点的关键字值。值。(3)非空非空右右子树上的结点关键字的值必须子树上的结点关键字的值必须大于大于子树的根结点的关键字子树的根结点的关键字值。值。(4)左右子树也是二叉查找树。左右子树也是二叉查找树。305240201512251022607080651.定义定义3 二叉查找树二叉查找树2.ADT数据元素集数据元素集:一个有一个有0个或多个元素的有穷结点集合。个或多个元素的有穷结点集合。操作集操作集:SearchTree MakeEmpty(Se
21、archTree T);Position Find(ElementType X,SearchTree T);Position FindMin(SearchTree T);Position FindMax(SearchTree T);SearchTree Insert(ElementType X,SearchTree T);SearchTree Delete(ElementType X,SearchTree T);ElementType Retrieve(Position P);3 二叉查找树二叉查找树3.实现实现 FindPosition Find(ElementType X,SearchTr
22、ee T)if(T=NULL)return NULL;/*not found in an empty tree*/if(X Element)/*if smaller than root*/return Find(X,T-Left);/*search left subtree*/else if(X T-Element)/*if larger than root*/return Find(X,T-Right);/*search right subtree*/else /*if X=root*/return T;/*found*/T(N)=S(N)=O(d)d 是是X的深度的深度这个测试必须首先进行
23、吗这个测试必须首先进行吗?它们是尾递归。它们是尾递归。如何消除?如何消除?3 二叉查找树二叉查找树Position Iter_Find(ElementType X,SearchTree T)/*iterative version of Find*/while (T)if (X=T-Element)return T;/*found*/if (X Element)T=T-Left;/*move down along left path*/else T=T-Right;/*move down along right path*/*end while-loop*/return NULL;/*not f
24、ound*/查找最大和最小元素查找最大和最小元素 最大元素最大元素一定是在一定是在树的树的最右分枝的端结点最右分枝的端结点上上 最小元素最小元素一定是在树的一定是在树的最左分枝的端结点最左分枝的端结点上上181015207229最左端点最左端点最右端点最右端点3 二叉查找树二叉查找树3 二叉查找树二叉查找树 FindMinPosition FindMin(SearchTree T)if(T=NULL)return NULL;/*not found in an empty tree*/else if(T-Left=NULL)return T;/*found left most*/else ret
25、urn FindMin(T-Left);/*keep moving to left*/FindMaxPosition FindMax(SearchTree T)if(T!=NULL)while(T-Right!=NULL)T=T-Right;/*keep moving to find right most*/return T;/*return NULL or the right most*/T(N)=O(d)T(N)=O(d)3 二叉查找树二叉查找树 Insert305240算法梗概算法梗概:Insert 80 检查检查 80 是否已在树中;是否已在树中;80 40,所以它必定是所以它必定是4
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 湘潭 大学 数据结构 课件 pptCh04Trees
限制150内