第六章树和二叉树(裁剪)最新

1第6章树和二叉树•6.1树的定义和基本术语•6.2二叉树•6.3遍历二叉树和线索二叉树•6.4树和森林•6.6赫夫曼树及其应用本章要点深入掌握树的相关概念、树的表示和树的性质深入掌握二叉树的相关概念、二叉树的性质和二叉树的存储结构深入掌握二叉树运算的实现过程掌握树和森林的相互转换过程深入掌握赫夫曼树的构造过程和赫夫曼编码灵活应用二叉树的特点解决复杂的应用问题难点：赫夫曼树的构造过程和赫夫曼编码重点：1、树和二叉树的相关概念、性质2、树和二叉树的存储结构及其基本运算的实现3、赫夫曼树的构造过程和赫夫曼编码本章要点：236.1树的定义和基本术语一.树的抽象数据类型定义二.树的基本术语46.1树的定义和基本术语一.树的抽象数据类型定义1.树的定义树是由n(n0)个结点组成的有限集合。如果n=0，称为空树；如果n0，则:有且只有一个特定的称之为根(root)的结点，它只有后继，但没有前驱；除根以外的其它结点划分为m(m0)个互不相交的有限集合T1,T2,…,Tm，每个集合本身又是一棵树，并且称之为根的子树(SubTree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个后继。56.1树的定义和基本术语一.树的抽象数据类型定义2.树的表示方法图6.1树的示例66.1树的定义和基本术语一.树的抽象数据类型定义2.树的表示方法(a)嵌套集合表示法(b)广义表表示法(c)凹入表示法76.1树的定义和基本术语二.树的基本术语结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支结点拥有的分支个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM86.1树的定义和基本术语二.树的基本术语(从根到结点的)路径：孩子结点、双亲结点、兄弟结点、堂兄弟祖先结点、子孙结点结点的层次:由从根到该结点所经分支和结点构成。假设根结点的层次为1,第l层的结点的子树根结点的层次为l+1ABCDEFGHIJMKL树的深度：树中叶子结点所在的最大层次96.1树的定义和基本术语二.树的基本术语有序树：是指树中结点的各子树从左至右是有次序的（不能互换），否则称为无序树。森林：是m（m≥0）棵互不相交的树的集合。106.2二叉树二.二叉树的操作三.二叉树的性质四.二叉树的存储结构一.二叉树的定义116.2二叉树一.二叉树的定义一棵二叉树是结点的一个有限集合，该集合（1）或者为空，（2）或者是由一个根结点组成（3）或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。126.2二叉树一.二叉树的定义ABCDEFGHK根结点左子树右子树特点：1）每个结点的度≤2；2）是有序树6.2二叉树一.二叉树的定义图6.3二叉树的五种不同形态136.2二叉树二.二叉树的操作14(1)InitBiTree(&T)(2)DestroyBiTree(&T)(3)CreateBiTree(&T，definition)(4)ClearBiTree(&T)(5)BiTreeEmpty(T)(6)BiTreeDepth(T)(7)Root(t)(8)Value(T,e)(9)Assign(T,&e,value)(10)Parent(T,e)(11)LeftChild(T,e)(12)RightChild(T,e)(13)InsertChild(T,p,LR,c)(14)DeleteChild(T,p,LR)(15)PreOrderTraverse(T,Visit())(16)InOrderTraverse(T,Visit())(17)PostOrderTraverse(T,Visit())……6.2二叉树三.二叉树的性质15性质1若二叉树的层次从1开始,则在二叉树的第i层最多有2i-1个结点。(i1)[证明用数学归纳法]性质2深度为k的二叉树最多有2k-1个结点。(k1)[证明用求等比级数前k项和的公式]6.2二叉树三.二叉树的性质16性质3对任何一棵二叉树,如果其叶结点个数为n0,度为2的非叶结点个数为n2,则有n0＝n2＋1证明：若设度为1的结点有n1个，总结点个数为n，总边数为e，则根据二叉树的定义，n=n0+n1+n2e=2n2+n1=n–1因此，有2n2+n1=n0+n1+n2–1n2=n0-1n0=n2+16.2二叉树三.二叉树的性质17定义1满二叉树(FullBinaryTree)一棵深度为k且有2k-1个结点的二叉树称为满二叉树。6.2二叉树三.二叉树的性质18定义2完全二叉树(CompleteBinaryTree)深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。或者：若设二叉树的深度为h，则共有h层。除第h层外，其它各层(0h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点。6.2二叉树三.二叉树的性质19完全二叉树的特点是：1）只允许最后一层有空缺结点且空缺在右边，即叶子结点只能在层次最大的两层上出现；2）对任一结点，如果其右子树的深度为l，则其左子树的深度必为l或l+1。6.2二叉树三.二叉树的性质20性质4具有n个结点的完全二叉树的深度为log2n+1证明：设完全二叉树的深度为k，则有2k-1-1n2k-12k-1n2k取对数k-1log2nk因为k为整数，所以k=log2n+16.2二叉树三.二叉树的性质21性质5如果将一棵有n个结点的完全二叉树的结点按层序(自顶向下，同一层自左向右）连续编号1,2,…,n，然后按此结点编号将树中各结点顺序地存放于一个一维数组中,并简称编号为i的结点为结点i(1in)。则有以下关系：若i=1,则i是二叉树的根，无双亲;若i1,则i的双亲为i/2若2*in,则i无左孩子；否则其左孩子结点为2i，若2*i+1n,则i无右孩子，否则其右孩子结点为2i+1，线性结构树形结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)双亲在同一层的结点ABCDEFGHIJKLM结点A的度：结点B的度：结点M的度：叶子：结点A的孩子：结点B的孩子：结点I的双亲：结点L的双亲：结点B，C，D为兄弟结点K，L为兄弟树的度：结点A的层次：结点M的层次：树的深度：结点F，G为堂兄弟结点A是结点F，G的祖先结点B的子孙：320B，C，DE，F3K，L，F，G，M，I，JDE14例E，K，L，F4思考：具有3个结点的二叉树有多少种形态？例：112345678910121i=6其双亲为|i/2|=3；其左孩子为2*i=12;i=1是树的根,无双亲;其左孩子为2*i=2,右孩子为2*i+1=3.∵2*i=18122*i+1=1912∴其无左、右孩子。∵2*i+1=1312∴其无右孩子。i=9其双亲为|i/2|=4；6.2二叉树四、二叉树的存储结构26顺序存储链式存储6.2二叉树四、二叉树的存储结构271.顺序存储结构（数组表示）顺序存储二叉树的具体方法是：在一棵具有n个结点的完全二叉树中，从根结点开始编号为1，自上到下，每层自左至右地给所有结点编号，这样可以得到一个反映整个二叉树结构的线性序列；然后将完全二叉树上编号为i的结点依次存储在一维数组中下标为i-1的元素中。6.2二叉树四、二叉树的存储结构281.顺序存储结构（数组表示）#defineMAX_TREE_SIZE100typedefTElemTypeSqBiTree[MAX_TREE_SIZE];SqBiTreebt;二叉树的顺序存储表示6.2二叉树四、二叉树的存储结构291.顺序存储结构（数组表示）完全二叉树的数组表示一般二叉树的数组表示6.2二叉树四、二叉树的存储结构301.顺序存储结构（数组表示）由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。一棵深度为k且只有k个结点的单支树需要长度为2K-1的一维数组单支树6.2二叉树四、二叉树的存储结构312.链式存储结构链式存储是使用链表来存储二叉树中的数据元素，链表中的一个结点相应地存储二叉树中的一个结点。常见的二叉树的链式存储结构有两种：二叉链表和三叉链表。6.2二叉树四、二叉树的存储结构322.链式存储结构二叉链表是指链表中的每个结点包含两个指针域和一个数据域，分别用来存储指向二叉树中结点的左右孩子的指针及结点信息。三叉链表是指链表中的每个结点包含三个指针域和一个数据域，相比二叉链表多出的一个指针域则用来指向该结点的双亲结点。6.2二叉树四、二叉树的存储结构332.链式存储结构6.2二叉树四、二叉树的存储结构342.链式存储结构typedefstructBiTNode{TElemTypedata;StructBiTNode*lchild,*rchild;}BiTNode,*BiTree;二叉链表存储表示6.2二叉树四、二叉树的存储结构352.链式存储结构二叉树链表表示的示例6.3遍历二叉树和线索二叉树36遍历二叉树线索二叉树“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。遍历：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。即找一个完整而有规律的走法，得到树中所有结点的一个线性排列。“访问”的含义可以很广，如：输出结点的信息等。6.3遍历二叉树和线索二叉树一、遍历二叉树6.3遍历二叉树和线索二叉树一、遍历二叉树38遍历的结果：产生一个关于结点的线性序列。设访问根结点记作D，遍历根的左子树记作L遍历根的右子树记作R则可能的遍历次序有：先序DLR，逆先序DRL中序LDR，逆中序RDL后序LRD，逆后序RLD6.3遍历二叉树和线索二叉树一、遍历二叉树39先序遍历(PreorderTraversal)先序遍历二叉树算法的框架是若二叉树为空，则空操作；否则访问根结点(D)；先序遍历左子树(L)；先序遍历右子树(R)。ADBCDLRADLRDLRBDCDLR先序遍历序列：ABDC先序遍历:6.3遍历二叉树和线索二叉树一、遍历二叉树41中序遍历(InorderTraversal)中序遍历二叉树算法的框架是若二叉树为空，则空操作；否则中序遍历左子树(L)；访问根结点(D)；中序遍历右子树(R)。ADBCLDRBLDRLDRADCLDR中序遍历序列：BDAC中序遍历:6.3遍历二叉树和线索二叉树一、遍历二叉树43后序遍历(PostorderTraversal)后序遍历二叉树算法的框架是若二叉树为空，则空操作；否则后序遍历左子树(L)；后序遍历右子树(R)；访问根结点(D)。ADBCLRDLRDLRDADCLRD后序遍历序列：DBCA后序遍历:BABCDEFGHK分析：先序序列：中序序列：后序序列：ABCDEFGHKBDCAEHGKFDCBHKGFEA-+/a*b-efcd先序遍历：中序遍历：后序遍历：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef47由二叉树的先序序列和中序序列可唯一地确定一棵二叉树。例,先序序列{ABHFDECKG}和中序序列{HBDFAEKCG},构造二叉树过程如下：6.3遍历二叉树和线索二叉树一、遍历二叉树48思考：已知二叉树的先序序列和后序序列，问能否唯一确定这棵二叉树？遍历算法的递归描述voidPreOrder(BiTreeT,void(*Visit)(TElemTypee)){//先序遍历二叉树if(T){Visit(T-data);//访问结点PreOrder(T-lchild,Visit);//遍历左子树PreOrder(T-rchild,Visit);//遍历右子树}}voidpre(BiTreet){if(t!=NULL){prin