数据结构与算法—赵玉兰 第4章 树与二叉树VIP专享VIP免费

计算机学院软件工程系4.1树的定义和相关术语4.2二叉树4.3树和森林4.4森林与二叉树的关系4.5Huffman树与编码计算机学院软件工程系4.1树的定义和相关术语4.2二叉树4.3树和森林4.4森林与二叉树的关系4.5Huffman树与编码计算机学院软件工程系内蒙古大学理工学院计算机学院生命科学学院外国语学院人文学院数学系物理系电子系计算机系计算中心网络中心汉语系历史系哲学系生物系环境系动物中心生物工程中心资源所英语系日语系行政机构树形结构是一种非线性结构，应用十分广泛。如：行政机构、目录、家谱等。计算机学院软件工程系磁盘目录计算机学院软件工程系红楼梦家谱计算机学院软件工程系树和森林的概念树和森林的概念树的定义树的定义树是由树是由nn((nn≥≥0)0)个结点组成的有限集合。如果个结点组成的有限集合。如果nn=0=0，称为，称为空树空树；如果；如果nn>0>0，则，则有一个特定的称之为有一个特定的称之为根根(root)(root)的结点，它只的结点，它只有直接后继，但没有直接前驱；有直接后继，但没有直接前驱；除根以外的其他结点被划分到除根以外的其他结点被划分到mm((mm≥≥0)0)个个互不相交的子集互不相交的子集TT11,,TT22,…,,…,TTmm中，每个子集中，每个子集又都构成一棵树，称之为又都构成一棵树，称之为根的子树根的子树(subtree)(subtree)。。计算机学院软件工程系树的特点树的特点每棵子树的根结点有且仅有一个直接前每棵子树的根结点有且仅有一个直接前驱，但可以有驱，但可以有00个或多个直接后继。个或多个直接后继。树是一种典型的“树是一种典型的“层次结构层次结构”，体现出”，体现出““一对多一对多”的关系。”的关系。ACGBDEFKLHMIJ计算机学院软件工程系例4.1:Tree=(D,R)D={Book,C1,C2,C3,S1.1,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-Section计算机学院软件工程系基本术语：主要来源于家谱和自然界中的树。双亲、子女（parent,child）：若R，则称a是b的双亲，b是a的子女(孩子);结点度（degree）：结点所拥有的子女数；叶子（leaf）：度为0的结点；分枝结点（branchnode）：度大于0的结点；树的度：树中最大的结点的度；ABCDEFGHIJMKL计算机学院软件工程系结点所在的层次(level)：根在第1层，其它任一结点所在的层是其双亲的层数加1。深度或高(depth)：树中结点的最大层数。兄弟(sibling)：同一双亲的结点间互称兄弟。堂兄弟(cousin)：同层的非兄弟结点互称堂兄弟。423ABCDEFGHIJMKL1计算机学院软件工程系祖先（descendant）、子孙（ancestor）：一个结点是它所有子树中结点的祖先，而子树中的这些结点都是它的子孙。路径（path）：是一个结点序列n1,n2,n3,…,nk，并且前1个结点是后1个结点的双亲；它的长度是k-1。有序树（orderedtree）：将树中每个结点的各子树看出是从左到右是有次序的(不能互换)；否则是无序树。ABCACB无序树有序树计算机学院软件工程系ABCDEFGHIJKLM结点A、B、C的度分别为：3、2、1叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先计算机学院软件工程系森林(Forest)：m(m≥0)棵互不相交的树的集合。FGABCDEHIJK由三棵树构成的森林A根BCDEFGHIJK森林由根的各子树构成的森林计算机学院软件工程系4.1树的定义和相关术语4.2二叉树4.3树和森林4.4森林与二叉树的关系4.5Huffman树与编码计算机学院软件工程系二叉树二叉树(BinaryTree)(BinaryTree)二叉树的五种不同形态：二叉树的五种不同形态：二叉树的定义二叉树的定义一棵二叉树是一个结点的有限一棵二叉树是一个结点的有限集合，该集合或者为空，或者是由一个根集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、结点加上...