第六章-树和二叉树.

16.1树的定义和基本概念6.2二叉树6.2.1树的定义和基本术语6.2.2二叉树的性质6.2.3二叉树的存储结构6.3遍历二叉树6.3.1遍历二叉树6.3.2线索二叉树6.4树和森林6.4.1树的存储结构6.4.2森林与二叉树的转换6.4.3树和森林的遍历6.6赫夫曼树及其应用6.6.1最优二叉树（赫夫曼树）6.6.2赫夫曼编码第六章树和二叉树2重点：本章是重点章二叉树又是本章的重点内容要了解树的定义熟悉二叉树的定义、性质、存储结构、遍历、线索化树的存储结构、遍历以及树、森林与二叉树的转换，哈夫曼树及哈夫曼编码等内容第六章树和二叉树3熟练掌握二叉树的结构特性；熟悉二叉树的各种存储结构和特点熟练掌握遍历二叉树的各种操作；熟练应用二叉树遍历的具体算法理解线索化二叉树的实质，熟练掌握二叉树的线索化过程掌握森林与树的转换方法学会编写实现树的各种操作算法了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。第六章树和二叉树4难点：•二叉树的遍历及其有关应用第六章树和二叉树5•树形结构是一类非常重要的非线性数据结构，它是以分支关系定义的层次结构。它在现实世界中广泛存在，在计算机领域中也有广泛应用•本章重点讨论二叉树的存储结构及其各种操作，并研究树和森林与二叉树之间的转换关系。最后给出一些应用实例第六章树和二叉树66.1树的定义和基本术语•树（Tree）是n(n=0)个结点的有限集。具有如下的特征：在任意一棵非空树中：（1）有且仅有一个特定的称为根(Root)的结点；（2）除根结点外，其余结点可分为m（m=0）个互不相交的有限集T1,T2,…,Tm,其中每一个集合Ti本身又是一棵树，称为根的子树(SubTree)。76.1树的定义和基本术语ABCDEFGHIJKLMAABBCCDDEEFFGGHHIIJJKKLLMMT={A,B,C,D,E,F,G,H,I,J，K，L，M}A是根，其余结点可以划分为3个互不相交的集合：T1,T2,T3T1={B,E,F，K，L},T2={C,G},T3={D,H,I,J，M};它们是A的子树。对于T1，B是根，其余结点可以划分为2个互不相交的集合：T11={E，K，L}，T12={F}，T11,T12是B的子树。86.1树的定义和基本术语•树的表示方法：1)广义表表示法：(A(B(E(K,L),F),C(G),D(H(M),I,J)))3)凹入表IJFKLGMCCDBEAIIJJFFKKLLGGMMCCDBEA2)嵌套集合表示法96.1树的定义和基本术语1）树中只有根结点没有前趋；2）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；4）除根外的其他结点，都存在唯一条从根到该结点的路径；5）树是一种分枝结构,除了一个称为根结点外,每个元素都有且仅有一个直接前趋（双亲节点），有且仅有零个或多个直接后继（孩子结点）。从逻辑结构看：P118图6.1..\数据结构教材--C语言版.pdfABCDEFGHIJKLMAABBCCDDEEFFGGHHIIJJKKLLMM106.1树的定义和基本术语•有向树：１）有确定的根；２）树根和子树根之间为有向关系•有序树和无序树的区别在于：看子树之间是否存在次序（从左至右有序性，即不能互换）关系116.1树的定义和基本术语•基本术语结点：数据元素+若干指向子树的分支结点的度：子树分支的个数(出度)树的度：树中所有结点的度的最大值叶子结点：度为零的结点分支结点：度大于零的结点路径：从根到结点的通路孩子结点、双亲结点、兄弟结点祖先结点、子孙结点ABCDEFGHIJKLMAABBCCDDEEFFGGHHIIJJKKLLMM126.1树的定义和基本术语结点的层次：假设根结点的层次为1,第l层的结点的层次为l树的深度：树中叶子结点所在的最大层次森林：是m（m≥0）棵互不相交的树的集合•任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点，F被称为子树森林136.1树的定义和基本术语4146.1树的定义和基本术语树和线性结构的比较线性结构树结构第一个数据元素根结点(无前驱)(无前驱)最后一个数据元素多个叶子结点(无后继)(无后继)其它数据元素树中其它结点(一个前驱、一个后继)(一个前驱、多个后继)156.1树的定义和基本术语•抽象数据类型树的定义P118ADTTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；否则:(1)在D中存在唯一的称为根的数据元素root,(2)当结点个数n1时，除跟外的其余结点可分为m(m0)个互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。166.1树的定义和基本术语基本操作：插入：InitTree(&T);CreateTree(&T,definition);Assign(T,cur_e,value);InsertChild(&T,&p,i,c);删除：ClearTree(&T);DestroyTree(&T);DeleteChild(&T,&p,i);DestroyTree(&T);176.1树的定义和基本术语•树的基本运算通常有以下几种：1.InitTree(&T)//创建一棵空树；2.BiTreeEmpty(T)//判断某棵树是否为空；3.Root(T)//求树根结点，若为空树，则返回一特殊值；4.Parent(T,e)//求树中某个指定结点的父结点，当指定结点为根时，返回一特殊值；5.LeftChild(T,e)//求树中某个指定结点的左子结点，当指定结点为树叶时，它没有子女，则返回一特殊值；6.RightSibling(T,e)//求树中某个指定结点的右兄弟结点，当指定结点没有右兄弟时，返回一特殊值；7.TraverseTree(T,visit())//即按某种方式访问树中的所有结点，并使每个结点恰好被访问一次。186.2二叉树•二叉树的类型定义二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。它的每一个结点至多有两棵子树，并且子树有左右次序之分，不能随意颠倒(即二叉树是有序树)。二叉树抽象数据类型定义：P121ADTBinaryTree..\数据结构教材--C语言版.pdf•二叉树的五种基本形态196.2二叉树•二叉树的主要基本操作：查找：Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);//返回兄弟结点BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());//层次遍历每个结点206.2二叉树•二叉树的主要基本操作：插入：InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);//给出T的定义InsertChild(T,p,LR,c);//根据LR为0或1，c在P指向结点的左或右子树位置插入删除：ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);216.2二叉树•二叉树的重要特性：性质1：在二叉树的第i层上至多有2i-1个结点(i≥1)[证明用数学归纳法]P123..\数据结构教材--C语言版.pdf性质2：深度为k的二叉树上至多含2k-1个结点（k≥1）[证明用求等比级数前k项和的公式]P124226.2二叉树性质3：对任何一棵二叉树，若他含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1证：设n1为二叉树中度为1的结点数。则有结点总数n=n0+n1+n2再看二叉树中的分支数。除了根结点外，其余结点都有一个分支进入，设B为分支总数，则n=B+1。由于这些分支都是由分支为1或2的结点发出的，因此有：B=n1+2n2于是有n=n1+2n2+1n1+2n2+1=n0+n1+n2=n0=n2+1236.2二叉树•两类特殊的二叉树：P125..\数据结构教材--C语言版.pdf•满二叉树：除树叶之外，一棵二叉树的任何结点，都有两棵非空子树，则此二叉树称作“满二叉树”（离散数学中称此树是“正则的”）。指的是深度为k且含有2k-1个结点的二叉树•完全二叉树：如果一棵二叉树至多只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则此二叉树称为“完全二叉树”。完全二叉树不一定是满二叉树。树中所含的n个结点和满二叉树中编号为1至n的结点一一对应24满二叉树的特点：(1)每一层结点数都达到最大值。即对给定深度，它是具有最多结点数的二叉树(2)满二叉树中不存在度数为1的结点,且树叶都在最下一层上6.2二叉树25完全二叉树特点：（1）满二叉树是完全二叉树，完全二叉树不一定是满二叉树。（2）叶子结点只可能在层次最大的两层上出现；（3）对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次为必l或l＋1。6.2二叉树266.2二叉树276.2二叉树性质4：具有n个结点的完全二叉树的深度为log2n+1证：假设深度为k，则根据性质2和完全二叉树的定义有2k-1-1n=2k-1或2k-1=n2k于是k-1=log2nk因k是整数，所以k=+1n2log286.2二叉树性质5：对应P125图6.4a，b..\数据结构教材--C语言版.pdf若对含n个结点的二叉树从上到下且从左至右进行1至n的编号，则对二叉树中任意一个编号为i的结点：(1)若i=1，则该结点是二叉树的根，无双亲,否则，编号为i/2的结点为其双亲结点;(2)若2in，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；(3)若2i+1n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。296.2二叉树•二叉树的存储结构一、二叉树的顺序存储表示用一组地址连续的存储单元依次自上而下、自左而右存储完全二叉树的结点。对于一般树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应分量中（如下图）306.2二叉树316.2二叉树完全二叉树的数组表示一般二叉树的数组表示326.2二叉树#defineMAXNODE100/*定义二叉树中结点的最大个数*/typedefstructSeqBTree/*顺序树类型定义*/{DataTypenodelist[MAXNODE];intn;/*改造成完全二叉树后，结点的个数*/}SeqBTree,*PSeqBTree;显然，这种顺序存储结构仅适用于完全二叉树。因为，在最坏的情况下，一个深度为k且只有k个结点的单支树（树中不存在度为2的结点）却需要长度为2k-1的一维数组。336.2二叉树由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。单支树346.2二叉树二、二叉树链式存储结构由二叉树的定义可知，二叉树的结点由一个数据元素和两个分支构成，因此在表示时，至少需要包含三个域：数据域和左、右指针域。利用这种结点结构所得的二叉树存储结构称为二叉链表。P126图6.7：..\数据结构教材--C语言版.pdf356.2二叉树366.2二叉树1.二叉链表存储表示P127..\数据结构教材--C语言版.pdf376.2二叉树templateclassElemclassBiTreeNode//二叉树的结点{protected:BiTreeNodeElem*lchild;//指向左子树的指针BiTreeNodeElem*rchild;//指向右子树的指针public:Elem*data;BiTreeNode(con