数据结构-树与二叉树.ppt

Chapter 6Tree&Binary Tree,教,学,内,容,1、树和森林的概念2、二叉树的定义、性质及运算；3、二叉树的存储结构 4、遍历二叉树、树、森林5、森林与二叉树的转换6、哈夫曼树、哈夫曼编码,树型结构（非线性结构）,结点之间有分支,具有层次关系,例,自然界:树,人类社会,家谱,院系组织机构,树的概念,树的定义 树是 n(n 0)个结点的有限集。若n=0，称为空树；若 n 0，则它满足如下两个条件：,有且仅有一个称之为根(Root)的结点。当n 1，除根以外的其它结点分为 m(m 0)个互不相交的有限集 T1,T2,Tm，其中每个集合又是一棵符合本定义的树，并且称为根的子树。,例如,A,只有根结点的树,有13个结点的树,A是根；其余数据元素分成三个互不相交的子集，T1=B,E,F,K,L；T2=C,G；T3=D,H,I,J,M,T1,T2,T3都是根A的子树，且本身也是一棵树。,根结点,T1,R=,树结构和线性结构作如下对照：,树的基本术语,结点结点的度叶子结点分支结点,儿子结点父亲结点兄弟结点祖先结点,树的度结点的层次树的深度森林,有序树,子树之间存在确定的次序关系,无序树,子树之间不存在确定的次序关系,家族树就属于有序树。,森林,是m(m0)棵互不相交的树的集合,root,给森林中的各子树加上一个父亲结点,森林就变成了树。,T3,T2,T1,二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交叉的二叉树组成。,二叉树,为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。,根结点,右子树,左子树,(a)空二叉树,(b)根和空的 左右子树,(c)根和左子树,(d)根和右子树,(e)根和左右子树,注：虽然二叉树与树概念不同，但有关树的基本术语对二叉树都适用。,二叉树的五种基本形态,性质1 在二叉树的第 i 层上至多有 2i 1个结点。(i 1),证明：当i=1时，只有根结点，2i-1=20=1。假设对所有j，ij1，命题成立，即第j层上至多有2 j-1 个结点。由归纳假设第i-1 层上至多有 2i2个结点。二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2*2i2=2i-1。,二叉树的重要特性,性质2 深度为 k 的二叉树至多有 2 k-1个结点，其中k 1。证明：由性质1可见，深度为k的二叉树的最大结点数为,20+21+2k-1=2k-1,性质3 对任何一棵二叉树T,如果其叶子结点数为 n0,度为2的结点数为 n2,则n0n21。,证明：n=n0+n1+n2 e=n 1=2n2+n1 因此，2n2+n1=n0+n1+n2-1 n0=n2+1,满二叉树(Full Binary Tree)定义1:一棵深度为k且有2 k-1个结点的二叉树称为满二叉树。,两种特殊形态的二叉树,特点:每一层上的结点数都达到最大,叶子全部在最底层,非完全二叉树,完全二叉树(Complete Binary Tree)若设二叉树的深度为h，除第 h 层外，其它各层(0 h-1)的结点数都达到最大值，第 h 层从右向左连续缺若干结点。,完全二叉树,性质4 具有 n(n 0)个结点的完全二叉树的深度为log2(n)1。,证明：设完全二叉树的深度为 h，则根据性质2和完全二叉树的定义有2h-1-1 n 2h-1,取对数 h1 log2n h，又h是整数因此有 h=log2(n)1,性 质 5,若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：,哪个是完全二叉树,(1)若i=1，则该结点是二叉树的根，否 则，编号为i/2 的结点为其父亲结点。(2)若2in，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点。(3)若2i+1n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子 结点。,3.深度为9的二叉树中至少有 个结点。)9)8)91,2.深度为的二叉树的结点总数，最多为 个。)k-1)log2k)k)k,1.树中各结点的度的最大值称为树。)高度)层次)深度)度,D,C,C,课堂练习：,二、二叉树的链式存储表示,一、二叉树的顺序存储表示,6.3 二叉树的存储结构,顺序存储表示,用一组地址连续的存储单元存储二叉树中的数据元素。将完全二叉树上编号为i的结点元素存储在一维数组中下标为i-1的分量中,1,2,3,4,5,6,7,10,8,9,1,练习,2,4,1,6,3,5,对于一般的非完全二叉树不能直接使用二叉树的顺序存储结构。,可以首先在非完全二叉树中增添一些并不存在的空结点使之变成完全二叉树的形态，然后再用顺序存储结构存储。,(a)一般二叉树,(b)完全二叉树形态,单支树,由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。,链表存储表示,A,D,E,B,C,F,root,lchild data rchild,结点结构,二叉链表,A,D,E,B,C,F,root,三叉链表,parent lchild data rchild,结点结构,(Binary Tree Traversal),6.3 二叉树的遍历,遍历概念,顺着某一条搜索路径巡访二叉树中的结点，使 得每个结点均被访问一次，而且仅被访问一次。,“访问”的含义很广，可以是对结点作各种处理，如：输出结点的信息、修改结点的数据值等，但要求这种访问不破坏原来的数据结构。,遍历方法,依次遍历二叉树中的三个组成 部分，便是遍历了整个二叉树,假设：L：遍历左子树 v：访问根结点 R：遍历右子树,则遍历整个二叉树方案共有：,遍历目的,得到树中所有结点的一个线性排列。,vLR、LvR、LRv、vRL、RvL、RLv 六种。,若规定先左后右，则只有前三种情况：vLR 前（根）序遍历，LvR 中（根）序遍历，LRv 后（根）序遍历。,前序遍历二叉树的操作定义：若二叉树为空，则空操作；否则(1)访问根结点；(2)前序遍历左子树；(3)前序遍历右子树。,前序遍历：ABC,A B E L D H M I J,中序遍历二叉树的操作定义：若二叉树为空，则空操作；否则(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树。,中序遍历：BAC,E L B A M H I D J,后序遍历二叉树的操作定义：若二叉树为空，则空操作；否则(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。,后序遍历：BCA,L E B M I H J D A,a+b,(a+b)c d/e,a+bc,分析表达式和二叉树的关系,a,b,+,a,b,c,+,a,b,c,+,(a+b)c,a,b,c,d,e,-,+,/,-,-,/,+,a,b,c,d,e,f,例：写出下图二叉树的先序、中序和后序遍历顺序。,遍历结果：,前序：-+ab-c d/e f,中序：a+bc-d-e/f,后序：a b c d-+e f/-,表达式的前缀表示,表达式的中缀表示,表达式的后缀表示,二叉树的类定义,template class BinTreeNode/二叉树结点类 private:BinTreeNode*LChild,*RChild;Type data;public:BinTreeNode()LChild=RChild=NULL;BinTreeNode(const Type,template class BinaryTree/二叉树类 protected:BinTreeNode*root;void PreOrderHelp(BinTreeNode*r,void(*Visit)(const Type,先、中、后序遍历（辅助函数）,public:BinaryTree();/建立以r为根的二叉树 BinaryTree(BinTreeNode*r);virtual BinaryTree();/析构函数 BinTreeNode*GetRoot()const;bool Empty()const;void InOrder(void(*Visit)(const Type/二叉树的前序遍历,void PostOrder(void(*Visit)(const Type,二叉树前序遍历递归算法,template void BinaryTree:PreOrderHelp(BinTreeNode*r,void(*Visit)(const Type,template void BinaryTree:PreOrder(void(*Visit)(Type,template void write(const Type,二叉树前序遍历非递归算法,template void BinaryTree:PreOrder()Stack*s;BinTreeNode*p=root;do while(p!=NULL)cout pdata;Push(s,p);p=pLChild;if(!Empty(s)p=pop(s);p=pRChild;while(!Empty(s)|(p!=NULL);,二叉树中序遍历非递归算法,template void BinaryTree:InOrder()BinTreeNode*p=root;Stack*s;do while(p!=NULL)Push(s,p);p=pLChild;if(!Empty(s)p=pop(s);cout pdata;p=pRChild;while(!Empty(s)|(p!=NULL);,层次遍历(Levelorder Traversal),从上到下，从左到右遍历结果-a*e f b-cd,二叉树的重建,由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树由二叉树的后序序列和中序序列可以唯一地确定一棵二叉树由二叉树的前序序列和后序序列不可唯一地确定一棵二叉树,仅知二叉树的前序序列“abcdefg”不能唯一确定一棵二叉树，如果同时已知二叉树的中序序列“cbdaegf”，则会如何？,由二叉树的前序和中序序列建树,二叉树的前序序列,二叉树的中序序列,左子树,左子树,右子树,右子树,根,根,a b c d e f g,c b d a e g f,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,前序序列中序序列,前序序列 A B H F D E C K G 中序序列 H B D F A E K C G,二叉树应用事例,template void BinaryTree:InsertRightChild(BinTreeNode*cur,const Type/e成为cur的右孩子,template void BinaryTree:InsertLeftChild(BinTreeNode*cur,const Type/e成为cur的左孩子,int main(void)BinTreeNode*cur;int c;cur=new BinTreeNode(2);BinaryTree bt(cur);/建立二叉树c=3;bt.InsertLeftChild(cur,c);/插入左孩子cur=bt.LeftChild(cur);c=4;bt.InsertRightChild(cur,c);/插入右孩子cur=bt.GetRoot();/取出根结点c=6;bt.InsertRightChild(cur,c);/插入右孩子return 0;,6.6 树和森林,一、树的存储表示,父亲表示法,孩子表示法,改进：父亲、孩子表示法结合,孩子兄弟表示法,AB C E D F G,root,练习,树的遍历,深度优先遍历树的先根次序遍历树的后根次序遍历广度优先遍历树的层次次序遍历,A B C DE F G H I J K,先根遍历,A B E F C D G H I J K,后根遍历,E F B C I J K H G D A,层次遍历：,A B C D E F G H I J K,B C DE F G H I J K,1森林中第一棵树的根结点,2森林中第一棵树的子树森林,3森林中其它树构成的森林,森林由三部分构成,森林的先根遍历,若森林F为空,返回否则:访问F的第一棵树的根结点 先根次序遍历第一棵树的子树森林 先根次序遍历其它树组成的森林,结果：B E F C D G H I J K,森林的后根遍历,若森林F为空，返回否则:后根次序遍历第一棵树的子树森林 访问F的第一棵树的根结点 后根次序遍历其它树组成的森林,结果：E F B C I J K H G D,森林的层次遍历,若森林F为空，返回否则:依次遍历各棵树的根结点 依次遍历各棵树根结点的所有子女 依次遍历这些子女结点的子女结点,结果：B C D E F G H I J K,森林与二叉树的相互转换,6.7 哈 夫 曼 树(Huffman Tree)与哈 夫 曼 编 码,结点的路径长度 从根结点到该结点的路径上分 支的数目,树的路径长度 树中每个结点的路径长度之和,树的带权路径长度(Weighted Path Length,WPL)树的各叶子结点所带的权值与 该结点到根的路径长度的乘积 的和,结点的带权路径长度 从该结点到到根结点之间的路 径长度与结点上权的乘积。,在所有含n个叶子结点、并带有各自权值的m叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”,或“哈夫曼树”(Huffman Tree),哈夫曼树中，权值大的结点离根最近,具有不同带权路径长度的二叉树,WPL(a)=72+52+23+43+92=60,WPL(b)=74+94+53+42+21=89,根据给定的 n 个权值 w1,w2,wn，造 n 棵二叉树的集合 F=T1,T2,Tn，其中每棵二叉树中均只含一个带权 值为 wi 的根结点，其左、右子树为 空树；,(1),构造哈夫曼树,在 F 中选取其根结点的权值为最 小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并 置这棵新的二叉树根结点的权值 为其左、右子树根结点的权值之 和；,(2),从F中删去这两棵树，同时加入 刚生成的新树,重复(2)和(3)两步，直至 F 中只 含一棵树为止,(3),(4),哈夫曼树的构造过程,9,练习：已知权值 W=5,6,2,9,7,5,6,2,7,9,2,5,7,16,6,7,13,29,哈夫曼编码,哈夫曼树的应用很广，哈夫曼编码就是其在电讯通信中的应用之一。在电讯通信业务中，通常用二进制编码来表示字母或其他字符，并用这样的编码来表示字符序列。,例：如果需传送的电文为 ABACCDA，它只用到四种字符，用两位二进制编码便可分辨。假设 A,B,C,D 的编码分别为 00,01,10,11，则上述电文便为 00010010101100（共 14 位），译码员按两位进行分组译码，便可恢复原来的电文。,能否使编码总长度更短呢？,实际应用中各字符的出现频度不相同,数据的最小冗余编码问题,用短（长）编码表示频率大（小）的字符,使得编码序列的总长度最小，使所需总空间量最少,若假设 A,B,C,D 的编码分别为 0，00，1，01，则电文 ABACCDA 便为 000011010（共 9 位）。,可译为 BBCCDA、ABACCDA、AAAACCACA 存在多义性,要求任一字符的编码都不能是另一字符编码的前缀！这种编码称为前缀编码（其实是非前缀码）。,译码的惟一性问题,利用最优二叉树可以很好地解决上述两个问题,在编码过程要考虑两个问题,数据的最小冗余编码问题,译码的惟一性问题,以电文中的字符作为叶子结点构造二叉树。然后将二叉树中 结点引向其左孩子的分支标 0，引向其右孩子的分支标 1；每 个字符的编码即为从根到每个叶子的路径上得到的 0,1 序列。如 此得到的即为二进制前缀编码。,如 此得到的即为二进制前缀编码。,用二叉树设计二进制前缀编码,例：,编码：A：0 B：10 C：110 D：111,?,任意一个叶子 结点都不可能 在其它叶子结 点的路径中。,假设各个字符在电文中出现的次数（或频率）为 wi，其编码长度为 li，电文中只有 n 种字符，编码总长为：,叶子结点的权,从根到叶子的路径长度,设计电文总长最短的编码,设计哈夫曼树（以 n 种 字符出现的频率作权）,用哈夫曼树设计总长最短的二进制前缀编码,由哈夫曼树得到的二进制前缀编码称为哈夫曼编码,解：,编码：A：0 C：10 B：110 D：111,例：如果需传送的电文为 ABACCDA，即：A,B,C,D 的频率（即权值）分别为 0.43,0.14,0.29,0.14，试构造哈夫曼编码。,则电文 ABACCDA 便为 0110010101110（共 13 位）。,解：,编码：A：11 C：10 E：00 B：010 D：011,例：如果需传送的电文为 ABCACCDAEAE，即：A,B,C,D,E 的频率（即权值）分别为 0.36,0.1,0.27,0.1,0.18，试构造哈夫曼编码。,则电文 ABCACCDAEAE 便为 110101011101001111001100（共 24 位，比 33 位短）。,译码,从哈夫曼树根开始，对待译码电文逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束。,电文为“1101000”,译文只能是“CAT”,教学要求,本章是重点章，二叉树又是本章的重点内容。要求：1、熟悉树的定义、存储结构、遍历；2、熟悉二叉树的定义、性质、存储结构；3、熟练掌握二叉树的遍历；4、熟练掌握树、森林与二叉树的转换；5、熟练掌握哈夫曼树及哈夫曼编码等内容。,