数据结构与算法教程 朱明方 吴及 第4章 树与二叉树

《数据结构与算法教程 朱明方 吴及 第4章 树与二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章树与二叉树4.1树的基本概念一、树的定义与表示二、树的性质4.2二叉树一、二叉树的定义二、二叉树的基本性质三、二叉树的抽象数据类型四、二叉树的存储结构五、二叉树的运算六、线索二叉树第四章树与二叉树4.3二叉树应用一、利用二叉树实现表达式线性化二、最优二叉树三、二叉搜索树四、堆4.4树的运算一、树的抽象数据类型二、树的存储结构三、树的遍历四、树的其他运算第四章树与二叉树4.5森林的遍历一、森林与二叉树的转换二、森林的遍历一、树结构的引出•操作系统中的文件管理DOS操作系统早期的文件管理：4.1树

2、的基本概念……0磁道1扇区360KB(5″)软盘：0-79道,18扇区/磁道，512字节/扇区,目录扇区数：7，每个文件目录项：32字节，总目录数：112逻辑结构：文件1目录文件1正文文件2目录文件2正文文件112目录文件112正文4.1树的基本概念……问题:1.文件数受限2.文件读写速度慢改进后：文件1文件子目录1子目录根目录文件2文件子目录n文件n4.1树的基本概念…好处：增加文件数，提高查找速度4.1树的基本概念•书的章、节、目结构：书第1章第2章第3章…1.11.21.32.12.2…3.1

3、…1.1.11.1.2…4.1树的基本概念•CERNET的分层：…………………CERNET中心西北东北华北华东华南西南中南哈工大东北大学吉大南京大学浙大上海交大华南理工深圳大学兰州大学西安交大青海大学重庆大学电子科大清华北大南开大连理工华中科大武汉大学4.1树的基本概念•家族树：曾祖父祖父…伯父父亲…儿子女儿叔父…规律：问题中数据元素之间有1对多的关系——抽象为树型结构ABCDEFG4.1树的基本概念二、树的定义与表示树(tree)——树型结构，表示元素之间的层次关系；1.树的定义树是n(n≥0)个

4、结点的有限集，n=0——空树；一棵非空树：①有且只有一个特定的结点——根结点(root)；②当n>1，其余结点可分为m个互不相交的子集，它们又是一棵树——根结点的子树(subtree)；递归定义说明：树是一种递归的数据结构——树中包含树结构特点：结点间有明显层次关系(行政机构、程序模块等)例如，树：可见其结点是分层次的；4.1树的基本概念2.树的表示树除了用结点和连线表示外，还有其他方式表示，如集合图、凹入表、广义表等；ABCDEFGA(B(E,F),C(G),D)ABEFCGD4.1树的基本概念3

5、.基本术语结点(node)：数据元素及指向子树的分支；结点的度(degree)：结点拥有的子树数；叶子结点(终端结点)——度为0；分支结点(非终端结点)——度不为0。树的度：树中结点的度之最大值；孩子(child)——结点的子树的根(后件)；双亲(parent)——本结点；兄弟(sibling)——同一个双亲的孩子；祖先(ancestor)——根到某结点所经分支(路径)上所有结点；子孙(descentant)——所含子树中的结点；ABCDEFG4.1树的基本概念结点的层次(level)：从根结点开始

6、定义，根结点为第一层，根结点的孩子为第二层，…。树的深度(depth)：结点的最大层次；有序树：结点的子树从左到右有序安排(不能互换)；无序树：结点的子树顺序任意(可以互换)；森林(forest)：m(m≥0)棵互不相交的树之集合；树结点其子树的集合即为森林，由此可把树定义为：Tree=(root,F)，其中,root为根结点，F是其子树构成的森林；1A………..第1层2B3C4D….第2层E6FG7………..第3层54.1树的基本概念三、树的性质(1)设树有n个结点，每个结点的度为di(i=1,2

7、,…,n),则有：证明：除根结点外，每个结点有一个分支指向；树的总分支数为(di为结点i的度)；(2)度为k的树中，第i层上至多有ki-1个结点(i≥1)用数学归纳法证明：对于i=1,ki-1=k0=1命题成立；假设对于第i-1层(i>1)命题成立，则该层上有ki-2个结点；对于第i层，最多结点数为：ki-2.k=ki-1命题得证。(3)深度为h的k叉树，至多有个结点；利用性质(2)证明：k叉树的最大结点数为每一层最大结点数之和，则有：4.1树的基本概念4.1树的基本概念(4)具有n个结点的k叉树，

8、其最小深度为:logk(n(k-1)+1)分析：在结点数相同的k叉树中，每一层的结点都达到最大值，或除最后一层外其余层都满的树，其深度为最小；利用性质3证明：设k叉树的最小深度为h，则：(前h-1层满的k叉树结点总数)