第5章树和二叉树ss.ppt

树的逻辑结构树的存储结构二叉树的逻辑结构二叉树的存储结构及实现树、森林与二叉树的转换哈夫曼树,第 5 章 树和二叉树,本章的主要内容是,树的定义,树：n（n0）个结点的有限集合。当n0时，称为空树；任意一棵非空树满足以下条件：有且仅有一个特定的称为根的结点；当n1时，除根结点之外的其余结点被分成m（m0）个互不相交的有限集合T1,T2,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。,5.1 树的逻辑结构,树的定义是采用递归方法,(a)一棵树结构(b)一个非树结构(c)一个非树结构,5.1 树的逻辑结构,树的定义,树的应用举例文件结构,5.1 树的逻辑结构,树的基本术语,结点的度：结点所拥有的子树的个数。树的度：树中各结点度的最大值。,5.1 树的逻辑结构,5.1 树的逻辑结构,叶子结点：度为0的结点，也称为终端结点。分支结点：度不为0的结点，也称为非终端结点。,树的基本术语,孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点；兄弟：具有同一个双亲的孩子结点互称为兄弟。,5.1 树的逻辑结构,树的基本术语,路径：如果树的结点序列n1,n2,nk有如下关系：结点ni是ni+1的双亲（1=ik），则把n1,n2,nk称为一条由n1至nk的路径；路径上经过的边的个数称为路径长度。,5.1 树的逻辑结构,树的基本术语,祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙。,5.1 树的逻辑结构,树的基本术语,结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。树的深度：树中所有结点的最大层数，也称高度。,5.1 树的逻辑结构,树的基本术语,层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。,5.1 树的逻辑结构,树的基本术语,有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。,数据结构中讨论的一般都是有序树,5.1 树的逻辑结构,树的基本术语,森林：m(m0)棵互不相交的树的集合。,5.1 树的逻辑结构,树的基本术语,同构：对两棵树，若通过对结点适当地重命名，就可以使这两棵树完全相等（结点对应相等，结点对应关系也相等），则称这两棵树同构。,5.1 树的逻辑结构,树的基本术语,树结构和线性结构的比较,线性结构,树结构,无前驱,无双亲,无后继,无孩子,一个前驱,一个后继,一个双亲,多个孩子,一对一 一对多,5.1 树的逻辑结构,树的遍历操作,树的遍历：从根结点出发，按照某种次序访问树中所有结点，使得每个结点被访问一次且仅被访问一次。,如何理解访问?,抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。,如何理解次序?,树通常有前序（根）遍历、后序（根）遍历和层序（次）遍历三种方式。,5.1 树的逻辑结构,树结构（非线性结构）线性结构。,遍历的实质?,前序遍历,树的前序遍历操作定义为：若树为空，则空操作返回；否则 访问根结点；按照从左到右的顺序前序遍历根结点的每一棵子树。,5.1 树的逻辑结构,前序遍历序列：A B D E H I F C G,后序遍历,树的后序遍历操作定义为：若树为空，则空操作返回；否则 按照从左到右的顺序后序遍历根结点的每一棵子树；访问根结点。,5.1 树的逻辑结构,后序遍历序列：D H I E F B G C A,层序遍历,树的层序遍历操作定义为：从树的第一层（即根结点）开始，自上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。,5.1 树的逻辑结构,层序遍历序列：A B C D E F G H I,5.2 树的存储结构,实现树的存储结构，关键是什么?,树中结点之间的逻辑关系是什么?,一对多的关系存储结构的关键：如何表示结点的双亲和孩子,如何表示树中结点之间的逻辑关系。,双亲表示法,基本思想：用一维数组来存储树的各个结点（一般按层序存储），数组中的一个元素对应树中的一个结点，每个结点记录两类信息：结点的数据信息以及该结点的双亲在数组中的下标。,5.2 树的存储结构,template struct PNode T data;/数据域 int parent;/指针域，双亲在数组中的下标;,5.2 树的存储结构,树的双亲表示法实质上是一个静态链表。,双亲表示法中结点数据类型的定义,下标 data parent,5.2 树的存储结构,如何查找双亲结点？时间性能？,双亲表示法,5.2 树的存储结构,双亲表示法,如何查找孩子结点？时间性能？,下标 data parent,firstchild,下标 data parent,rightsib,5.2 树的存储结构,双亲表示法,如何查找兄弟结点？时间性能？,链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。,如何确定链表中的结点结构？,5.2 树的存储结构,孩子表示法-多重链表表示法,5.2 树的存储结构,缺点：浪费空间,链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。,如何确定链表中的结点结构？,5.2 树的存储结构,方案二：指针域的个数等于该结点的度,其中：data：数据域，存放该结点的数据信息；degree：度域，存放该结点的度；child1childd：指针域，指向该结点的孩子。,孩子表示法-多重链表表示法,5.2 树的存储结构,缺点：结点结构不一致,A 2,B 3,C 2,E 1,I 0,G 0,H 0,F 0,D 0,基本思想：把每个结点的孩子排列起来，看成是一个线性表，且以单链表存储，则n个结点共有 n 个孩子链表。这 n 个单链表共有 n 个头指针，这 n 个头指针又组成了一个线性表。为了便于进行查找采用顺序存储。最后，将存放 n 个头指针的数组和存放n个结点的数组结合起来，构成孩子链表的表头数组。,5.2 树的存储结构,特点：将每个结点的所有孩子放在一起，构成线性表。,孩子表示法-孩子链表表示法,012345678,下标 data firstchild,A B C D E F G H I,5.2 树的存储结构,struct CTNode int child;CTNode*next;,5.2 树的存储结构,template struct CBNode T data;CTNode*firstchild;,孩子链表表示法,012345678,下标 data firstchild,A B C D E F G H I,5.2 树的存储结构,如何查找孩子结点？,012345678,下标 data firstchild,A B C D E F G H I,5.2 树的存储结构,如何查找双亲结点？,012345678,下标 data firstchild,A B C D E F G H I,5.2 树的存储结构,如何查找兄弟结点？,孩子兄弟表示法,5.2 树的存储结构,某结点的第一个孩子是惟一的某结点的右兄弟是惟一的,template struct TNode T data;TNode*firstchild,*rightsib;,5.2 树的存储结构,结点结构,data：数据域，存储该结点的数据信息；firstchild：指针域，指向该结点第一个孩子；rightsib：指针域，指向该结点的右兄弟结点。,孩子兄弟表示法,5.2 树的存储结构,孩子兄弟表示法,如何查找兄弟结点？,5.2 树的存储结构,孩子兄弟表示法,如何查找孩子结点？,树的存储结构小结,顺序存储：本质上是静态指针双亲表示法链式存储：多重链表示法孩子链表表示法孩子兄弟表示法,二叉树的定义,二叉树是n（n0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。,5.3 二叉树的逻辑结构,结构简单，适合于计算机处理问题转化：将树转换为二叉树，从而利用二叉树解决树的有关问题。,研究二叉树的意义？,二叉树的特点：,每个结点最多有两棵子树；二叉树是有序的，其次序不能任意颠倒。,5.3 二叉树的逻辑结构,注意：二叉树和树是两种树结构。,二叉树的基本形态,5.3 二叉树的逻辑结构,5.3 二叉树的逻辑结构,具有3个结点的树和具有3个结点的二叉树的形态,二叉树和树是两种树结构。,特殊的二叉树,斜树1.所有结点都只有左子树的二叉树称为左斜树；2.所有结点都只有右子树的二叉树称为右斜树；3.左斜树和右斜树统称为斜树。,1.在斜树中，每一层只有一个结点；2.斜树的结点个数与其深度相同。,5.3 二叉树的逻辑结构,斜树的特点：,满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。,满二叉树的特点：,叶子只能出现在最下一层；只有度为0和度为2的结点。,5.3 二叉树的逻辑结构,特殊的二叉树,满二叉树,5.3 二叉树的逻辑结构,不是满二叉树，虽然所有分支结点都有左右子树，但叶子不在同一层上。,满二叉树在同样深度的二叉树中结点个数最多满二叉树在同样深度的二叉树中叶子结点个数最多,特殊的二叉树,完全二叉树对一棵具有n个结点的二叉树按层序编号，如果编号为i（1in）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。,5.3 二叉树的逻辑结构,特殊的二叉树,在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。,5.3 二叉树的逻辑结构,A,1,5,2,3,4,6,7,9,10,B,C,D,E,F,G,H,I,J,不是完全二叉树，结点10与满二叉树中的结点10不是同一个结点,特殊的二叉树,1.叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部；2.完全二叉树中如果有度为1的结点，只可能有一个，且该结点只有左孩子。3.深度为k的完全二叉树在k-1层上一定是满二叉树。,完全二叉树的特点,5.3 二叉树的逻辑结构,特殊的二叉树,二叉树的基本性质,性质5-1 二叉树的第i层上最多有2i-1个结点（i1）。,证明：当i=1时，第1层只有一个根结点，而 2i-1=20=1，结论显然成立。假定i=k（1ki）时结论成立，即第k层上至多有2k-1个结点，则 i=k+1时，因为第k+1层上的结点是第k层上结点的孩子，而二叉树中每个结点最多有2个孩子，故在第k+1层上最大结点个数为第k层上的最大结点个数的二倍，即22k-12k。结论成立。,5.3 二叉树的逻辑结构,性质5-2 一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点。,证明：由性质1可知，深度为k的二叉树中结点个数最多=2k-1；每一层至少要有一个结点，因此深度为k的二叉树，至少有k个结点。,5.3 二叉树的逻辑结构,二叉树的基本性质,性质5-3 在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有:n0n21。,证明:设n为二叉树的结点总数，n1为二叉树中度为1的结点数，则有：nn0n1n2 在二叉树中，除了根结点外，其余结点都有唯一的一个分枝进入，由于这些分枝是由度为1和度为2的结点射出的，一个度为1的结点射出一个分枝，一个度为2的结点射出两个分枝，所以有：nn12n21因此可以得到：n0n21。,5.3 二叉树的逻辑结构,二叉树的基本性质,5.3 二叉树的逻辑结构,在有n个结点的满二叉树中，有多少个叶子结点？,二叉树的基本性质,性质5-3 在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有:n0n21。,性质5-4 具有n个结点的完全二叉树的深度为 log2n+1。,5.3 二叉树的逻辑结构,证明：假设具有n个结点的完全二叉树的深度为k，根据完全二叉树的定义和性质2，有下式成立 2k-1 n 2k,最少结点数,最多结点数,完全二叉树的基本性质,5.3 二叉树的逻辑结构,证明：假设具有n个结点的完全二叉树的深度为k，根据完全二叉树的定义和性质2，有下式成立 2k-1 n 2k,完全二叉树的基本性质,性质5-5 对一棵具有n个结点的完全二叉树中从1开始按层序编号，则对于任意的序号为i（1in）的结点（简称为结点i），有：（1）如果i1，则结点i的双亲结点的序号为 i/2；如果i1，则结点i是根结点，无双亲结点。(2)如果2in，则结点i的左孩子的序号为2i；如果2in，则结点i无左孩子。(3)如果2i1n，则结点i的右孩子的序号为2i1；如果2i1n，则结点 i无右孩子。,5.3 二叉树的逻辑结构,完全二叉树的基本性质,对一棵具有n个结点的完全二叉树中从1开始按层序编号，则 结点i的双亲结点为 i/2；结点i的左孩子为2i；结点i的右孩子为2i1。,5.3 二叉树的逻辑结构,性质5表明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。,二叉树的遍历操作,二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。,二叉树遍历操作的目的？,5.3 二叉树的逻辑结构,二叉树的遍历方式：DLR、LDR、LRD、DRL、RDL、RLD,如果限定先左后右，则二叉树遍历方式有三种：前序：DLR中序：LDR后序：LRD,层序遍历：按二叉树的层序编号的次序访问各结点。,5.3 二叉树的逻辑结构,考虑二叉树的组成：,前序（根）遍历若二叉树为空，则空操作返回；否则：访问根结点；前序遍历根结点的左子树；前序遍历根结点的右子树。,5.3 二叉树的逻辑结构,前序遍历序列：A B D G C E F,二叉树的遍历操作,中序（根）遍历若二叉树为空，则空操作返回；否则：中序遍历根结点的左子树；访问根结点；中序遍历根结点的右子树。,5.3 二叉树的逻辑结构,中序遍历序列：D G B A E C F,二叉树的遍历操作,后序（根）遍历若二叉树为空，则空操作返回；否则：后序遍历根结点的左子树；后序遍历根结点的右子树。访问根结点；,5.3 二叉树的逻辑结构,后序遍历序列：G D B E F C A,二叉树的遍历操作,层序遍历二叉树的层次遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。,5.3 二叉树的逻辑结构,层序遍历序列：A B C D E F G,二叉树的遍历操作,5.3 二叉树的逻辑结构,-,-,/,+,*,a,b,c,d,e,f,二叉树遍历操作练习,前序遍历结果：-+a*b-c d/e f中序遍历结果：a+b*c-d-e/f后序遍历结果：a b c d-*+e f/-,5.3 二叉树的逻辑结构,若已知一棵二叉树的前序（或中序，或后序，或层序）序列，能否唯一确定这棵二叉树呢？,例：已知前序序列为ABC，则可能的二叉树有5种。,二叉树的遍历操作,5.3 二叉树的逻辑结构,例：已知前序遍历序列为ABC，后序遍历序列为CBA，则下列二叉树都满足条件。,若已知一棵二叉树的前序序列和后序序列，能否唯一确定这棵二叉树呢？,二叉树的遍历操作,若已知一棵二叉树的前序序列和中序序列，能否唯一确定这棵二叉树呢？怎样确定？,例如：已知一棵二叉树的前序遍历序列和中序遍历序列分别为ABCDEFGHI 和BCAEDGHFI，如何构造该二叉树呢?,5.3 二叉树的逻辑结构,二叉树的遍历操作,前序：A B C D E F G H I中序：B C A E D G H F I,前序：B C中序：B C,前序：D E F G H I中序：E D G H F I,前序：F G H I中序：G H F I,前序：D E F G H I中序：E D G H F I,顺序存储结构,二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置（下标）应能体现结点之间的逻辑关系父子关系。,如何利用数组下标来反映结点之间的逻辑关系?,完全二叉树和满二叉树中结点的序号可以唯一地反映出结点之间的逻辑关系。,5.4 二叉树的存储结构及实现,完全二叉树的顺序存储,5.4 二叉树的存储结构及实现,以编号为下标,二叉树的顺序存储,5.4 二叉树的存储结构及实现,以编号为下标,按照完全二叉树编号,一棵斜树的顺序存储会怎样呢？,深度为k的右斜树，k个结点需分配2k1个存储单元。,一棵二叉树改造后成完全二叉树形态，需增加很多空结点，造成存储空间的浪费。,5.4 二叉树的存储结构及实现,二叉树的顺序存储结构一般仅存储完全二叉树,二叉链表,基本思想：令二叉树的每个结点对应一个链表结点，链表结点除了存放与二叉树结点有关的数据信息外，还要设置指示左右孩子的指针。,结点结构：,其中，data：数据域，存放该结点的数据信息；lchild：左指针域，存放指向左孩子的指针；rchild：右指针域，存放指向右孩子的指针。,5.4 二叉树的存储结构及实现,template struct BiNode T data;BiNode*lchild,*rchild;,5.4 二叉树的存储结构及实现,二叉链表,二叉链表,5.4 二叉树的存储结构及实现,具有n个结点的二叉链表中，有多少个空指针？,二叉链表,5.4 二叉树的存储结构及实现,具有n个结点的二叉链表中，有n+1个空指针。,二叉链表存储结构的类声明,template class BiTree public:BiTree()root=NULL;BiTree(BiNode*root);BiTree();void PreOrder(BiNode*root);void InOrder(BiNode*root);void PostOrder(BiNode*root);void LeverOrder(BiNode*root);private:BiNode*root;void Creat(BiNode*root);void Release(BiNode*root);,5.4 二叉树的存储结构及实现,前序遍历递归算法,template void BiTree:PreOrder(BiNode*root)if(root=NULL)return;else coutdata;PreOrder(root-lchild);PreOrder(root-rchild);,5.4 二叉树的存储结构及实现,前序遍历算法的执行轨迹,template void BiTree:PreOrder(BiNode*root)if(root=NULL)return;else 1 coutdata;2 PreOrder(root-lchild);3 PreOrder(root-rchild);4,二叉树前序遍历的非递归算法的关键：在前序遍历过某结点的整个左子树后，如何找到该结点的右子树的根指针。解决办法：在访问完该结点后，将该结点的指针保存在栈中，以便以后能通过它找到该结点的右子树。,5.4 二叉树的存储结构及实现,前序遍历非递归算法,非递归前序遍历二叉树,栈是实现递归的最常用的结构思想：遇到一个结点，就访问该结点，并把此结点推入栈中，然后遍历它的左子树；遍历完它的左子树后，从栈顶托出这个结点，并按照它的右链接指示的地址再去遍历该结点的右子树结构。,访问结点序列:,A,栈S内容:,B,D,A,B,前序遍历的非递归实现,5.4 二叉树的存储结构及实现,A,D,B,C,访问结点序列:,A,栈S内容:,B,D,A,前序遍历的非递归实现,5.4 二叉树的存储结构及实现,A,D,B,C,D,访问结点序列:,A,栈S内容:,B,D,C,前序遍历的非递归实现,5.4 二叉树的存储结构及实现,A,D,B,C,C,1.栈s初始化；2.循环直到root为空且栈s为空 2.1 当root不空时循环2.1.1 输出root-data;2.1.2 将指针root的值保存到栈中；2.1.3 继续遍历root的左子树2.2 如果栈s不空，则2.2.1 将栈顶元素弹出至root；2.2.2 准备遍历root的右子树；,前序遍历非递归算法（伪代码）,5.4 二叉树的存储结构及实现,前序遍历非递归算法（伪代码）,template void BiTree:PreOrder(BiNode*root)SeqStack*s;while(root!=NULL|!s.empty()while(root!=NULL)coutdata;s.push=root;root=root-lchild;if(!s.empty()root=s.pop();root=root-rchild;,1.栈s初始化；2.循环直到root为空且栈s为空 2.1 当root不空时循环2.1.1 输出root-data;2.1.2 将指针root的值保存到栈中；2.1.3 继续遍历root的左子树2.2 如果栈s不空，则2.2.1 将栈顶元素弹出至root；2.2.2 准备遍历root的右子树；,前序遍历非递归算法（伪代码）,template void BiTree:PreOrder(BiNode*root)SeqStack*s;while(root!=NULL|!s.empty()while(root!=NULL)coutdata;s.push=root;root=root-lchild;if(!s.empty()root=s.pop();root=root-rchild;,前序遍历非递归算法（伪代码）,template void BiTree:PreOrder(BiNode*root)SeqStack*s;while(root!=NULL|!s.empty()while(root!=NULL)coutdata;s.push=root;root=root-lchild;if(!s.empty()root=s.pop();root=root-rchild;,if,二叉树的建立,为了建立一棵二叉树，将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值如“#”，以标识其为空，把这样处理后的二叉树称为原二叉树的扩展二叉树。,5.4 二叉树的存储结构及实现,如何由一种遍历序列生成该二叉树？,遍历是二叉树各种操作的基础，可以在遍历的过程中进行各种操作，例如建立一棵二叉树。,扩展二叉树的前序遍历序列:A B#D#C#,5.4 二叉树的存储结构及实现,二叉树的建立,设二叉树中的结点均为一个字符。假设扩展二叉树的前序遍历序列由键盘输入，root为指向根结点的指针，二叉链表的建立过程是：,5.4 二叉树的存储结构及实现,二叉树的建立,按前序扩展遍历序列输入结点的值如果输入结点值为“#”,则建立一棵空的子树否则，根结点申请空间，将输入值写入数据域中，以相同方法的创建根结点的左子树以相同的方法创建根结点的右子树递归方法,按前序扩展遍历序列输入输入节点的值如果输入节点之为“#”,则建立一棵空的子树否则，根结点申请空间，将输入值写入数据域中，以相同方法的创建根节点的左子树以相同的方法创建根节点的右子树递归方法,扩展二叉树的前序遍历序列:A B#D#C#,D,B,A,C,template BiTree:BiTree()root=creat()；template BiNode*BiTree:Creat()BiNode*root;cinch;if(ch=#)root=NULL;else root=new BiNode;root-data=ch;root-lchild=creat();root-rchild=creat();return root,5.4 二叉树的存储结构及实现,按前序扩展遍历序列输入输入节点的值如果输入节点之为“#”,则建立一棵空的子树否则，根结点申请空间，将输入值写入数据域中，以相同方法的创建根节点的左子树以相同的方法创建根节点的右子树递归方法,template BiTree:BiTree()root=creat()；template BiNode*BiTree:Creat()BiNode*root;cinch;if(ch=#)root=NULL;else root=new BiNode;root-data=ch;1 root-lchild=creat();2 root-rchild=creat();3 return root,5.4 二叉树的存储结构及实现,A B#D#C#,中序遍历递归算法,template void BiTree:InOrder(BiNode*root)if(root=NULL)return;else InOrder(root-lchild);coutdata;InOrder(root-rchild);,5.4 二叉树的存储结构及实现,后序遍历递归算法,template void BiTree:PostOrder(BiNode*root)if(root=NULL)return;else PostOrder(root-lchild);PostOrder(root-rchild);coutdata;,5.4 二叉树的存储结构及实现,层序遍历,5.4 二叉树的存储结构及实现,遍历序列：,A,A,B,C,B,D,C,E,F,G,D,E,F,G,层序遍历,队列Q初始化；2.如果二叉树非空，将根指针入队；3.循环直到队列Q为空 3.1 q=队列Q的队头元素出队；3.2 访问结点q的数据域；3.3 若结点q存在左孩子，则将左孩子指针入队；3.4 若结点q存在右孩子，则将右孩子指针入队；,5.4 二叉树的存储结构及实现,层序遍历二叉树,template void BiTree:LeverOrder(BiNode*root)front=rear=0;/采用顺序队列，并假定不会发生上溢if(root=NULL)return;Q+rear=root;while(front!=rear)q=Q+front;coutdata;if(q-lchild!=NULL)Q+rear=q-lchild;if(q-rchild!=NULL)Q+rear=q-rchild;,templatevoid BiTree:Release(BiNode*root)if(root!=NULL)Release(root-lchild);/释放左子树 Release(root-rchild);/释放右子树 delete root;,templateBiTree:BiTree(void)Release(root);,二叉树算法设计练习,遍历二叉树是二叉树各种操作的基础，遍历算法中对每个结点的访问操作可以是多种形式及多个操作，根据遍历算法的框架，适当修改访问操作的内容，可以派生出很多关于二叉树的应用算法。,void InOrder(BiNode*root)if(root=NULL)return;else InOrder(root-lchild);coutdata;InOrder(root-rchild);,二叉树算法设计练习,设计算法求二叉树的结点个数。,void Count(BiNode*root)/n为全局量并已初始化为0 if(root)Count(root-lchild);n+;Count(root-rchild);,统计叶子节点的数目,增加一个数据成员，leafcount,初值为0对树进行遍历。如果一个节点是叶子，则将leafcount+1；可以在前序、中序或后序的遍历过程中进行计算。算法分析从根节点出发判断根节点是否是叶子节点，如果是，则叶子数+1否则，在左子树中遍历，并统计叶子节点的数目，在右子树中进行遍历，并统计叶子节点的数目,template inline void BiTree:countleaf(BiTreeNode*root)if(root)if(root-lchild=0,计算树的高度,高度的定义max（左子树高度，右子树高度）+1算法分析从根节点出发开始计算，如果root=NULL,高度为0；如果root是叶子节点，则高度为1；其它情况下，分别计算左子树的高度；右子树的高度；返回max（左子树高度，右子树高度）+1递归的定义,计算树的高度,template int BiTree:cal_height(BiTreeNode*root)int lheight=0,rheight=0;if(root=0)return 0;if(root-lchild=0,lheight=cal_height(root-lchild);rheight=cal_height(root-rchild);if(lheightrheight)return lheight+1;else return rheight+1;,左右子树的交换,将每个节点的左、右子树进行交换可以在遍历过程中进行交换。算法分析从根出发开始操作如果要操作的节点是叶子或是空值，则不进行任何操作；如果要操作的节点不是叶子节点，则交换左右儿子对左子树进行处理对右子树进行处理,左右子树进行交换,template void Binarytree:jiaohuan(binarytreenode*root)binarytreenode*temp;if(root=0)return;elseif(root-lchild=0 else,temp=root-rchild;root-rchild=root-lchild;root-lchild=temp;jiaohuan(root-lchild);jiaohuan(root-rchild);,三叉链表,在二叉链表的基础上增加了一个指向双亲的指针域。,结点结构,其中：data、lchild和rchild三个域的含义同二叉链表的结点结构；parent域为指向该结点的双亲结点的指针。,5.4 二叉树的存储结构及实现,三叉链表,5.4 二叉树的存储结构及实现,三叉链表的静态链表形式,5.4 二叉树的存储结构及实现,二叉树的遍历运算是将二叉树中结点按一定规律线性化的过程。当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在遍历序列中的前驱和后继信息。要得到这些信息可采用以下两种方法：第一种方法是将二叉树遍历一遍，在遍历过程中便可得到结点的前驱和后继，但这种动态访问浪费时间；第二种方法是充分利用二叉链表中的空链域，将遍历过程中结点的前驱、后继信息保存下来。,5.4 二叉树的存储结构及实现,我们知道，在有n个结点的二叉链表中共有2n个链域，但只有n-1个有用的非空链域，其余n+1个链域是空的。我们可以利用剩下的n+1个空链域来存放遍历过程中结点的前驱和后继信息。,线索链表,线索：将二叉链表中的空指针域指向前驱结点和后继结点的指针被称为线索；线索化：使二叉链表中结点的空链域存放其前驱或后继信息的过程称为线索化；线索二叉树：加上线索的二叉树称为线索二叉树。,5.4 二叉树的存储结构及实现,5.4 二叉树的存储结构及实现,结点结构,线索链表,enum flag Child,Thread;template struct ThrNode T data;ThrNode*lchild,*rchild;flag ltag,rtag;,5.4 二叉树的存储结构及实现,线索链表,结点结构,二叉树的遍历方式有4种，故有4种意义下的前驱和后继，相应的有4种线索二叉树：前序线索二叉树 中序线索二叉树 后序线索二叉树 层序线索二叉树,5.4 二叉树的存储结构及实现,线索二叉树,5.5 树、森林与二叉树的转换,是哪些树结构的存储结构?,树和二叉树之间具有对应关系,5.5 树、森林与二叉树的转换,树和二叉树之间的对应关系 树：兄弟关系二叉树：双亲和右孩子 树：双亲和长子二叉树：双亲和左孩子,5.5 树、森林与二叉树的转换,1.兄弟加线.,树和二叉树之间的对应关系,5.5 树、森林与二叉树的转换,2.保留双亲与第一孩子连线,删去与其他孩子的连线.,树和二叉树之间的对应关系,1.兄弟加线.,3.顺时针转动,使之层次分明.,5.5 树、森林与二叉树的转换,树和二叉树之间的对应关系,2.保留双亲与第一孩子连线,删去与其他孩子的连线.,1.兄弟加线.,A,B,C,D,E,F,G,5.5 树、森林与二叉树的转换,树和二叉树之间的对应关系,ABEFCDG,ABEFCDG,树的前序遍历等价于二叉树的前序遍历！,5.5 树、森林与二叉树的转换,EFBCGDA,EFBCGDA,树的后序遍历等价于二叉树的中序遍历！,5.5 树、森林与二叉树的转换,森林转换为二叉树,将森林中的每棵树转换成二叉树；从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。,5.5 树、森林与二叉树的转换,5.5 树、森林与二叉树的转换,二叉树转换为树或森林,加线若某结点x是其双亲y的左孩子，则把结点x的右孩子、右孩子的右孩子、，都与结点y用线连起来；去线删去原二叉树中所有的双亲结点与右孩子结点的连线；层次调整整理由、两步所得到的树或森林，使之层次分明。,5.5 树、森林与二叉树的转换,5.5 树、森林与二叉树的转换,森林的遍历,森林有两种遍历方法：前序（根）遍历：前序遍历森林即为前序遍历森林中的每一棵树。后序（根）遍历：后序遍历森林即为后序遍历森林中的每一棵树。,5.5 树、森林与二叉树的转换,(1)先根序遍历:若森林 F 为空,返回；否则 访问 F 的第一棵树的根结点；先根次序遍历第一棵树的子树森林；先根次序遍历其它树组成的森林。,先根序 A B C D E F G H I K J,(2)后根序遍历：若森林 F 为空，返回；否则 后根次序遍历第一棵树的子树森林；访问 F 的第一棵树的根结点；后根次序遍历其它树组成的森林。,后根序 B C E D A G F KJ H,相关概念,叶子结点的权值：对叶子结点赋予的一个有意义的数值量。,二叉树的带权路径长度：设二叉树具有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和。记为：,WPL=,5.6 哈夫曼树及哈夫曼编码,哈夫曼树：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树。,例：给定4个叶子结点，其权值分别为2，3，4，7，可以构造出形状不同的多个二叉树。,5.6 哈夫曼树及哈夫曼编码,WPL=32 WPL=41 WPL=30,哈夫曼树的特点：1.权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。2.只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点.,5.6 哈夫曼树及哈夫曼编码,2,3,4,7,WPL=32 WPL=41 WPL=30,2,3,4,7,7,4,2,3,哈夫曼算法基本思想：初始化：由给定的n个权值w1，w2，wn构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合FT1，T2，Tn；选取与合并：在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和；删除与加入：在F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到F中；重复、两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。,5.6 哈夫曼树及哈夫曼编码,第1步：初始化,W2，3，4，5 哈夫曼树的构造过程,5.6 哈夫曼树及哈夫曼编码,第2步：选取与合并,第3步：删除与加入,W2，3，4，5 哈夫曼树的构造过程,5.6 哈夫曼树及哈夫曼编码,重复第2步,5,4,3,2,5,重复第3步,W2，3，4，5 哈夫曼树的构造过程,5.6 哈夫曼树及哈夫曼编码,重复第2步,重复第3步,哈夫曼算法的存储结构,struct element int weight;int lchild,rchild,parent;,5.6 哈夫曼树及哈夫曼编码,伪代码,数组huffTree初始化，所有元素结点的双亲、左 右孩子都置为-1；2.数组huffTree的前n个元素的权值置给定值wn；3.进行n-1次合并 3.1 在二叉树集合中选取两个权值最小的根结点，其下标分别为i1,i2；3.2 将二叉树i1、i2合并为一棵新的二叉树k；,5.6 哈夫曼树及哈夫曼编码,weight parent lchild rchild,-1-1-1-1-1-1-1-1-1-1-1-1-1-1