数据结构章树和叉树

《数据结构章树和叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章树和二叉树（Tree&BinaryTree2021/9/9数据结构2数据结构课程的内容2021/9/9数据结构3第1章绪论第2章线性表第3章栈和队列第4章串第5章数组和广义表第6章树和二叉树第7章图第9章查找第10章内排序目录2021/9/9数据结构4目录6.1树的定义和基本术语16.2二叉树26.3遍历二叉树和线索二叉树36.4树和森林46.5赫夫曼树及其应用5782021/9/9数据结构56.1树的基本概念特点：非线性结构，一个直接前驱，但可能有多个直接后继。6.1.1树的定义注1：过去许多书籍中都定义树为n≥1，曾经有“空树不

2、是树”的说法，但现在树的定义已修改。注2：树的定义具有递归性，即“树中还有树”。由n个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树。ABCGEIDHFJFLK2021/9/9数据结构66.1.2树的逻辑表示方法一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。特点：树的5种表示法：图形表示法嵌套集合表示法广义表表示法凹入表示法左孩子－右兄弟表示法202

3、1/9/9数据结构7图形表示法教师学生其他人员2009级2010级2011级2012级……辽宁工程技术大学电气系电信学院外语系……叶子根子树2021/9/9数据结构8嵌套集合表示法2021/9/9数据结构9(A(B(E(K,L),F),C(G),D(H(M),I,J))约定：根作为由子树森林组成的表的名字写在表的左边广义表表示法2021/9/9数据结构10凹入表示法又称目录表示法2021/9/9数据结构11ABCDEFGHIJKLMdata左孩子右兄弟左孩子－右兄弟表示法多叉树转为了二叉树2021/9/9数据结构126.1.3若干术语——

4、即上层的那个结点(直接前驱)——即下层结点的子树的根(直接后继)——同一双亲下的同层结点（孩子之间互称兄弟）——即双亲位于同一层的结点（但并非同一双亲）——即从根到该结点所经分支的所有结点——即该结点下层子树中的任一结点ABCGEIDHFJFLK根叶子森林有序树无序树——即根结点(没有前驱)——即终端结点(没有后继)——指m棵不相交的树的集合(例如删除A后的子树个数)双亲孩子兄弟堂兄弟祖先子孙——结点各子树从左至右有序，不能互换（左为第一）——结点各子树可互换位置。2021/9/9数据结构13树的度树的深度(或高度)ABCGEIDHFJF

5、LK——所有结点度中的最大值（Max{各结点的度}）——指所有结点中最大的层数（Max{各结点的层次}）问：右上图中的结点数＝；树的度＝；树的深度＝——即树的数据元素——结点挂接的子树数结点结点的度结点的层次终端结点分支结点——从根到该结点的层数（根结点算第一层）——即度为0的结点，即叶子——即度不为0的结点（也称为内部结点）（有几个直接后继就是几度，亦称“次数”）13342021/9/9数据结构146.2二叉树为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性

6、。6.2.1二叉树的定义6.2.2二叉树的性质6.2.3二叉树的存储结构2021/9/9数据结构156.2.1二叉树的定义定义：是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。逻辑结构：一对二（1:2）基本特征:①每个结点最多只有两棵子树（不存在度大于2的结点）；②左子树和右子树次序不能颠倒。问：具有3个结点的二叉树可能有几种不同形态？有5种基本形态：一般的树有几种？2021/9/9数据结构166.2.2二叉树的性质(3+2)讨论1：第i层的结点数最多是多少？（利用二进制性质可轻松求出）

7、性质1:在二叉树的第i层上至多有2i-1个结点（i>0）。性质2:深度为k的二叉树至多有2k-1个结点（k>0）。再提问：第i层上至少有个结点？1讨论2：深度为k的二叉树，最多有多少个结点？（利用二进制性质可轻松求出）2i-1个2k-1个2021/9/9数据结构17性质3:对于任何一棵二叉树，若度为2的结点数有n2个，则叶子数（n0）必定为n2＋1（即n0=n2+1）证明：∵二叉树中全部结点数n＝n0+n1+n2(叶子数＋1度结点数＋2度结点数)又∵二叉树中全部结点数n＝B+1(总分支数＋根结点)（除根结点外，每个结点必有一个直接前趋，即

8、一个分支）而总分支数B=n1+2n2(1度结点必有1个直接后继，2度结点必有2个)三式联立可得：n0+n1+n2=n1+2n2+1,即n0=n2+1物理意义：叶子数＝度为2结点数＋1讨论3：二