首页计算机计算机基础数据结构 05 第五章 树.pptx

05 第五章 树.pptx

页数:113页文件大小:2.47 MB来源: 数据结构ppt课件

本课件为数据结构第五章树,系统讲解树与二叉树的定义、基本术语与性质,介绍二叉树的顺序与链式存储结构及先序、中序、后序与层次遍历算法,随后扩展到线索二叉树、树与森林的存储及转换,最后讲解哈夫曼树的构造、最佳判定树与哈夫曼编码的应用。

第五章树目录页,列出树的实例、二叉树、存储结构、遍历与二叉树应用等内容
五子棋游戏示意图,说明对弈过程中棋盘状态展开所形成的树型结构
UNIX文件系统结构图,展示根目录与各级子目录文件构成的树型层次关系
查看本课件的文字版(共 113 页,供检索与复制)

第1页:第五章树目录

实例树的定义二叉树第五章树树型结构的存储树和二叉树的遍历二叉树的应用本章小结

第2页:实例:五子棋游戏

五子棋游戏……..……..…...…...…...…...树的实例

第3页:实例:UNIX文件系统结构

UNIX文件系统结构/(root)libuseretcbinmathdsswyintaoxieStack.cppQueue.cppTree.cpp人类的族谱各种社会关系各类分类编码编译程序的语法树Internet中的DNS(域名系统)树的实例

第4页:树的定义

树是一类重要的非线性数据结构,是以分支关系定义的层次结构 定义:树(tree)是n(n>=0)个结点的有限集T,其中: 有且仅有一个特定的结点,称为树的根(root) 当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm,其中每一个集合本身又是一棵树,称为根的子树(subtree) 特点: 非空树中存在唯一一个称为根结点 非空树中各子树是互不相交的集合至少存在一个数据元素有两个或两个以上的直接前驱(或直接后继)元素的数据结构树的定义

第5页:树的结构示意:根与子树

A只有根结点的树ABCDEFGHIJKLM有子树的树根子树

第6页:树的基本术语

结点(node)
表示树中的元素,包括数据项及若干指向其子树的分支
结点的度(degree)
结点拥有的子树数
叶子(leaf)
度为0的结点
孩子(child)
结点子树的根称为该结点的孩子
双亲(parents)
孩子结点的上层结点叫该结点的~
兄弟(sibling)
同一双亲的孩子
树的度
一棵树中最大的结点度数
结点的层次(level)
从根结点算起,根为第一层,它的孩子为第二层……
深度(depth)
树中结点的最大层次数
森林(forest)
m(m 0)棵互不相交的树的集合树的基本术语

第7页:树的基本术语示例

结点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树的基本术语子孙

第8页:抽象数据类型树的定义

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抽象数据类型树的定义

第9页:树的基本操作(续)

基本操作(续):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( ) );遍历抽象数据类型树的定义

第10页:二叉树的定义与基本形态

定义:二叉树是n(n 0)个结点的有限集,它或为空树(n=0),或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成 特点 每个结点至多有二棵子树(即不存在度大于2的结点) 二叉树的子树有左、右之分,且其次序不能任意颠倒 基本形态二叉树的定义 空二叉树左、右子树均非空DRL只有根结点二叉树D右子树为空DL左子树为空DR

第11页:抽象数据类型二叉树的定义

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抽象数据类型二叉树的定义

第12页:二叉树的基本操作(续)

基本操作(续):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);求当前结点的右兄弟抽象数据类型二叉树的定义

第13页:二叉树的基本操作(续二)

基本操作(续):}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的右子树抽象数据类型二叉树的定义

第14页:二叉树性质1

二叉树的性质 性质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。

第15页:二叉树性质2

证明:由性质1,可得深度为k的二叉树最大结点数是完全二叉树性质4二叉树的性质 性质2:深度为k的二叉树上至多含2k-1个结点(k≥1)等比数列求和:

第16页:二叉树性质3

性质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

第17页:满二叉树

满二叉树 定义:

特点:每一层上的结点数都是最大结点数,除最下层的叶子结点外,每个结点的度都为2。满二叉树及其编号完全二叉树特殊形式的二叉树123456789101112131415

第18页:完全二叉树

完全二叉树 定义:深度为k,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称为~完全二叉树及其编号示例 特点 度小于2的结点只可能在层次最大的两层上出现,如果某个结点没有左孩子,那么它一定没有右孩子,该结点为叶子结点 除最后一层外,每层都充满了结点,最下面一层结点都集中在该层的最左边满二叉树顺序存储完全二叉树中可能有度为1的结点吗?特殊形式的二叉树123456891011127

第19页:二叉树形态示例

1231145891213671014151231145891267101234567123456

第20页:完全二叉树性质4

性质4:证明:设深度为k,根据二叉树性质2知:n ≤2k-1,2k-1≤n<2k,于是有:性质2完全二叉树性质具有n个结点的完全二叉树的深度为 log2n +1123114589126710完全二叉树及其编号示例2k-1-1<

第21页:完全二叉树性质5

性质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完全二叉树及其编号示例

第22页:结点i与双亲孩子的关系

性质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与双亲和左、右孩子关系二叉树顺序存储

第23页:树与二叉树的存储结构

树与二叉树的存储结构及其相互转换树的存储结构二叉树的存储结构树与二叉树的相互转换双亲表示法孩子表示法孩子兄弟表示法多重链表孩子链表带双亲的孩子链表顺序存储结构二叉链表三叉链表

第24页:双亲表示法

双亲表示法树的存储应该存储哪些信息?data parent

typedefstruct PTNode{ TElemType data;//数据域int parent;//双亲位置域}PTNode;#define Max_Tree_Size 100//树中结点最大数目typedefstruct{PTNodenodes [Max_Tree_Size];//结点数组int r, n;//根结点的位置和结点个数}PTree;结点结构树结构树的存储结构——双亲表示法

第25页:双亲表示法示例

abcdefhgi如何找孩子结点找双亲容易找孩子难 PTreeT;T.r=0;//根结点位置T.n=9;//结点个数601234578dataparentT.nodesacdefghib-101124440 双亲表示法树的存储结构——双亲表示法

第26页:孩子表示法:多重链表

孩子表示法 多重链表:每个结点有多个指针域,分别指向其子树的根data child1 child2 ………. childDdata degree child1 child2 ………. childd 结点同构:结点的指针个数相等,为树的度D 结点不同构:结点指针个数不等,为该结点的度dABCDEFH树的存储结构——孩子表示法ACBDEFH

第27页:孩子链表

孩子链表:每个结点的孩子结点用单链表存储,再用含n个元素的结构数组指向每个孩子链表树的存储结构——孩子表示法abcdefhgi12^34^5^^^^^^601234578acdefghib867^

typedefstruct CTNode{ int child;struct CTNode *next;}*ChildPtr;孩子结点

第28页:孩子链表的结点结构

孩子链表:每个结点的孩子结点用单链表存储,再用含n个元素的结构数组指向每个孩子链表树的存储结构——孩子表示法abcdefhgi12^34^5^^^^^^601234578acdefghib867^

typedefstruct{ TElemType data;ChildPtrfirstchild;}CTBox;孩头子结链点表

第29页:孩子链表的树结构

孩子链表:每个结点的孩子结点用单链表存储,再用含n个元素的结构数组指向每个孩子链表树的存储结构——孩子表示法abcdefhgi12^34^5^^^^^^601234578acdefghib867^

typedefstruct{CTBoxnodes[Max_Tree_Size];int r, n;//根结点的位置、结点个数}CTree;树结构CTreeT;T.r=0;//根结点位置T.n=9;//结点个数T.nodes如何找双亲结点找孩子容易找双亲难

第30页:带双亲的孩子链表

带双亲的孩子链表501234678acdefghibdatafirstchild12348675^^^^^^^^^-101124440parentabcdefhgi树的存储结构——双亲孩子表示法找孩子容易找双亲容易

第31页:孩子兄弟表示法

孩子兄弟表示法(二叉树表示法) 实现:用二叉链表作树的存储结构,链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点firstchild data nextsibling

typedefstruct CSnode{ElemType data;//数据域struct CSnode *firstchild, *nextsibling;//指向第一个孩子、下一个兄弟}CSNode, *CSTree;结点结构树的存储结构——孩子兄弟表示法

第32页:孩子兄弟表示法示例

孩子兄弟表示法(二叉树表示法) 实现:用二叉链表作树的存储结构,链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点树的存储结构——孩子兄弟表示法abcdefhgiabcdefghi^^^^^^^^^^abcdefghi^^^^^^^^^^

第33页:孩子兄弟表示法的特点

孩子兄弟表示法(二叉树表示法) 实现:用二叉链表作树的存储结构,链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点树的存储结构——孩子兄弟表示法abcdefhgiabcdefghi^^^^^^^^^^ 特点 操作容易如何查找某结点的第i个孩子? 破坏了树的层次

第34页:二叉树的顺序存储表示

实现:按完全二叉树的结点层次编号,依次存放二叉树中的数据元素

#define Max_Tree_Size 100//树中结点最大数目typedefTElemTypeSqBiTree[Max_Tree_Size];// 0号单元存储根结点二叉树的顺序存储表示二叉树的存储结构——顺序存储结构

第35页:二叉树顺序存储示例

实现:按完全二叉树的结点层次编号,依次存放二叉树中的数据元素二叉树的存储结构——顺序存储结构abcdefg完全二叉树性质 特点: 结点间的父子关系蕴含在其存储位置中 浪费空间,适于存满二叉树和完全二叉树1 2 3 4 5 6 7 8 9 10 11abcde0000fg该存储结构能否反映结点之间的关系?SqBiTreeT;

第36页:二叉链表

二叉链表lchild data rchildABCDEFGABCDEFG^^^^^^^^在n个结点的二叉链表中,有个空指针域n+1

typedefstruct BiTNode{ TElemType data;//数据域struct BiTNode *lchild, *rchild;}BiTNode, *BiTree;二叉树的存储结构——链式存储结构找孩子容易找双亲难

第37页:三叉链表

三叉链表lchild dataparentrchildABCDEFGABCDEFG^^^^^^^^^

typedefstruct TriTNode{ TElemType data;//数据域struct TriTNode *lchild, *rchild,*parent;}TriTNode, *TriTree;二叉树的存储结构——链式存储结构找孩子容易找双亲容易

第38页:树与二叉树的转换

ACBED树ABCDE二叉树A ^^ BC^ D ^^ E ^ABCDEABCDE对应存储存储解释解释^^^^^^^^^^^^ 树与二叉树的转换:

  • 以二叉链表为树与二叉树之间的对应关系,即给定一棵树,可以找到唯一的一棵二叉树与之对应。
  • 用一棵二叉树表示一棵树,可以很好地解决树的存储问题,而且树的各种操作均可转换为对应二叉树的操作。树与二叉树的相互转换

第39页:将树转换成二叉树

加线(连兄弟):在兄弟之间加一连线抹线(断父子):对每个结点,除了其左孩子外,去除其与其余孩子之间的关系旋转:以树的根结点为轴心,将整树顺时针转45°ABCDEFGHIABCDEFGHIABCDEFGHI为什么要“连兄弟、断父子”?将树转换成二叉树转换成二叉树以后,结点的下一个兄弟”变成”其右孩子树转换成的二叉树其右子树一定为空

第40页:将二叉树转换成树

加线(连祖孙):若p结点是双亲结点的左孩子,则将p的右孩子,右孩子的右孩子,……沿分支找到的所有右孩子,都与p的双亲用线连起来抹线(断父子):抹掉原二叉树中双亲与右孩子之间的连线调整:将结点按层次排列,形成树结构ABCDEFGHIABCDEFGHIABCDEFGHI只能将根的右子树为空的二叉树转换成树将二叉树转换成树为什么要“连祖孙、断父子”?转换成树以后,某结点的左孩子p的右孩子、右孩子的右孩子,……都”变成”p的兄弟

第41页:将森林转换成二叉树

将各棵树分别转换成二叉树 将每棵树的根结点用线相连 以第一棵树根结点为二叉树的根,再以根结点为轴心,顺时针旋转,构成二叉树型结构森林转换成的二叉树其右子树非空将森林转换成二叉树ABCDEFGHIJABCDEFGHIJABCDEFGHIJ

第42页:将二叉树转换成森林

抹线:将二叉树中根结点与其右孩子连线,及沿右分支搜索到的所有右孩子间连线全部抹掉,使之变成孤立的二叉树 还原:将孤立的二叉树还原成树将二叉树转换成森林ABCDEFGHIJABCDEFGHIJABCDEFGHIJ右子树不为空的二叉树只能转换成森林

第43页:遍历的定义

遍历—— 按一定规律走遍树的各个结点,且使每一结点仅被访问一次(“访问”的含义很广,如对结点进行处理、输出结点信息,等等) 即找一个完整而有规律的走法,以得到树中所有结点的一个线性排列 遍历的关键在于访问结点的次序树与二叉树的遍历

第44页:二叉树的遍历方法

DLRLDR、LRD、DLRRDL、RLD、DRL 常用方法 先序遍历:先访问根结点,然后分别先序遍历左子树、右子树 中序遍历:先中序遍历左子树,然后访问根结点,最后中序遍历右子树 后序遍历:先后序遍历左、右子树,然后访问根结点 按层次遍历:从上到下、从左到右访问各结点 二叉树遍历的三个“子任务”:

  • 访问根结点
  • 遍历左子树
  • 遍历右子树二叉树的遍历

第45页:先序遍历

ADBCD L RAD L RD L R>B>>D>>CD L R先序遍历序列:A B D C先序遍历:二叉树的遍历

第46页:中序遍历

ADBCL D RBL D RL D R>A>>D>>CL D R中序遍历序列:B D A C中序遍历:二叉树的遍历

第47页:后序遍历

ADBCL R DL R DL R D>A>>D>>CL R D后序遍历序列:D B C A后序遍历:B二叉树的遍历

第48页:遍历序列练习:表达式树

-+/a*b-efcd先序遍历:中序遍历:后序遍历:层次遍历:-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef二叉树的遍历

第49页:先序遍历递归算法

ABCDEFG^^^^^^^^

voidPreOrderTraverse(BiTreeT){ if(T){ printf("%d\t",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}} 递归算法:二叉链表存储结构二叉树的遍历算法

第50页:中序遍历递归算法

ABCDEFG^^^^^^^^

voidInOrderTraverse(BiTreeT){ if(T){InOrderTraverse(T->lchild);printf("%d\t",T->data);InOrderTraverse(T->rchild);}}二叉树的遍历算法 递归算法:二叉链表存储结构

第51页:后序遍历递归算法

ABCDEFG^^^^^^^^

遍历的应用——可以对结点做各种处理(不改变结点之间关系),如修改或输出、使用结点信息等

voidPostOrderTraverse(BiTreeT){ if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%d\t",T->data);}} 递归算法:二叉链表存储结构二叉树的遍历算法

第52页:先序遍历递归执行过程

主程序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

第53页:按先序序列建立二叉链表

按先序遍历序列建立二叉树的二叉链表,已知先序序列为:A B C D E F ABCDEFA ^B^ C ^D^ E^^ F ^二叉树遍历算法的应用对于二叉树,若能将某问题分解到其左、右子树上分别进行相同操作,则可将递归的遍历算法进行适当改写来实现。对哪种遍历算法进行改写?^^^^^^^

第54页:建立二叉链表的改写思路

按先序遍历序列建立二叉树的二叉链表,已知先序序列为: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);}}如何进行改写?接收字符……判断字符是否为空字符不为空,则建立新结点并赋值再建立其左、右孩子

第55页:建立二叉链表的算法

按先序遍历序列建立二叉树的二叉链表,已知先序序列为: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的左、右孩子为参数递归调用

第56页:统计叶子结点个数(一)

统计二叉树中叶子结点个数算法——左子树叶子数+右子树叶子数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左、右子树上的叶子结点数

第57页:统计叶子结点个数(二)

统计二叉树中叶子结点个数算法——左子树叶子数+右子树叶子数

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左、右子树上的叶子结点数

第58页:求二叉树深度算法

求二叉树深度算法——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左、右子树的深度

第59页:由先序和中序序列构造二叉树

由二叉树先序序列和中序序列,构造二叉树二叉树的先序序列二叉树的中序序列左子树左子树右子树右子树根根a b c d e f gc b d a e g f例:aabbeeffabcdefg^^^^^^^^先序序列中序序列二叉树遍历算法的应用

第60页:不同序列组合能否构造二叉树

Ch5_1.c 思考:已知二叉树中序序列和后序序列,能构造二叉树吗? 思考:已知二叉树先序序列和后序序列,能构造二叉树吗? 思考:已知二叉树层次遍历序列和中序序列,能构造二叉树吗?二叉树遍历算法的应用二叉树的先序序列二叉树的中序序列左子树左子树右子树右子树根根二叉树的后序序列二叉树的层次序列左子树右子树根根第一层第二层……

第61页:由中序和后序构造二叉树(一)

AC例:中序序列为:D B G E H J A C I F后序序列为:D G J H E B I F C AFI 由二叉树中序序列和后序序列,构造二叉树二叉树遍历算法的应用二叉树的中序序列左子树右子树根二叉树的后序序列左子树右子树根AACCFFII

第62页:由中序和后序构造二叉树(二)

ABDC例:中序序列为:D B G E H J A C I F后序序列为:D G J H E B I F C AFI 由二叉树中序序列和后序序列,构造二叉树二叉树遍历算法的应用二叉树的中序序列左子树右子树根二叉树的后序序列左子树右子树根AACCFFIIBBDD

第63页:由中序和后序构造二叉树(三)

ABDCE例:中序序列为:D B G E H J A C I F后序序列为:D G J H E B I F C AFI 由二叉树中序序列和后序序列,构造二叉树二叉树遍历算法的应用二叉树的中序序列左子树右子树根二叉树的后序序列左子树右子树根AACCFFIIBBDDEEGGGHHHJJJ

第64页:由层次和中序序列构造二叉树

ABDCGE例:层次序列为:A B C D E F G H I J中序序列为:D B G E H J A C I FFHIJ 由二叉树层次序列和中序序列,构造二叉树二叉树遍历算法的应用二叉树的层次序列根第一层第二层……二叉树的中序序列左子树右子树根AABBCCDDEEFFGGHHIIJJ

第65页:层次遍历非递归算法思想

访问:AB CD E FG0 1 2 3 4 5 6 7frAB^ D ^E^^ G^^ C^ F ^二叉树的层次遍历非递归算法

  • 算法思想:
  • 使用队列实现层次遍历二叉树的非递归算法
  • 首先,将二叉树的根结点入队
  • 队头元素(某子树的根)出队并访问,再将其非空左、右孩子入队,则出队次序为从左向右的下一层结点
  • 如此反复直到队空为止

第66页:层次遍历:根结点入队

0 1 2 3 4 5 6 7frAB^ D ^E^^ G^^ C^ F ^A二叉树的层次遍历非递归算法

  • 算法思想:
  • 使用队列实现层次遍历二叉树的非递归算法
  • 首先,将二叉树的根结点入队
  • 队头元素(某子树的根)出队并访问,再将其非空左、右孩子入队,则出队次序为从左向右的下一层结点
  • 如此反复直到队空为止

第67页:层次遍历:出队访问A

访问:A0 1 2 3 4 5 6 7frAB^ D ^E^^ G^^ C^ F ^二叉树的层次遍历非递归算法

  • 算法思想:
  • 使用队列实现层次遍历二叉树的非递归算法
  • 首先,将二叉树的根结点入队
  • 队头元素(某子树的根)出队并访问,再将其非空左、右孩子入队,则出队次序为从左向右的下一层结点
  • 如此反复直到队空为止

第68页:层次遍历:孩子入队

访问:A0 1 2 3 4 5 6 7frBAB^ D ^E^^ G^^ C^ F ^二叉树的层次遍历非递归算法

  • 算法思想:
  • 使用队列实现层次遍历二叉树的非递归算法
  • 首先,将二叉树的根结点入队
  • 队头元素(某子树的根)出队并访问,再将其非空左、右孩子入队,则出队次序为从左向右的下一层结点
  • 如此反复直到队空为止

第69页:层次遍历:继续入队

访问:A0 1 2 3 4 5 6 7frBCAB^ D ^E^^ G^^ C^ F ^二叉树的层次遍历非递归算法

  • 算法思想:
  • 使用队列实现层次遍历二叉树的非递归算法
  • 首先,将二叉树的根结点入队
  • 队头元素(某子树的根)出队并访问,再将其非空左、右孩子入队,则出队次序为从左向右的下一层结点
  • 如此反复直到队空为止

第70页:层次遍历:再次出队

访问:A0 1 2 3 4 5 6 7frCBAB^ D ^E^^ G^^ C^ F ^二叉树的层次遍历非递归算法

  • 算法思想:
  • 使用队列实现层次遍历二叉树的非递归算法
  • 首先,将二叉树的根结点入队
  • 队头元素(某子树的根)出队并访问,再将其非空左、右孩子入队,则出队次序为从左向右的下一层结点
  • 如此反复直到队空为止

第71页:层次遍历:D入队

访问:A0 1 2 3 4 5 6 7frCBDAB^ D ^E^^ G^^ C^ F ^二叉树的层次遍历非递归算法

  • 算法思想:
  • 使用队列实现层次遍历二叉树的非递归算法
  • 首先,将二叉树的根结点入队
  • 队头元素(某子树的根)出队并访问,再将其非空左、右孩子入队,则出队次序为从左向右的下一层结点
  • 如此反复直到队空为止

第72页:层次遍历:E入队

访问:A0 1 2 3 4 5 6 7frCBDEAB^ D ^E^^ G^^ C^ F ^二叉树的层次遍历非递归算法

  • 算法思想:
  • 使用队列实现层次遍历二叉树的非递归算法
  • 首先,将二叉树的根结点入队
  • 队头元素(某子树的根)出队并访问,再将其非空左、右孩子入队,则出队次序为从左向右的下一层结点
  • 如此反复直到队空为止

第73页:层次遍历:C出队

访问:A0 1 2 3 4 5 6 7frBDECAB^ D ^E^^ G^^ C^ F ^二叉树的层次遍历非递归算法

  • 算法思想:
  • 使用队列实现层次遍历二叉树的非递归算法
  • 首先,将二叉树的根结点入队
  • 队头元素(某子树的根)出队并访问,再将其非空左、右孩子入队,则出队次序为从左向右的下一层结点
  • 如此反复直到队空为止

第74页:层次遍历:F入队

访问:A0 1 2 3 4 5 6 7frBDECFAB^ D ^E^^ G^^ C^ F ^二叉树的层次遍历非递归算法

  • 算法思想:
  • 使用队列实现层次遍历二叉树的非递归算法
  • 首先,将二叉树的根结点入队
  • 队头元素(某子树的根)出队并访问,再将其非空左、右孩子入队,则出队次序为从左向右的下一层结点
  • 如此反复直到队空为止

第75页:层次遍历:D出队

访问:A0 1 2 3 4 5 6 7frBECFDAB^ D ^E^^ G^^ C^ F ^二叉树的层次遍历非递归算法

  • 算法思想:
  • 使用队列实现层次遍历二叉树的非递归算法
  • 首先,将二叉树的根结点入队
  • 队头元素(某子树的根)出队并访问,再将其非空左、右孩子入队,则出队次序为从左向右的下一层结点
  • 如此反复直到队空为止

第76页:层次遍历:E出队

访问:A0 1 2 3 4 5 6 7frBECFDAB^ D ^E^^ G^^ C^ F ^二叉树的层次遍历非递归算法

  • 算法思想:
  • 使用队列实现层次遍历二叉树的非递归算法
  • 首先,将二叉树的根结点入队
  • 队头元素(某子树的根)出队并访问,再将其非空左、右孩子入队,则出队次序为从左向右的下一层结点
  • 如此反复直到队空为止

第77页:层次遍历:G入队

访问:A0 1 2 3 4 5 6 7frBECFDAB^ D ^E^^ G^^ C^ F ^G二叉树的层次遍历非递归算法

  • 算法思想:
  • 使用队列实现层次遍历二叉树的非递归算法
  • 首先,将二叉树的根结点入队
  • 队头元素(某子树的根)出队并访问,再将其非空左、右孩子入队,则出队次序为从左向右的下一层结点
  • 如此反复直到队空为止

第78页:层次遍历:F出队

访问:A0 1 2 3 4 5 6 7fBECDFAB^ D ^E^^ G^^ C^ F ^Gr二叉树的层次遍历非递归算法

  • 算法思想:
  • 使用队列实现层次遍历二叉树的非递归算法
  • 首先,将二叉树的根结点入队
  • 队头元素(某子树的根)出队并访问,再将其非空左、右孩子入队,则出队次序为从左向右的下一层结点
  • 如此反复直到队空为止

第79页:层次遍历结束

访问:A0 1 2 3 4 5 6 7fBECDFAB^ D ^E^^ G^^ C^ F ^Gr结束二叉树的层次遍历非递归算法

  • 算法思想:
  • 使用队列实现层次遍历二叉树的非递归算法
  • 首先,将二叉树的根结点入队
  • 队头元素(某子树的根)出队并访问,再将其非空左、右孩子入队,则出队次序为从左向右的下一层结点
  • 如此反复直到队空为止

第80页:层次遍历算法

访问: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;}}二叉树的层次遍历非递归算法根结点入队当队列不为空时出队将非空孩子入队

第81页:树的遍历方法

常用方法 先根(序)遍历:先访问树的根结点,然后依次先根遍历根的每棵子树“根左右” 后根(序)遍历:先依次后根遍历每棵子树,然后访问根结点“左右根” 按层次遍历:先访问第一层上的结点,然后依次遍历第二层,……第n层的结点树的遍历先根遍历最左边一棵子树先根遍历下一棵子树根……后根遍历下一棵子树后根遍历最左边一棵子树……根根第一层第二层……

第82页:树的遍历序列示例

ABCDEFGHIJKLMNO先序遍历:后序遍历:层次遍历:ABEFIGCDHJKLNOMEIFGBCJKNOLMHDAABCDEFGHIJKLMNO树的遍历

第83页:树遍历与二叉树遍历的对应

递归算法:

采用孩子
兄弟存储结构
将孩子
兄弟链表看作某棵二叉树的二叉链表表示ACBED树ABCDE二叉树先根遍历树后根遍历树先序遍历对应的二叉树中序遍历对应的二叉树先序:先根:中序:后根:ABCDEBDCEAABCDEBDCEA树的遍历算法ABCDEABCDE

第84页:多重链表结点结构

#define D 3//树的度typedefstruct node{ ElemType data;//数据域struct node *ch[D];//D个孩子指针域}CNode,*CTree;data child1 child2 ………. childD 非递归算法:结点同构的多重链表结构树的遍历算法

第85页:树的先根遍历非递归算法思想

ABCDEFHACBDEFH T访问:A B E F C D H能否用队列进行存储?树的先根遍历非递归算法访问某结点时,需要存储其所有孩子的信息

  • 算法思想:
  • 使用栈实现树的先根遍历非递归算法
  • 首先,将二叉树的根结点入栈
  • 栈顶元素(某子树的根)出栈并访问,再将其所有孩子按照从右向左依次入栈,则出栈次序为从左向右的各棵子树的根
  • 如此反复直到栈空为止

第86页:树的先根遍历算法

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];}}树的先根遍历非递归算法

第87页:先根遍历:访问根结点A

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];}}树的先根遍历非递归算法

第88页:先根遍历:D入栈

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];}}

第89页:先根遍历:C入栈

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];}}

第90页:先根遍历:B入栈

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];}}

第91页:先根遍历:访问B

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];}}

第92页:先根遍历:F入栈

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];}}

第93页:先根遍历:E入栈

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];}}

第94页:先根遍历:访问E

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];}}

第95页:先根遍历:访问F

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];}}

第96页:先根遍历:访问C

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];}}

第97页:先根遍历:访问D

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];}}

第98页:先根遍历:H入栈

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];}}

第99页:先根遍历结束

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];}}

第100页:森林的先序遍历

常用方法先序遍历森林中其余树构成的森林。 先序遍历:若森林不空,则先序遍历森林中第一棵树的子树森林;访问森林中第一棵树的根结点;即:从左至右先根遍历森林中每一棵树。森林的遍历ABCDEFGHIJ先序遍历序列:ABCDEFGHIJABCDEFGHIJ先序遍历森林先序遍历对应的二叉树ABCDEFGHIJABCDEFGHIJ

第101页:森林的中序遍历

常用方法 中序遍历:若森林不空,则森林的遍历ABCDEFGHIJABCDEFGHIJ中序遍历森林中其余树构成的森林。中序遍历森林中第一棵树的子树森林;访问森林中第一棵树的根结点;即:从左至右后根遍历森林中每一棵树。中序遍历序列:BCDAFEHJIG中序遍历森林中序遍历对应的二叉树ABCDEFGHIJABCDEFGHIJ

第102页:哈夫曼树的定义

哈夫曼树(Huffman)
带权路径长度最短的树 定义 路径:从树中一个结点到另一个结点之间的分支构成这两个结点间的~ 路径长度:路径上的分支数 树的路径长度:从树根到每一个结点的路径长度之和 树的带权路径长度:树中所有带权结点的路径长度之和
Huffman树
设有n个权值{w1,w2,……wn},构造一棵有n个叶子结点的二叉树,每个叶子的权值为wi,则wpl最小的二叉树叫~
ABCDEF728带权路径长度wpl
WeightedPathLength二叉树的应用

第103页:带权路径长度对比

同一组权值构造不同二叉树的带权路径长度对比:4 个结点权值分别为 7、5、2、4,树中叶子结点的路径长度不同,WPL 相差明显。

权值为 7、5、2、4 的三棵二叉树 WPL 对比
二叉树各权值到根的路径长度WPL
二叉树一7×3、5×3、2×1、4×246
二叉树二(哈夫曼树)7×1、5×2、2×3、4×335
二叉树三7×2、5×2、2×2、4×236

哈夫曼树的结构特点是权值大的结点更靠近根结点;表中 WPL 由课件给出的计算式汇总,最小者为哈夫曼树的 35。

第104页:哈夫曼树不唯一

例有4个结点,权值分别为7,5,2,4,构造有4个叶子结点的二叉树abcd7524WPL=7*1+5*2+2*3+4*3=35Huffman树cd24b5a7bcd24a75Huffman树不唯一

第105页:哈夫曼树的构造步骤

构造Huffman树步骤 根据给定的n个权值{w1,w2,……wn},构造n棵只有根结点的二叉树,令起权值为wj 在森林中选取两棵根结点权值最小的树作左右子树,构造一棵新的二叉树,置新二叉树根结点权值为其左右子树根结点权值之和 在森林中删除这两棵树,同时将新得到的二叉树加入森林中 重复上述两步,直到只含一棵树为止,这棵树即哈夫曼树 重复次数:n-1次Huffman树的构造

第106页:哈夫曼树构造示例

例a7b5c2d461811带权路径长度WPL=7*1+5*2+2*3+4*3=35Huffman树的构造

第107页:哈夫曼树构造示例:八权值

例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树的构造

第108页:最佳判定树:百分制转换

百分制转换成五分制的最佳判定树:按各分数段人数比例构造判定树,可减少比较次数;下表列出等级、分数段与对应比例。

百分制转五分制的等级、分数段与比例
等级分数段比例
A90~1000.10
B80~890.30
C70~790.40
D60~690.15
E0~590.05

课件指出 80% 以上的学生需要经过 2 次以上的比较,因此按比例构造哈夫曼判定树可提升判定效率。

第109页:最佳判定算法

等级分数段比例ABCDE0~5960~6970~7980~8990~1000.050.150.400.300.10构造以分数的分布比例为权值的哈夫曼树可得最佳判定算法70 a<80a<60CYNBYNDYNEYNA80 a<9060 a<70EA0.15D0.30B0.60C1.00 最佳判定树Huffman树的应用

第110页:等长编码与不等长编码

等长编码与不等长编码对比:以 ABACCDA 为例,等长编码译码唯一但码长较长,不等长编码码长更短但可能产生前缀歧义。

字符集 {A,B,C,D} 的等长编码与不等长编码
字符等长编码不等长编码
A000
B0100
C101
D1101

原文 ABACCDA 用等长编码得到 00010010101100,用不等长编码得到 000011010;此处的不等长编码中 A 的编码是 B 的前缀,仅作为反例说明,不能保证唯一译码。

第111页:哈夫曼编码示例

字符集 D={C,A,S,T,;} 的哈夫曼编码:按字符出现频率构造哈夫曼树,左分支标 0、右分支标 1,从根到叶子的 0/1 序列即为该字符的编码。

字符集 {C,A,S,T,;} 的出现频率与哈夫曼编码
字符出现频率哈夫曼编码
C2110
A410
S2111
T300
;301

原文编码片段存在粘连,表中编码按哈夫曼树构造规则整理;哈夫曼编码保证任一字符的编码不是其他字符编码的前缀,且电文总长最短。

第112页:哈夫曼译码过程

译码:从Huffman树根开始,从待译码电文中逐位取码。若编码是“0”,则向左走;若编码是“1”,则向右走,一旦到达叶子结点,则译出一个字符;再重新从根出发,直到电文结束例若发送电文是{CAS;CAT;SAT;AT}其编码“”若收到电文为“1101000”译文只能是“” Huffman编码:数据通信用的二进制编码Huffman树的应用CATCS22433T;64A81400001111T :; :A :C :S :00011011011111010111011101000011111000011000

第113页:第五章本章小结

掌握树的基本概念和术语本章小结End掌握二叉树的定义、性质和几种特殊形态的二叉树掌握二叉树的存储结构,遍历的定义及其递归算法的实现(及应用)掌握树的存储结构及其遍历过程掌握森林的遍历过程掌握树、森林与二叉树的相互转换掌握哈夫曼树的实现方法及带权路径长度的计算,掌握哈夫曼编码的构造方法

顶部目录