页数:113页文件大小:2.47 MB来源: 数据结构ppt课件
本课件为数据结构第五章树,系统讲解树与二叉树的定义、基本术语与性质,介绍二叉树的顺序与链式存储结构及先序、中序、后序与层次遍历算法,随后扩展到线索二叉树、树与森林的存储及转换,最后讲解哈夫曼树的构造、最佳判定树与哈夫曼编码的应用。
实例树的定义二叉树第五章树树型结构的存储树和二叉树的遍历二叉树的应用本章小结
五子棋游戏……..……..…...…...…...…...树的实例
UNIX文件系统结构/(root)libuseretcbinmathdsswyintaoxieStack.cppQueue.cppTree.cpp人类的族谱各种社会关系各类分类编码编译程序的语法树Internet中的DNS(域名系统)树的实例
树是一类重要的非线性数据结构,是以分支关系定义的层次结构 定义:树(tree)是n(n>=0)个结点的有限集T,其中: 有且仅有一个特定的结点,称为树的根(root) 当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm,其中每一个集合本身又是一棵树,称为根的子树(subtree) 特点: 非空树中存在唯一一个称为根结点 非空树中各子树是互不相交的集合至少存在一个数据元素有两个或两个以上的直接前驱(或直接后继)元素的数据结构树的定义
A只有根结点的树ABCDEFGHIJKLM有子树的树根子树
结点A的度:结点B的度:结点M的度:叶子:结点A的孩子:结点B的孩子:结点I的双亲:结点L的双亲:结点B,C,D为结点K,L为树的度:结点A的层次:结点M的层次:树的深度:结点F,G为结点A是结点F,G的结点F,G是结点A的320B, C, DE, F3144K, L, F, G, M, I, JDE兄弟兄弟堂兄弟祖先ABCDEFGHIJKLM树的基本术语子孙
ADTTree{数据对象:D是具有相同特性的数据元素的集合数据关系:若D为空集,则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root;(2)当n>1时,其余结点可分为m (m>0)个互不相交的有限集T1, T2, …, Tm,其中每一棵子集本身又是一棵符合本定义的树,称为根root的子树。基本操作:InitTree(&T);构造空树TClearTree(&T);将树T清为空树DestroyTree(&T);销毁树TCreateTree(&T, definition);按定义definition构造树T抽象数据类型树的定义
基本操作(续):TreeEmpty(T);判定树T是否为空树Value(T, cur_e);求树T中当前结点的元素值TreeDepth(T);求树T的深度Root(T);求树T的根结点}ADTTreeAssign(T, cur_e, value);为树T中当前结点赋值Parent(T, cur_e);求当前结点的双亲结点LeftChild(T, cur_e);求当前结点的最左孩子RightSibling(T, cur_e);求当前结点的右兄弟InsertChild(&T, &p, i, c);将根为c的树插入为结点p的第i棵子树DeleteChild(&T, &p, i);删除结点p的第i棵子TraverseTree( T, Visit( ) );遍历抽象数据类型树的定义
定义:二叉树是n(n 0)个结点的有限集,它或为空树(n=0),或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成 特点 每个结点至多有二棵子树(即不存在度大于2的结点) 二叉树的子树有左、右之分,且其次序不能任意颠倒 基本形态二叉树的定义 空二叉树左、右子树均非空DRL只有根结点二叉树D右子树为空DL左子树为空DR
ADTBinaryTree{数据对象:D是具有相同特性的数据元素的集合数据关系:若D为空集,则称为空二叉树。否则:(1)在D中存在唯一的称为根的数据元素root;(2)若D-{root}≠ ,则存在D-{root}={Dl,Dr},且Dl∩Dr= ;(3)Dl和Dr分别是一棵符合本定义的二叉树,称为左子树和右子树。基本操作:InitBiTree(&T);构造空二叉树TClearBiTree(&T);将二叉树T清为空树DestroyBiTree(&T);销毁二叉树TCreateBiTree(&T, definition);按definition构造二叉树T抽象数据类型二叉树的定义
基本操作(续):BiTreeEmpty(T);判定二叉树T是否为空Value(T, cur_e);求二叉树T中当前结点的元素值BiTreeDepth(T);求二叉树T的深度Root(T);求二叉树T的根结点Assign(T, cur_e, value);为二叉树T中当前结点赋值Parent(T, cur_e);求当前结点的双亲结点LeftChild(T, cur_e);求当前结点的左孩子RightChild(T, cur_e);求当前结点的右孩子LeftSibling(T, cur_e);求当前结点的左兄弟RightSibling(T, cur_e);求当前结点的右兄弟抽象数据类型二叉树的定义
基本操作(续):}ADTBinaryTreeDeleteChild(&T, &p, LR);根据LR为0或1,删除结点p的左或右子树PreOderTraverse( T, Visit( ) );先序遍历二叉树TInOderTraverse( T, Visit( ) );中序遍历二叉树TPostOderTraverse( T, Visit( ) );后序遍历二叉树TLevelOderTraverse( T, Visit( ) );层次遍历二叉树TInsertChild(&T, &p, LR, c);根据LR为0或1,插入c为结点p的左或右子树,结点p原子树成为c的右子树抽象数据类型二叉树的定义
二叉树的性质 性质1:在二叉树的第i层上至多有2i-1个结点(i≥1)用归纳法证明:归纳基:归纳假设:归纳证明:i=1层时,只有一个根结点:2i-1=20=1;假设对所有的j,1≤j i,命题成立,即第j层上至多有2j-1个结点,则第i-1层上至多有2i-2个结点;由于二叉树上每个结点至多有两棵子树,则第i层的结点数=2i-2 2=2i-1。
证明:由性质1,可得深度为k的二叉树最大结点数是完全二叉树性质4二叉树的性质 性质2:深度为k的二叉树上至多含2k-1个结点(k≥1)等比数列求和:
性质3:对任何一棵二叉树T,如果其叶子结点数为n0,度为2的结点数为n2,则n0=n2+1证明:设n1为二叉树T中度为1的结点数因为:二叉树中所有结点的度均小于或等于2所以:其结点总数n=n0+n1+n2二叉树中,除根结点外,其余结点都只有一个分支进入设B为分支总数,则n=B+1又:分支由度为1和度为2的结点射出, B=n1+2*n2于是,n=B+1=n1+2*n2+1二叉树的性质ABCDEFG=n0+n1+n2 n0=n2+1
满二叉树 定义:
特点:每一层上的结点数都是最大结点数,除最下层的叶子结点外,每个结点的度都为2。满二叉树及其编号完全二叉树特殊形式的二叉树123456789101112131415
完全二叉树 定义:深度为k,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称为~完全二叉树及其编号示例 特点 度小于2的结点只可能在层次最大的两层上出现,如果某个结点没有左孩子,那么它一定没有右孩子,该结点为叶子结点 除最后一层外,每层都充满了结点,最下面一层结点都集中在该层的最左边满二叉树顺序存储完全二叉树中可能有度为1的结点吗?特殊形式的二叉树123456891011127
1231145891213671014151231145891267101234567123456
性质4:证明:设深度为k,根据二叉树性质2知:n ≤2k-1,2k-1≤n<2k,于是有:性质2完全二叉树性质具有n个结点的完全二叉树的深度为 log2n +1123114589126710完全二叉树及其编号示例2k-1-1<
性质5:完全二叉树性质如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i(1 i n),有:(1)如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则其双亲是 i/2 (2)如果2i>n,则结点i无左孩子;如果2i n,则其左孩子是2i(3)如果2i+1>n,则结点i无右孩子;如果2i+1 n,则其右孩子是2i+1123114589126710完全二叉树及其编号示例
性质5:完全二叉树性质如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i(1 i n),有:(1)如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则其双亲是 i/2 (2)如果2i>n,则结点i无左孩子;如果2i n,则其左孩子是2i(3)如果2i+1>n,则结点i无右孩子;如果2i+1 n,则其右孩子是2i+1[i/2]ii+12i2i+12i+2完全二叉树中结点i与双亲和左、右孩子关系二叉树顺序存储
树与二叉树的存储结构及其相互转换树的存储结构二叉树的存储结构树与二叉树的相互转换双亲表示法孩子表示法孩子兄弟表示法多重链表孩子链表带双亲的孩子链表顺序存储结构二叉链表三叉链表
双亲表示法树的存储应该存储哪些信息?data parent
typedefstruct PTNode{ TElemType data;//数据域int parent;//双亲位置域}PTNode;#define Max_Tree_Size 100//树中结点最大数目typedefstruct{PTNodenodes [Max_Tree_Size];//结点数组int r, n;//根结点的位置和结点个数}PTree;结点结构树结构树的存储结构——双亲表示法abcdefhgi如何找孩子结点找双亲容易找孩子难 PTreeT;T.r=0;//根结点位置T.n=9;//结点个数601234578dataparentT.nodesacdefghib-101124440 双亲表示法树的存储结构——双亲表示法
孩子表示法 多重链表:每个结点有多个指针域,分别指向其子树的根data child1 child2 ………. childDdata degree child1 child2 ………. childd 结点同构:结点的指针个数相等,为树的度D 结点不同构:结点指针个数不等,为该结点的度dABCDEFH树的存储结构——孩子表示法ACBDEFH
孩子链表:每个结点的孩子结点用单链表存储,再用含n个元素的结构数组指向每个孩子链表树的存储结构——孩子表示法abcdefhgi12^34^5^^^^^^601234578acdefghib867^
typedefstruct CTNode{ int child;struct CTNode *next;}*ChildPtr;孩子结点孩子链表:每个结点的孩子结点用单链表存储,再用含n个元素的结构数组指向每个孩子链表树的存储结构——孩子表示法abcdefhgi12^34^5^^^^^^601234578acdefghib867^
typedefstruct{ TElemType data;ChildPtrfirstchild;}CTBox;孩头子结链点表孩子链表:每个结点的孩子结点用单链表存储,再用含n个元素的结构数组指向每个孩子链表树的存储结构——孩子表示法abcdefhgi12^34^5^^^^^^601234578acdefghib867^
typedefstruct{CTBoxnodes[Max_Tree_Size];int r, n;//根结点的位置、结点个数}CTree;树结构CTreeT;T.r=0;//根结点位置T.n=9;//结点个数T.nodes如何找双亲结点找孩子容易找双亲难带双亲的孩子链表501234678acdefghibdatafirstchild12348675^^^^^^^^^-101124440parentabcdefhgi树的存储结构——双亲孩子表示法找孩子容易找双亲容易
孩子兄弟表示法(二叉树表示法) 实现:用二叉链表作树的存储结构,链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点firstchild data nextsibling
typedefstruct CSnode{ElemType data;//数据域struct CSnode *firstchild, *nextsibling;//指向第一个孩子、下一个兄弟}CSNode, *CSTree;结点结构树的存储结构——孩子兄弟表示法孩子兄弟表示法(二叉树表示法) 实现:用二叉链表作树的存储结构,链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点树的存储结构——孩子兄弟表示法abcdefhgiabcdefghi^^^^^^^^^^abcdefghi^^^^^^^^^^
孩子兄弟表示法(二叉树表示法) 实现:用二叉链表作树的存储结构,链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点树的存储结构——孩子兄弟表示法abcdefhgiabcdefghi^^^^^^^^^^ 特点 操作容易如何查找某结点的第i个孩子? 破坏了树的层次
实现:按完全二叉树的结点层次编号,依次存放二叉树中的数据元素
#define Max_Tree_Size 100//树中结点最大数目typedefTElemTypeSqBiTree[Max_Tree_Size];// 0号单元存储根结点二叉树的顺序存储表示二叉树的存储结构——顺序存储结构实现:按完全二叉树的结点层次编号,依次存放二叉树中的数据元素二叉树的存储结构——顺序存储结构abcdefg完全二叉树性质 特点: 结点间的父子关系蕴含在其存储位置中 浪费空间,适于存满二叉树和完全二叉树1 2 3 4 5 6 7 8 9 10 11abcde0000fg该存储结构能否反映结点之间的关系?SqBiTreeT;
二叉链表lchild data rchildABCDEFGABCDEFG^^^^^^^^在n个结点的二叉链表中,有个空指针域n+1
typedefstruct BiTNode{ TElemType data;//数据域struct BiTNode *lchild, *rchild;}BiTNode, *BiTree;二叉树的存储结构——链式存储结构找孩子容易找双亲难三叉链表lchild dataparentrchildABCDEFGABCDEFG^^^^^^^^^
typedefstruct TriTNode{ TElemType data;//数据域struct TriTNode *lchild, *rchild,*parent;}TriTNode, *TriTree;二叉树的存储结构——链式存储结构找孩子容易找双亲容易ACBED树ABCDE二叉树A ^^ BC^ D ^^ E ^ABCDEABCDE对应存储存储解释解释^^^^^^^^^^^^ 树与二叉树的转换:
加线(连兄弟):在兄弟之间加一连线抹线(断父子):对每个结点,除了其左孩子外,去除其与其余孩子之间的关系旋转:以树的根结点为轴心,将整树顺时针转45°ABCDEFGHIABCDEFGHIABCDEFGHI为什么要“连兄弟、断父子”?将树转换成二叉树转换成二叉树以后,结点的下一个兄弟”变成”其右孩子树转换成的二叉树其右子树一定为空
加线(连祖孙):若p结点是双亲结点的左孩子,则将p的右孩子,右孩子的右孩子,……沿分支找到的所有右孩子,都与p的双亲用线连起来抹线(断父子):抹掉原二叉树中双亲与右孩子之间的连线调整:将结点按层次排列,形成树结构ABCDEFGHIABCDEFGHIABCDEFGHI只能将根的右子树为空的二叉树转换成树将二叉树转换成树为什么要“连祖孙、断父子”?转换成树以后,某结点的左孩子p的右孩子、右孩子的右孩子,……都”变成”p的兄弟
将各棵树分别转换成二叉树 将每棵树的根结点用线相连 以第一棵树根结点为二叉树的根,再以根结点为轴心,顺时针旋转,构成二叉树型结构森林转换成的二叉树其右子树非空将森林转换成二叉树ABCDEFGHIJABCDEFGHIJABCDEFGHIJ
抹线:将二叉树中根结点与其右孩子连线,及沿右分支搜索到的所有右孩子间连线全部抹掉,使之变成孤立的二叉树 还原:将孤立的二叉树还原成树将二叉树转换成森林ABCDEFGHIJABCDEFGHIJABCDEFGHIJ右子树不为空的二叉树只能转换成森林
遍历—— 按一定规律走遍树的各个结点,且使每一结点仅被访问一次(“访问”的含义很广,如对结点进行处理、输出结点信息,等等) 即找一个完整而有规律的走法,以得到树中所有结点的一个线性排列 遍历的关键在于访问结点的次序树与二叉树的遍历
DLRLDR、LRD、DLRRDL、RLD、DRL 常用方法 先序遍历:先访问根结点,然后分别先序遍历左子树、右子树 中序遍历:先中序遍历左子树,然后访问根结点,最后中序遍历右子树 后序遍历:先后序遍历左、右子树,然后访问根结点 按层次遍历:从上到下、从左到右访问各结点 二叉树遍历的三个“子任务”:
ADBCD L RAD L RD L R>B>>D>>CD L R先序遍历序列:A B D C先序遍历:二叉树的遍历
ADBCL D RBL D RL D R>A>>D>>CL D R中序遍历序列:B D A C中序遍历:二叉树的遍历
ADBCL R DL R DL R D>A>>D>>CL R D后序遍历序列:D B C A后序遍历:B二叉树的遍历
-+/a*b-efcd先序遍历:中序遍历:后序遍历:层次遍历:-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef二叉树的遍历
ABCDEFG^^^^^^^^
voidPreOrderTraverse(BiTreeT){ if(T){ printf("%d\t",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}} 递归算法:二叉链表存储结构二叉树的遍历算法ABCDEFG^^^^^^^^
voidInOrderTraverse(BiTreeT){ if(T){InOrderTraverse(T->lchild);printf("%d\t",T->data);InOrderTraverse(T->rchild);}}二叉树的遍历算法 递归算法:二叉链表存储结构ABCDEFG^^^^^^^^
遍历的应用——可以对结点做各种处理(不改变结点之间关系),如修改或输出、使用结点信息等
voidPostOrderTraverse(BiTreeT){ if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%d\t",T->data);}} 递归算法:二叉链表存储结构二叉树的遍历算法主程序pre( T )返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(TL);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T>左是空返回pre(T R);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(T R);先序序列:
voidPreOrderTraverse(BiTreeT){ if(T){ printf("%d\t",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}ABDC按先序遍历序列建立二叉树的二叉链表,已知先序序列为:A B C D E F ABCDEFA ^B^ C ^D^ E^^ F ^二叉树遍历算法的应用对于二叉树,若能将某问题分解到其左、右子树上分别进行相同操作,则可将递归的遍历算法进行适当改写来实现。对哪种遍历算法进行改写?^^^^^^^
按先序遍历序列建立二叉树的二叉链表,已知先序序列为:A B C D E F ABCDEFA ^B^ C ^D^ E^^ F ^二叉树遍历算法的应用
voidPreOrderTraverse(BiTreeT){if(T){printf("%d\t",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}如何进行改写?接收字符……判断字符是否为空字符不为空,则建立新结点并赋值再建立其左、右孩子按先序遍历序列建立二叉树的二叉链表,已知先序序列为:A B C D E F ABCDEF二叉树遍历算法的应用A ^B^ C ^D^ E^^ F ^
StatusCreateBiTree(BiTree &T){charch;scanf("%c",&ch);if(ch==' ') T = NULL;else{T = (BiTNode *)malloc(sizeof(BiTNode));T->data = ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}returnOK;}定义变量接收字符若为空格,则树的根为空建立结点并赋值以T的左、右孩子为参数递归调用统计二叉树中叶子结点个数算法——左子树叶子数+右子树叶子数LeafCount1( ){static intcount;
if( T ){if((T->lchild==NULL)&& (T->rchild==NULL))count++;else{}}returncount;}ABCDEF二叉树遍历算法的应用intBitree T局部静态变量具有继承性定义变量T不为空时求叶子结点数判断T是否为叶子结点count=LeafCount1(T->lchild);count=LeafCount1(T->rchild);求T左、右子树上的叶子结点数统计二叉树中叶子结点个数算法——左子树叶子数+右子树叶子数
voidLeafCount2 (BiTreeT, int&count){if( T ){if((T->lchild==NULL)&& (T->rchild==NULL))count++;LeafCount2( T->lchild, count);LeafCount2( T->rchild, count);}}ABCDEF二叉树遍历算法的应用T不为空时求叶子结点数判断T是否为叶子结点求T左、右子树上的叶子结点数求二叉树深度算法——max{左子树深度+1,右子树深度+1}intDepth(BiTree T ){intdepthval, depthLeft, depthRight;
if( T==NULL ) depthval = 0;else{depthLeft =Depth(T->lchild);depthRight=Depth(T->rchild);depthval=depthLeft>depthRight ? depthLeft+1:depthRight+1;}returndepthval;}ABCDEF应对哪种遍历算法进行改写?二叉树遍历算法的应用定义变量T为空时,以T为根的树深度为0分别求T左、右子树的深度由二叉树先序序列和中序序列,构造二叉树二叉树的先序序列二叉树的中序序列左子树左子树右子树右子树根根a b c d e f gc b d a e g f例:aabbeeffabcdefg^^^^^^^^先序序列中序序列二叉树遍历算法的应用
Ch5_1.c 思考:已知二叉树中序序列和后序序列,能构造二叉树吗? 思考:已知二叉树先序序列和后序序列,能构造二叉树吗? 思考:已知二叉树层次遍历序列和中序序列,能构造二叉树吗?二叉树遍历算法的应用二叉树的先序序列二叉树的中序序列左子树左子树右子树右子树根根二叉树的后序序列二叉树的层次序列左子树右子树根根第一层第二层……
AC例:中序序列为:D B G E H J A C I F后序序列为:D G J H E B I F C AFI 由二叉树中序序列和后序序列,构造二叉树二叉树遍历算法的应用二叉树的中序序列左子树右子树根二叉树的后序序列左子树右子树根AACCFFII
ABDC例:中序序列为:D B G E H J A C I F后序序列为:D G J H E B I F C AFI 由二叉树中序序列和后序序列,构造二叉树二叉树遍历算法的应用二叉树的中序序列左子树右子树根二叉树的后序序列左子树右子树根AACCFFIIBBDD
ABDCE例:中序序列为:D B G E H J A C I F后序序列为:D G J H E B I F C AFI 由二叉树中序序列和后序序列,构造二叉树二叉树遍历算法的应用二叉树的中序序列左子树右子树根二叉树的后序序列左子树右子树根AACCFFIIBBDDEEGGGHHHJJJ
ABDCGE例:层次序列为:A B C D E F G H I J中序序列为:D B G E H J A C I FFHIJ 由二叉树层次序列和中序序列,构造二叉树二叉树遍历算法的应用二叉树的层次序列根第一层第二层……二叉树的中序序列左子树右子树根AABBCCDDEEFFGGHHIIJJ
访问:AB CD E FG0 1 2 3 4 5 6 7frAB^ D ^E^^ G^^ C^ F ^二叉树的层次遍历非递归算法
0 1 2 3 4 5 6 7frAB^ D ^E^^ G^^ C^ F ^A二叉树的层次遍历非递归算法
访问:A0 1 2 3 4 5 6 7frAB^ D ^E^^ G^^ C^ F ^二叉树的层次遍历非递归算法
访问:A0 1 2 3 4 5 6 7frBAB^ D ^E^^ G^^ C^ F ^二叉树的层次遍历非递归算法
访问:A0 1 2 3 4 5 6 7frBCAB^ D ^E^^ G^^ C^ F ^二叉树的层次遍历非递归算法
访问:A0 1 2 3 4 5 6 7frCBAB^ D ^E^^ G^^ C^ F ^二叉树的层次遍历非递归算法
访问:A0 1 2 3 4 5 6 7frCBDAB^ D ^E^^ G^^ C^ F ^二叉树的层次遍历非递归算法
访问:A0 1 2 3 4 5 6 7frCBDEAB^ D ^E^^ G^^ C^ F ^二叉树的层次遍历非递归算法
访问:A0 1 2 3 4 5 6 7frBDECAB^ D ^E^^ G^^ C^ F ^二叉树的层次遍历非递归算法
访问:A0 1 2 3 4 5 6 7frBDECFAB^ D ^E^^ G^^ C^ F ^二叉树的层次遍历非递归算法
访问:A0 1 2 3 4 5 6 7frBECFDAB^ D ^E^^ G^^ C^ F ^二叉树的层次遍历非递归算法
访问:A0 1 2 3 4 5 6 7frBECFDAB^ D ^E^^ G^^ C^ F ^二叉树的层次遍历非递归算法
访问:A0 1 2 3 4 5 6 7frBECFDAB^ D ^E^^ G^^ C^ F ^G二叉树的层次遍历非递归算法
访问:A0 1 2 3 4 5 6 7fBECDFAB^ D ^E^^ G^^ C^ F ^Gr二叉树的层次遍历非递归算法
访问:A0 1 2 3 4 5 6 7fBECDFAB^ D ^E^^ G^^ C^ F ^Gr结束二叉树的层次遍历非递归算法
访问:A0 1 2 3 4 5 6 7fBECDFAB^ D ^E^^ G^^ C^ F ^Gr结束
voidLevelTrave(BiTreeT){ int f=0,r=0;BiTree p, q[M];q[r++]=T;while(f<r){p=q[f++];printf("%c\t",p->data);if(p->lchild)q[r++]=p->lchild;if(p->rchild)q[r++]=p->rchild;}}二叉树的层次遍历非递归算法根结点入队当队列不为空时出队将非空孩子入队常用方法 先根(序)遍历:先访问树的根结点,然后依次先根遍历根的每棵子树“根左右” 后根(序)遍历:先依次后根遍历每棵子树,然后访问根结点“左右根” 按层次遍历:先访问第一层上的结点,然后依次遍历第二层,……第n层的结点树的遍历先根遍历最左边一棵子树先根遍历下一棵子树根……后根遍历下一棵子树后根遍历最左边一棵子树……根根第一层第二层……
ABCDEFGHIJKLMNO先序遍历:后序遍历:层次遍历:ABEFIGCDHJKLNOMEIFGBCJKNOLMHDAABCDEFGHIJKLMNO树的遍历
递归算法:
#define D 3//树的度typedefstruct node{ ElemType data;//数据域struct node *ch[D];//D个孩子指针域}CNode,*CTree;data child1 child2 ………. childD 非递归算法:结点同构的多重链表结构树的遍历算法ABCDEFHACBDEFH T访问:A B E F C D H能否用队列进行存储?树的先根遍历非递归算法访问某结点时,需要存储其所有孩子的信息
piP->AABCDEFHACBDEFH T访问:A B E F C D H
voidpreroot( CTreeT){ int i=0, j;CNode *p, *s[M];s[i++]=T;while(i>0){p=s[--i];printf("%d\t",p->data);for(j=D-1;j>=0;j--)if(p->ch[j]!=NULL)s[i++]=p->ch[j];}}树的先根遍历非递归算法pi访问:AABCDEFHACBDEFH
voidpreroot( CTreeT){ int i=0, j;CNode *p, *s[M];s[i++]=T;while(i>0){p=s[--i];printf("%d\t",p->data);for(j=D-1;j>=0;j--)if(p->ch[j]!=NULL)s[i++]=p->ch[j];}}树的先根遍历非递归算法piP->D访问:AABCDEFHACBDEFH 树的先根遍历非递归算法
voidpreroot( CTreeT){ int i=0, j;CNode *p, *s[M];s[i++]=T;while(i>0){p=s[--i];printf("%d\t",p->data);for(j=D-1;j>=0;j--)if(p->ch[j]!=NULL)s[i++]=p->ch[j];}}piP->D访问:AP->CABCDEFHACBDEFH 树的先根遍历非递归算法
voidpreroot( CTreeT){ int i=0, j;CNode *p, *s[M];s[i++]=T;while(i>0){p=s[--i];printf("%d\t",p->data);for(j=D-1;j>=0;j--)if(p->ch[j]!=NULL)s[i++]=p->ch[j];}}piP->D访问:AP->CP->BABCDEFHACBDEFH 树的先根遍历非递归算法
voidpreroot( CTreeT){ int i=0, j;CNode *p, *s[M];s[i++]=T;while(i>0){p=s[--i];printf("%d\t",p->data);for(j=D-1;j>=0;j--)if(p->ch[j]!=NULL)s[i++]=p->ch[j];}}piP->D访问:A BP->CABCDEFHACBDEFH 树的先根遍历非递归算法
voidpreroot( CTreeT){ int i=0, j;CNode *p, *s[M];s[i++]=T;while(i>0){p=s[--i];printf("%d\t",p->data);for(j=D-1;j>=0;j--)if(p->ch[j]!=NULL)s[i++]=p->ch[j];}}piP->D访问:A BP->CP->FABCDEFHACBDEFH 树的先根遍历非递归算法
voidpreroot( CTreeT){ int i=0, j;CNode *p, *s[M];s[i++]=T;while(i>0){p=s[--i];printf("%d\t",p->data);for(j=D-1;j>=0;j--)if(p->ch[j]!=NULL)s[i++]=p->ch[j];}}piP->D访问:A BP->CP->FP->EABCDEFHACBDEFH 树的先根遍历非递归算法
voidpreroot( CTreeT){ int i=0, j;CNode *p, *s[M];s[i++]=T;while(i>0){p=s[--i];printf("%d\t",p->data);for(j=D-1;j>=0;j--)if(p->ch[j]!=NULL)s[i++]=p->ch[j];}}iP->D访问:A B EP->CP->FpABCDEFHACBDEFH 树的先根遍历非递归算法
voidpreroot( CTreeT){ int i=0, j;CNode *p, *s[M];s[i++]=T;while(i>0){p=s[--i];printf("%d\t",p->data);for(j=D-1;j>=0;j--)if(p->ch[j]!=NULL)s[i++]=p->ch[j];}}iP->D访问:A B E FP->CpABCDEFHACBDEFH 树的先根遍历非递归算法
voidpreroot( CTreeT){ int i=0, j;CNode *p, *s[M];s[i++]=T;while(i>0){p=s[--i];printf("%d\t",p->data);for(j=D-1;j>=0;j--)if(p->ch[j]!=NULL)s[i++]=p->ch[j];}}iP->D访问:A B E F CpABCDEFHACBDEFH 树的先根遍历非递归算法
voidpreroot( CTreeT){ int i=0, j;CNode *p, *s[M];s[i++]=T;while(i>0){p=s[--i];printf("%d\t",p->data);for(j=D-1;j>=0;j--)if(p->ch[j]!=NULL)s[i++]=p->ch[j];}}i访问:A B E F C DpABCDEFHACBDEFH 树的先根遍历非递归算法
voidpreroot( CTreeT){ int i=0, j;CNode *p, *s[M];s[i++]=T;while(i>0){p=s[--i];printf("%d\t",p->data);for(j=D-1;j>=0;j--)if(p->ch[j]!=NULL)s[i++]=p->ch[j];}}i访问:A B E F C DpP->HABCDEFHACBDEFH 树的先根遍历非递归算法
voidpreroot( CTreeT){ int i=0, j;CNode *p, *s[M];s[i++]=T;while(i>0){p=s[--i];printf("%d\t",p->data);for(j=D-1;j>=0;j--)if(p->ch[j]!=NULL)s[i++]=p->ch[j];}}i访问:A B E F C D Hp结束ABCDEFHACBDEFH 树的先根遍历非递归算法
voidpreroot( CTreeT){ int i=0, j;CNode *p, *s[M];s[i++]=T;while(i>0){p=s[--i];printf("%d\t",p->data);for(j=D-1;j>=0;j--)if(p->ch[j]!=NULL)s[i++]=p->ch[j];}}常用方法先序遍历森林中其余树构成的森林。 先序遍历:若森林不空,则先序遍历森林中第一棵树的子树森林;访问森林中第一棵树的根结点;即:从左至右先根遍历森林中每一棵树。森林的遍历ABCDEFGHIJ先序遍历序列:ABCDEFGHIJABCDEFGHIJ先序遍历森林先序遍历对应的二叉树ABCDEFGHIJABCDEFGHIJ
常用方法 中序遍历:若森林不空,则森林的遍历ABCDEFGHIJABCDEFGHIJ中序遍历森林中其余树构成的森林。中序遍历森林中第一棵树的子树森林;访问森林中第一棵树的根结点;即:从左至右后根遍历森林中每一棵树。中序遍历序列:BCDAFEHJIG中序遍历森林中序遍历对应的二叉树ABCDEFGHIJABCDEFGHIJ
同一组权值构造不同二叉树的带权路径长度对比:4 个结点权值分别为 7、5、2、4,树中叶子结点的路径长度不同,WPL 相差明显。
| 二叉树 | 各权值到根的路径长度 | WPL |
|---|---|---|
| 二叉树一 | 7×3、5×3、2×1、4×2 | 46 |
| 二叉树二(哈夫曼树) | 7×1、5×2、2×3、4×3 | 35 |
| 二叉树三 | 7×2、5×2、2×2、4×2 | 36 |
哈夫曼树的结构特点是权值大的结点更靠近根结点;表中 WPL 由课件给出的计算式汇总,最小者为哈夫曼树的 35。
例有4个结点,权值分别为7,5,2,4,构造有4个叶子结点的二叉树abcd7524WPL=7*1+5*2+2*3+4*3=35Huffman树cd24b5a7bcd24a75Huffman树不唯一
构造Huffman树步骤 根据给定的n个权值{w1,w2,……wn},构造n棵只有根结点的二叉树,令起权值为wj 在森林中选取两棵根结点权值最小的树作左右子树,构造一棵新的二叉树,置新二叉树根结点权值为其左右子树根结点权值之和 在森林中删除这两棵树,同时将新得到的二叉树加入森林中 重复上述两步,直到只含一棵树为止,这棵树即哈夫曼树 重复次数:n-1次Huffman树的构造
例a7b5c2d461811带权路径长度WPL=7*1+5*2+2*3+4*3=35Huffman树的构造
例w={5, 29, 7, 8, 14, 23, 3, 11}51429782331181519294258100一棵有n个叶子结点的Huffman树有2n-1个结点带权路径长度WPL=23*2+11*3+5*4+3*4 +29*2+14*3+7*4 +8*4 =271Huffman树的构造
百分制转换成五分制的最佳判定树:按各分数段人数比例构造判定树,可减少比较次数;下表列出等级、分数段与对应比例。
| 等级 | 分数段 | 比例 |
|---|---|---|
| A | 90~100 | 0.10 |
| B | 80~89 | 0.30 |
| C | 70~79 | 0.40 |
| D | 60~69 | 0.15 |
| E | 0~59 | 0.05 |
课件指出 80% 以上的学生需要经过 2 次以上的比较,因此按比例构造哈夫曼判定树可提升判定效率。
等级分数段比例ABCDE0~5960~6970~7980~8990~1000.050.150.400.300.10构造以分数的分布比例为权值的哈夫曼树可得最佳判定算法70 a<80a<60CYNBYNDYNEYNA80 a<9060 a<70EA0.15D0.30B0.60C1.00 最佳判定树Huffman树的应用
等长编码与不等长编码对比:以 ABACCDA 为例,等长编码译码唯一但码长较长,不等长编码码长更短但可能产生前缀歧义。
| 字符 | 等长编码 | 不等长编码 |
|---|---|---|
| A | 00 | 0 |
| B | 01 | 00 |
| C | 10 | 1 |
| D | 11 | 01 |
原文 ABACCDA 用等长编码得到 00010010101100,用不等长编码得到 000011010;此处的不等长编码中 A 的编码是 B 的前缀,仅作为反例说明,不能保证唯一译码。
字符集 D={C,A,S,T,;} 的哈夫曼编码:按字符出现频率构造哈夫曼树,左分支标 0、右分支标 1,从根到叶子的 0/1 序列即为该字符的编码。
| 字符 | 出现频率 | 哈夫曼编码 |
|---|---|---|
| C | 2 | 110 |
| A | 4 | 10 |
| S | 2 | 111 |
| T | 3 | 00 |
| ; | 3 | 01 |
原文编码片段存在粘连,表中编码按哈夫曼树构造规则整理;哈夫曼编码保证任一字符的编码不是其他字符编码的前缀,且电文总长最短。
译码:从Huffman树根开始,从待译码电文中逐位取码。若编码是“0”,则向左走;若编码是“1”,则向右走,一旦到达叶子结点,则译出一个字符;再重新从根出发,直到电文结束例若发送电文是{CAS;CAT;SAT;AT}其编码“”若收到电文为“1101000”译文只能是“” Huffman编码:数据通信用的二进制编码Huffman树的应用CATCS22433T;64A81400001111T :; :A :C :S :00011011011111010111011101000011111000011000
掌握树的基本概念和术语本章小结End掌握二叉树的定义、性质和几种特殊形态的二叉树掌握二叉树的存储结构,遍历的定义及其递归算法的实现(及应用)掌握树的存储结构及其遍历过程掌握森林的遍历过程掌握树、森林与二叉树的相互转换掌握哈夫曼树的实现方法及带权路径长度的计算,掌握哈夫曼编码的构造方法
下载地址:{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}