数据结构与算法—赵玉兰 第4章 树与二叉树.ppt

《数据结构与算法—赵玉兰 第4章 树与二叉树.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、4.1树的定义和相关术语4.2二叉树4.3树和森林4.4森林与二叉树的关系4.5Huffman树与编码14.1树的定义和相关术语4.2二叉树4.3树和森林4.4森林与二叉树的关系4.5Huffman树与编码2内蒙古大学理工学院计算机学院生命科学学院外国语学院人文学院数学系物理系电子系计算机系计算中心网络中心汉语系历史系哲学系生物系环境系动物中心生物工程中心资源所英语系日语系行政机构树形结构是一种非线性结构，应用十分广泛。如：行政机构、目录、家谱等。3磁盘目录4红楼梦家谱5树和森林的概念树的定义树是由n

2、(n≥0)个结点组成的有限集合。如果n=0，称为空树；如果n>0，则有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；除根以外的其他结点被划分到m(m≥0)个互不相交的子集T1,T2,…,Tm中，每个子集又都构成一棵树，称之为根的子树(subtree)。6树的特点每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。树是一种典型的“层次结构”，体现出“一对多”的关系。ACGBDEFKLHMIJ7例4.1:Tree=(D,R)D={Book,C1,C2,C3,S1.1,

3、S1.2,S2.1,S2.2,S2.3,S2.1.1,S2.1.2}R={,,,,,,,,,}BookC1C2C3S1.1S1.2S2.1S2.2S2.3S2.1.1S2.1.2ChapterSectionSub-Section8基本术语：主要来源于家谱和自然界中的树。双亲、子女（parent,child）：

4、若R，则称a是b的双亲，b是a的子女(孩子);结点度（degree）：结点所拥有的子女数；叶子（leaf）：度为0的结点；分枝结点（branchnode）：度大于0的结点；树的度：树中最大的结点的度；ABCDEFGHIJMKL9结点所在的层次(level)：根在第1层，其它任一结点所在的层是其双亲的层数加1。深度或高(depth)：树中结点的最大层数。兄弟(sibling)：同一双亲的结点间互称兄弟。堂兄弟(cousin)：同层的非兄弟结点互称堂兄弟。423ABCDEFGHIJMKL110

5、祖先（descendant）、子孙（ancestor）：一个结点是它所有子树中结点的祖先，而子树中的这些结点都是它的子孙。路径（path）：是一个结点序列n1,n2,n3,…,nk，并且前1个结点是后1个结点的双亲；它的长度是k-1。有序树（orderedtree）：将树中每个结点的各子树看出是从左到右是有次序的(不能互换)；否则是无序树。ABCACB无序树有序树11ABCDEFGHIJKLM结点A、B、C的度分别为：3、2、1叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，

6、F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先12森林(Forest)：m(m≥0)棵互不相交的树的集合。FGABCDEHIJK由三棵树构成的森林A根BCDEFGHIJK森林由根的各子树构成的森林134.1树的定义和相关术语4.2二叉树4.3树和森林4.4森林与二叉树的关系4.5Huffman树与编码14二叉树(BinaryTree)二叉树的五种不同形态：二叉树的定义一棵二叉树是一个

7、结点的有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。LRLR15自然界很神奇！164.2二叉树4.2.1二叉树的ADT描述4.2.2二叉树的遍历4.2.3二叉树的性质4.2.4二叉树的实现4.2.5二叉树遍历的非递归实现4.2.6线索二叉树174.2二叉树4.2.1二叉树的ADT描述4.2.2二叉树的遍历4.2.3二叉树的性质4.2.4二叉树的实现4.2.5二叉树遍历的非递归实现4.2.6线索二叉树18二叉树的抽象数据类型ADTBinaryTree

8、{Data是有限个结点的集合D。当D非空时，其中有一根结点t，其余结点被分为t的左子树和右子树。OperationsConstructorProcess:建立一棵空二叉树DeleteProcess:删除二叉树19IsEmptyProcess:判断二叉树是否是空Output:若二叉树为空，则返回true,否则返回falseSizeProcess:计算二叉树的结点数sizeOutput:sizeHeightProcess:计算二叉树的高度heightOutp