• / 146
  • 下载费用:10 金币  

《数据结构》(C语言版)第六章_树和二叉树.ppt

关 键 词:
《数据结构》(C语言版)第六章_树和二叉树.ppt
资源描述:
第六章 树和二叉树,6.1 树的定义和基本术语,6.2 二叉树,6.3 遍历二叉树和线索二叉树,6.4 树和森林,6.6 赫夫曼树及其应用,,学习提要: 掌握二叉树的性质,了解相应的证明方法。 2. 熟悉二叉树的各种存储结构的特点及适用范围。 3. 掌握各种遍历策略的递归算法,灵活运用遍历算法实现二叉树的其它操作。 4. 理解二叉树线索化的实质,熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。 5. 熟悉树的各种存储结构及其特点,掌握树和森林与二叉树的转换方法。,6. 了解最优树的特性,掌握建立最优树和哈夫曼编码的方法。重难点内容:二叉树的性质及其证明、二叉树的遍 历、二叉树的线索化、树和森林与二叉树 的转换、哈夫曼树的遍历和哈夫曼编码。,,§6.1 树的定义和基本术语,6.1.2 基本术语,6.1.1 树的类型定义,6.1.1 树的类型定义,树的抽象数据类型定义:,ADT Tree{数据对象 D: D是具有相同特性的数据元素的集合。数据关系 R: 若D为空集,则称为空树。否则:(1) 在D中存在唯一的称为根(root)的结点;(2) 当n1时,其余结点可分为m (m0)个互不相交的有限集T1, T2, …, Tm,其中每一棵子集本身又是一棵符合本定义的树,称为根的子树(SubTree)。基本操作P: } ADT Tree,,……,,,,根,子树,,基本操作:,查 找 类,插 入 类,删 除 类,,,,,Root(T) // 求树的根结点,查找类:,Value(T, cur_e) // 求当前结点的元素值,Parent(T, cur_e) // 求当前结点的双亲结点,LeftChild(T, cur_e) // 求当前结点的最左孩子,RightSibling(T, cur_e) // 求当前结点的右兄弟,TreeEmpty(T) // 判定树是否为空树,TreeDepth(T) // 求树的深度,TraverseTree( T, Visit() ) // 遍历,,InitTree(&T) // 初始化置空树,插入类:,CreateTree(&T, definition) // 按定义构造树,Assign(T, cur_e, value) // 给当前结点赋值,InsertChild(&T, &p, i, c) // 将以c为根的树插入为结点p的第i棵子树,,ClearTree(&T) // 将树清空,删除类:,DestroyTree(&T) // 销毁树的结构,DeleteChild(&T, &p, i) // 删除结点p的第i 棵子树,,6.1.2 基本术语,结点(node):数据元素+若干指向子树的分支。 结点的度(degree):分支个数。 树的度:树中所有结点的度的最大值。 叶子结点:度为0的结点,也称终端结点。 分支结点:度大于0的结点,也称非终端结点。,(从根到结点的)路径:,孩子结点、双亲结点 兄弟结点、堂兄弟 祖先结点、子孙结点,结点的层次:,树的深度:,由从根到该结点所经分支和结点构成。,,假设根结点的层次为1,第l 层的结点的子树根结点的层次为l+1。,树中叶子结点所在的最大层次。,任何一棵非空树是一个二元组Tree = (root,F) 其中:root 被称为根结点F 被称为子树森林,森林:,是m(m≥0)棵互 不相交的树的集合。,A,root,,B,C,D,E,F,G,H,I,J,M,K,L,,,,,,,,,,F,,,,,(1) 有确定的根; (2) 树根和子树根之间为有向关系。,有向树:,有序树:,子树之间存在确定的次序关系。,无序树:,子树之间不存在确定的次序关系。,,,线性结构,树形结构,第一个数据元素(无前驱),根结点(无前驱),最后一个数据元素(无后继),多个叶子结点(无后继),其它数据元素 (一个前驱、一个后继),其它数据元素 (一个前驱、多个后继),,,,§6.2 二叉树,6.2.2 二叉树的性质,6.2.1 二叉树的类型定义,6.2.3 二叉树的存储结构,二叉树或为空树,或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。,A,B,C,D,E,F,G,H,K,,,,,,,,,,,根结点,左子树,右子树,6.2.1 二叉树的类型定义,二叉树的五种基本形态:,,,N,,,,,N,N,N,L,R,R,L,二叉树和树是两种不同的树型结构,二叉树不等同于度为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());,,InitBiTree(,,ClearBiTree(,,性质 1 :在二叉树的第 i 层上至多有2i-1 个结 点。 (i≥1),6.2.2 二叉树的性质,用归纳法证明:归纳基:归纳假设:归纳证明:,i = 1 层时,只有一个根结点:2i-1 = 20 = 1;,二叉树上每个结点至多有两棵子树, 则第 i 层的结点数 = 2i-2 2 = 2i-1 。,假设对所有的 j,1≤ j  i,命题成立;,性质 2 : 深度为 k 的二叉树上至多含 2k-1 个结点(k≥1)。,证明:,基于上一条性质,深度为 k 的二叉树上的结点数至多为20+21+       +2k-1 = 2k-1,性质 3 : 对任何一棵二叉树,若它含有n0 个叶子结点、n2 个度为 2 的结点,则必存在关系式:n0 = n2+1。,证明:,设 二叉树上结点总数 n = n0 + n1 + n2 又 二叉树上分支总数 b = n1+2n2而 b = n-1 = n0 + n1 + n2 - 1 由此, n0 = n2 + 1 。,两种特殊形式的二叉树 满二叉树 定义:指的是深度为k且含有2k-1个结点的二叉树。 特点:每一层上的结点数都是最大结点数。,完全二叉树 定义:树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。 特点: 叶子结点只可能在层次最大的两层上出现 对任一结点,若其右分支下子孙的最大层次为 L,则其左分支下子孙的最大层次必为L 或L+1。,性质 4 : 具有 n 个结点的完全二叉树的深度为  log2n +1 。,证明:,设完全二叉树的深度为 k , 则根据第二条性质得 2k-1-1 n ≤ 2k-1 或 2k-1≤ n 2k 即 k-1 ≤ log2 n k 因为 k 只能是整数,因此, k =log2n + 1 。,性质5:如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i ,有: (1) 若 i=1,则该结点是二叉树的根,无双亲,否则,编号为 i/2 的结点为其双亲结点; (2) 若 2in,则该结点无左孩子, 否则,编号为 2i 的结点为其左孩子结点; (3) 若 2i+1n,则该结点无右孩子结点, 否则,编号为2i+1 的结点为其右孩子结点。,,#define MAX_TREE_SIZE 100 // 二叉树的最大结点数 typedef TElemType SqBiTree[MAX_TREE_SIZE]; // 0号单元存储根结点 SqBiTree bt;,一、顺序存储结构,6.2.3 二叉树的存储结构,例如:,A B C D E F G H I J K L,0 1 2 3 4 5 6 7 8 9 10 11,例如:,A,B,C,D,E,F,,,,A B D C E F,,,,,,,,,,,,,,,0 1 2 3 4 5 6 7 8 9 10 11 12 13,,,,,,2,5,1,14,3,7,特点: 结点间关系蕴含在其存储位置中,即编号为 i 的结点元素存储在一维数组中下标为 i-1 的分量中。 浪费空间,适于存满二叉树和完全二叉树。,二、链式存储结构,lchild data rchild,,,,结点结构:,二叉链表,typedef struct BiTNode { // 结点结构TElemType data;struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree;,在n个结点的二叉链表中,有n+1个空指针域,,,,,,,^,^,^,^,^,^,^,^,例如:,typedef struct TriTNode { // 结点结构TElemType data;struct TriTNode *lchild, *rchild; // 左右孩子指针struct TriTNode *parent; //双亲指针 } TriTNode, *TriTree;,lchild data parent rchild,,,,,结点结构:,三叉链表,,,,,,,,,,,,,^,^,^,^,^,^,^,^,^,例如:,,§6.3 遍历二叉树和线索二叉树,6.3.2 线索二叉树,6.3.1 遍历二叉树,6.3.1 遍历二叉树,一、问题的提出,二、先左后右遍历的定义,三、算法的递归描述,四、中序遍历算法的非递归描述,五、遍历算法的应用举例,,遍历二叉树,即顺着某一条搜索路径巡访二叉树中的结点,使得每个结点均被访问一次,而且仅被访问一次。,一、问题的提出,对“二叉树”而言,可以有三条搜索路径:,1.先上后下的按层次遍历; 2.先左(子树)后右(子树)的遍历; 3.先右(子树)后左(子树)的遍历。,,二、先左后右遍历的定义,,先(根)序遍历(DLR),二叉树的典型结构:,中(根)序遍历(LDR),后(根)序遍历(LRD),,先序遍历二叉树操作定义:若二叉树为空,则空操作;否则(1)访问根结点;(2)先序遍历左子树;(3)先序遍历右子树。,D L R,先序遍历序列:A B D C,先序遍历:,,中序遍历二叉树操作定义:若二叉树为空,则空操作;否则(1)中序遍历左子树; (2)访问根结点;(3)中序遍历右子树。,L D R,中序遍历序列:B D A C,中序遍历:,,后序遍历二叉树操作定义:若二叉树为空,则空操作;否则(1)后序遍历左子树;(2)后序遍历右子树;(3)访问根结点 。,L R D,后序遍历序列: D B C A,后序遍历:,,先序遍历:,中序遍历:,后序遍历:,层次遍历:,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,,三、算法的递归描述,void Preorder (BiTree T,void( *visit)(TElemType// 遍历右子树} },,返回,返回,返回,返回,A,C,B,D,返回,先序序列:A B D C,,visit(T-data); Preorder(T-lchild, visit); Preorder(T-rchild, visit),四、中序遍历算法的非递归描述,Status InOrderTraverse( Bitree T,Status(*visit)(TElemType e){Initstack(S); p=T;while (p || !Stackempty (S) ){if ( p ) { push ( S , p ) ; p = p-lchild;} //根指针进栈,遍历左子树else { //根指针退栈,访问根结点,遍历右子树pop(S,p); if ( !Visit (p-data) ) return ERROR;p=p-rchild;}}//whilereturn OK; }// InOrdertraverse,,,P-A,,P-B,,P-C,P=null,,C,,,P=null,,,,B,P-D,,,P-E,P=null,P=null,,,,E,,P-G,P=null,,,,G,P=null,,,,,P-F,P=null,,,F,,D,,,A,,P=null,,,五、遍历算法的应用举例,统计二叉树中叶子结点的个数(先序遍历),求二叉树的深度(后序遍历),建立二叉树的存储结构,,以字符串的形式根 左子树 右子树 定义一棵二叉树。,建立二叉树的存储结构,以按先序序列建立二叉树的二叉链表的过程为例来说明。,例如:,以空白字符“ ”表示,A(B( ,C( , )),D( , )),,,,,,,,,,空树,只含一个根结点的二叉树,A,以字符串“A ”表示,以下列字符串表示:,,,,,,,,Status CreateBiTree(BiTree } // CreateBiTree,A B C D,,,,,,,,,,,A,B,C,D,上页算法执行过程举例如下:,A,,,,T,B,,,C,,,D,,,,^,,^,^,,^,^,,统计二叉树中叶子结点的个数,算法基本思想:,先序(或中序或后序)遍历二叉树,在遍历过程中查找叶子结点,并计数。由此,需在遍历算法中增添一个“计数”的参数,并将算法中“访问结点”的操作改为:若是叶子,则计数器增1。,void CountLeaf (BiTree T, int } // if } // CountLeaf,,求二叉树的深度(后序遍历),算法基本思想:,从二叉树深度的定义可知,二叉树的深度应为其左、右子树深度的最大值加1。由此,需先分别求得左、右子树的深度,算法中“访问结点”的操作为:求得左、右子树深度的最大值,然后加1。,首先分析二叉树的深度和它的左、右子树深度之间的关系。,int Depth (BiTree T ){ // 返回二叉树的深度if ( !T ) depthval = 0;else {depthLeft = Depth( T-lchild );depthRight= Depth( T-rchild );depthval = 1 + (depthLeft depthRight ?depthLeft : depthRight) ;} return depthval; },,6.3.2 线索二叉树,一、线索二叉树,二、线索链表的遍历算法,三、如何建立线索链表,,一、线索二叉树,遍历二叉树的结果是,求得结点的一个线性序列。,A,B,C,D,E,F,G,H,K,,,,,,,,,例如:,先序序列:A B C D E F G H K,中序序列:B D C A H G K F E,后序序列:D C B H K G F E A,指向该线性序列中的“前驱”和 “后继” 的指针,称作“线索”。,加上线索的二叉树,称作 “线索二叉树”。,A B C D E F G H K,,,^ D ^,C ^,^ B,,,,,,,,,E ^,,,,,在二叉链表的结点中增加两个标志域, 并作如下规定:,其中:,如此定义的二叉树的存储结构称作“线索链表”。,typedef struct BiThrNod {TElemType data;struct BiThrNode *lchild, *rchild; // 左右指针PointerThr LTag, RTag; // 左右标志 } BiThrNode, *BiThrTree;,线索链表的类型描述:,typedef enum { Link, Thread } PointerThr; // Link==0: 指针,Thread==1: 线索,,,,,,,,,,,0,0,0,0,1,1,1,1,^,1,1,,,,,0,0,0,0,1,1,1,1,1,1,^,,,,,,,,,,0,0,0,0,1,1,1,1,^,1,1,,,,,^,,二、线索链表的遍历算法:,for ( p = firstNode(T); p; p = Succ(p) )Visit (p);,由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息,从而简化了遍历的算法。,例如: 对中序线索化链表的遍历算法。,※ 中序遍历的第一个结点?,※ 在中序线索化链表中结点的后继?,左子树上处于“最左下”(没有左子树)的结点。,若无右子树,则为后继线索所指结点;,否则为对其右子树进行中序遍历时访问的第一个结点。,void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e)) {p = T-lchild; // p指向根结点while (p != T) { // 空树或遍历结束时,p==Twhile (p-LTag==Link) p=p-lchild; //第一个结点if ( !Visit(p-data) return ERROR;while (p-RTag==Thread // p进至其右子树根} } // InOrderTraverse_Thr,,,B,,C,,A,,E,D,,,,while (p != T) { while (p-LTag==Link) p=p-lchild; if ( !Visit(p-data) return ERROR;while (p-RTag==Thread },在中序遍历过程中修改结点的 左、右指针域,以保存当前访问结 点的“前驱”和“后继”信息。遍历过 程中,附设指针pre, 并始终保持指 针pre指向当前访问的、指针p所指 结点的前驱。,三、如何建立线索链表?,void InThreading(BiThrTree p) {if (p) { // 对以p为根的非空二叉树进行线索化InThreading(p-lchild); // 左子树线索化if (!p-lchild) // 建前驱线索{ p-LTag = Thread; p-lchild = pre; }if (!pre-rchild) // 建后继线索{ pre-RTag = Thread; pre-rchild = p; } pre = p; // 保持 pre 指向 p 的前驱InThreading(p-rchild); // 右子树线索化} // if } // InThreading,Status InOrderThreading(BiThrTree } // InOrderThreading,… …,,if (!T) Thrt-lchild = Thrt; else { Thrt-lchild = T; pre = Thrt;InThreading(T); pre-rchild = Thrt; // 处理最后一个结点pre-RTag = Thread; Thrt-rchild = pre; },,if (p) { InThreading(p-lchild); if (!p-lchild) { p-LTag = Thread; p-lchild = pre; }if (!pre-rchild) { pre-RTag = Thread; pre-rchild = p; } pre = p; InThreading(p-rchild); },,1,,,1,,,,1,,,1,,,,1,,,1,,,,,p=null,§6.4 树和森林,6.4.2 森林和二叉树的转换,6.4.1 树的存储结构,6.4.3 树和森林的遍历,6.4.1 树的存储结构,一、双亲表示法,二、孩子表示法,三、孩子兄弟表示法,树的三种存储结构:,,#define MAX_TREE_SIZE 100 typedef struct PTnode{ //结点结构 telemtype data;int parent; //双亲位置域 } Tnode; Typedef struct{ //树结构PTnode nodes[MAX_TREE_SIZE];Int r ,n; //根的位置和结点数 }PTree;,,一、双亲表示法,0,1,1,2,4,4,4,0,-1,如何找孩子结点,R =0,N =9,,二、孩子表示法,多重链表:每个结点有多个指针域,分别指向其子树的根。 结点同构:结点的指针个数相等,为树的度D 结点不同构:结点指针个数不等,为该结点的度d,n个结点度为k的树中有n(k-1)+1个空链域,孩子链表:每个结点的孩子结点用单链表存储,再用含n个元素的结构数组指向每个孩子链表。,,typedef struct CTNode {int child;struct CTNode *next;} *ChildPtr;,孩子结点结构:,child next,,typedef struct {Elem data;ChildPtr firstchild; // 孩子链的头指针} CTBox;,双亲结点结构:,data firstchild,,树结构:,typedef struct {CTBox nodes[MAX_TREE_SIZE];int n, r; // 结点数和根结点的位置} CTree;,^,^,^,^,^,如何找双亲结点,R=0,N=9,带双亲的孩子链表,,firstchild data nextsibling,三、孩子兄弟表示法(二叉树表示法),typedef struct CSNode{Elem data;struct CSNode *firstchild, *nextsibling; } CSNode, *CSTree;,结点结构:,,,,,,,,,,,^,^,^,^,^,^,^,^,^,^,,,6.4.2 树、森林与二叉树转换,将树转换成二叉树 加线:在兄弟之间加一连线。 抹线:对每个结点,除了其第一个孩子外,去除其与其余孩子之间的关系。 旋转:以树的根结点为轴心,将整树顺时针转45度 。,,,,,,树转换成的二叉树其右子树一定为空,例如:,将二叉树转换成树 加线:若p结点是双亲结点的左孩子,则将p的右孩子,右孩子的右孩子,……沿分支找到的所有右孩子,都与p的双亲用线连起来。 抹线:抹掉原二叉树中双亲与右孩子之间的连线。 调整:将结点按层次排列,形成树结构。,,,,,,例如:,森林转换成二叉树,,,,,,设森林 F = ( T1, T2, …, Tn );T1= (root, t11, t12, …, t1m);二叉树 B=(root,LB,RB)。,则由森林转换成二叉树的转换规则为: 若 F = Φ,则 B = Φ;否则,由 ROOT( T1 ) 对应得到 root;由 (t11, t12, …, t1m ) 对应得到 LB;由 (T2, T3,…, Tn ) 对应得到 RB.,二叉树转换成森林,,,,设森林 F = ( T1, T2, …, Tn );T1= (root, t11, t12, …, t1m);二叉树 B =(root,LB,RB)。,则由二叉树转换为森林的转换规则为:若 B = Φ, 则 F = Φ;否则,由 root对应得到 ROOT( T1 );由LB 对应得到 ( t11, t12, …,t1m);由RB 对应得到 (T2, T3, …, Tn),由此,树的各种操作均可对应二叉树的操作来完成。,应当注意的是,和树对应的二叉树,其左、右子树的概念 已改变为:左是孩子,右是兄弟。,,一、树的遍历,二、森林的遍历,三、树的遍历的应用,6.4.3 树和森林的遍历,,一、树的遍历,按层次遍历:,先根(次序)遍历:,后根(次序)遍历:,若树不空,则先访问根结点,然后依次先根遍历各棵子树。,若树不空,则先依次后根遍历各棵子树,然后访问根结点。,若树不空,则自上而下自左至右访问树中每个结点。,AB C DE F GHI 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 GHI J K,,,,,,,,,,,,,,,,,,,,,1.森林中第一棵树的根结点;,2.森林中第一棵树的子树森林;,3.森林中其它树构成的森林。,森林由三部分构成:,,二、森林的遍历,若森林不空,则 (1)访问森林中第一棵树的根结点; (2)先序遍历森林中第一棵树的子树森林; (3)先序遍历森林中(除第一棵树之外)其余树构成的森林。,1. 先序遍历,即:依次从左至右对森林中的每一棵树进行先根遍历。,,2.中序遍历,若森林不空,则 (1)中序遍历森林中第一棵树的子树森林; (2)访问森林中第一棵树的根结点; (3)中序遍历森林中(除第一棵树之外)其 余树构成的森林。,即:依次从左至右对森林中的每一棵树进行后根遍历。,,树的遍历和二叉树遍历的对应关系 ?,先根遍历,后根遍历,树,二叉树,森林,先序遍历,先序遍历,中序遍历,中序遍历,,求树的深度,输出树中所有从根到叶子的路径,建树的存储结构,三、树的遍历的应用,,设树的存储结构为孩子兄弟链表,typedef struct CSNode{Elem data;struct CSNode *firstchild,*nextsibling; } CSNode, *CSTree;,int TreeDepth(CSTree T) {if(!T) return 0;else {h1 = TreeDepth( T-firstchild );h2 = TreeDepth( T-nextsibling);} } // TreeDepth,return(max(h1+1, h2));,求树的深度的算法:,,输出树中所有从根到叶子的路径的算法:,例如:对左图所示的树,其输出结果应为:,A B E A B F A C A D G H I A D G H J A D G H K,void AllPath( Bitree T, Stack} // if(T) } // AllPath,// 输出二叉树上从根到所有叶子结点的路径,,void OutPath( CSTree T, Stack} // while } // OutPath,// 输出树中所有从根到叶的路径,,,建树的存储结构的算法:,和二叉树类似,不同的定义相应有不同的算法。,假设以二元组(F,C)的形式自上而下、自左而右依次输入树的各边,建立树的孩子-兄弟链表。,,A,,,,,,,B,C,D,E,F,G,,,,,,,例如:,对下列所示树的输入序列应为:,(‘#’, ‘A’) (‘A’, ‘B’) (‘A’, ‘C’) (‘A’, ‘D’) (‘C’, ‘E’) (‘C’, ‘F’) (‘E’, ‘G’),A,,,B,,,C,,,D,,,,,,(‘#’, ‘A’),(‘A’, ‘B’),(‘A’, ‘C’),(‘A’, ‘D’),(‘C’, ‘E’),可见,算法中需要一个队列保存已建好的结点的指针。,void CreatTree( CSTree // 所建为根结点else { } // 非根结点的情况} // for } // CreateTree,… …,,GetHead(Q,s); // 取队列头元素(指针值) while (s-data != fa ) { // 查询双亲结点DeQueue(Q,s); GetHead(Q,s); } if (!(s-firstchild)) { s-firstchild = p; r = p; }// 链接第一个孩子结点 else { r-nextsibling = p; r = p; }// 链接其它孩子结点,,,,,§6.6 赫夫曼树及其应用,6.6.1 最优二叉树,6.6.2 赫夫曼编码,,,,6.6.1 最优二叉树(赫夫曼树),结点的路径长度:从根结点到该结点的路径上分支的数目。 树的路径长度:从树根到每一个结点的路径长度之和。,,,,树的带权路径长度:树中所有叶子结点的带权路径长度之和,记作,赫夫曼树(最优二叉树):带权路径长度之和最小的二叉树。,结点的带权路径长度:从该结点到树根之间的路径长度与结点上权的乘积。,例如:,WPL=7*2+5*2+2*2+4*2=36,WPL=7*3+5*3+2*1+4*2=46,WPL=7*1+5*2+2*3+4*3=35,,(1)根据给定的 n 个权值 {w1, w2, …, wn},构造 n 棵二叉树的集合F = {T1, T2, … , Tn},其中每棵二叉树中均只含一个带权值为 wi 的根结点,其左、右子树为空树;,如何构造最优树?,(赫夫曼算法)以二叉树为例:,(2)在 F 中选取其根结点的权值为最小的两棵二叉树,分别作为左、右子树构造一棵新的二叉树,并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;,(3)从F中删去这两棵树,同时加入刚生成的新树;,(4)重复 (2) 和 (3) 两步,直至 F 中只 含一棵树为止。,9,例如: 已知权值 W={ 5, 6, 2, 9, 7 },5,6,2,7,5,2,,,7,6,9,7,6,7,13,,,9,5,2,,,7,9,5,2,,,7,16,,,6,7,13,,,29,,,Huffman算法实现:,typedef struct {unsigned int weight; unsigned int parent,lchild,rchild; } HTNode,*HuffmanTree;,一棵有n个叶子结点的Huffman树有 2n-1个结点结点类型定义,Viod HuffmanTree(HuffmanTree },5,29,7,8,14,23,3,11,例6-2: 设权w= (5,29,7,8,14,23,3,11),8,1,7,9,9,15,3,4,10,10,19,8,9,11,11,29,5,10,12,12,42,13,13,6,11,58,14,14,100,15,15,2,12,13,14,n=8,则m=15,,例如:假设需传送的电文‘ABACCDA’。,目前,数据通信用的二进制编码。,假设A、B、C、D的编码分别为00、01、10、11,则上述字符串的电文编码为‘00010010101100’。,6.6.2 赫夫曼编码,假设A、B、C、D的编码分别为0、00、1、10,则上述字符串的电文编码为‘000011010’。,,指的是,任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。,前缀编码:,利用赫夫曼树可以构造一种不等长的二进制编码,并且构造所得的赫夫曼编码是一种最优前缀编码,即使所传电文的总长度最短。,赫夫曼编码: 思想:根据字符出现频率编码,使电文总长最短。 编码:根据字符出现频率构造Huffman树,然后将树中结点引向其左孩子的分支标“0”,引向其右孩子的分支标“1”;每个字符的编码即为从根到每个叶子的路径上得到的0、1序列。,例:已知某系统在通信联络中只可能出现8种字符,其概率分别是 0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11, 试设计赫夫曼编码。,设权w=(5,29,7,8,14,23,3,11),0,0,0,0,0,0,0,1,1,1,1,1,1,1,00,010,0110,0111,10,110,1110,1111,1,1,0,0,1,1,0,0,i=1,,,,,,,,,,,Viod HuffmanCoding(HuffmanCode //释放工作空间 }//HuffmanCoding,,for (i=1; i=n; ++i){ //逐个字符求哈夫曼编码start = n-1;for (c=i, f=HT[i].parent; f!=0; c=f, f=HT[f].parent) //从叶子到根逆向求编码if ( HT[f].lchild == c ) cd[--start]= “0”;else cd[--start]=“1”;HC[i] = (char *) malloc (n-start) *sizeof(char);//为第i个字符编码分配空间Strcpy( HC[i], //从cd复制编码(串)到BC },,译码:从Huffman树根开始,从待译码电文中逐位取码。若编码是“0”,则向左走;若编码是“1”,则向右走,一旦到达叶子结点,则译出一个字符;再重新从根出发,直到电文结束。,,第六章 作业,6.1、6.3、 6.12、6.15、6.17、6.19、6.21、6.22、6.27,,补充作业:设权W={10, 5, 12, 7, 4, 2}, 建立一棵哈夫曼树(按左子树根结点的权小于等于右子根的权的次序构造,画出建树过程),并求出其带权路径长度WPL。,6.1 已知一棵树边的集合为{ ,, ,, ,,,,,,,, },请画出这棵树,并回答下列问题:(1) 哪个是根结点?(2) 哪些是叶子结点?(3) 哪个是结点G的双亲?(4) 哪些是结点G的祖先?(5) 哪些是结点G的子孙?(6) 哪些是结点E的子孙?(7) 哪些是结点E的兄弟?哪些是结点F的兄弟?(8) 结点B和N的层次号分别是什么?(9) 树的深度是多少?(10) 以结点C为根的子树的深度是多少?,6.3 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 6.12 对题6.3所得各种形状的二叉树,分别写出前序、中序和后序遍历的序列。 6.15 请对如图所示二叉树进行后序线索化,为每个空指针建立相应的前驱或后继线索。,6.17 阅读下列算法,若有错,则改征之。 BiTree InSucc(BiTree q){//已知q是指向中序线索二叉树上某个结点的指针, //本函数返回指向*q的后继的指针。r = qrchild;if ( !r rtag )while( !rrtag ) r = rrchild;return r; }//InSucc,6.19 分别画出和下列树对应的各个二叉树:,6.22 对于6.19题中给出的各树分别求出以下遍历序列:(1)先根序列; (2)后根序列。,6.21 画出和下列二叉树相应的森林:,6.27 假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列ABCDEFGHIJK。请画出该二叉树。,,
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:《数据结构》(C语言版)第六章_树和二叉树.ppt
链接地址:https://www.weizhuannet.com/p-10026160.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开