(最新)034数据结构.ppt

《(最新)034数据结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、网络游戏开发语言基础-C++程序设计专业教程理论讲解部分Ver3.1第034课数据结构概述：遍历二叉树的执行踪迹二叉树的构造与运用最优二叉树的概念和构造编码和解码的概念重点：难点：最优二叉树的构造最优二叉树的构造9数据结构第034课数据结构1）、遍历二叉树的执行踪迹   　三种递归遍历算法的搜索路线相同（如下图虚线所示）具体线路为：   　从根结点出发，逆时针沿着二叉树外缘移动，对每个结点均途径三次，最后回到根结点。9.5.5遍历序列9数据结构DBAECFABDCEF第034课数据结构先序序列   先序遍历二叉树时，对结点的访问次序为先序序列   先序遍历上图所示的二叉树时，得

2、到的先序序列为：2）、遍历序列中序序列   中序遍历二叉树时，对结点的访问次序为中序序列　中序遍历上图所示的二叉树时，得到的中序序列为：9数据结构DBEFCA第034课数据结构后序序列   后序遍历二叉树时，对结点的访问次序为后序序列　后序遍历上图所示的二叉树时，得到的后序序列为：9数据结构第034课数据结构在搜索路线中若访问结点均是第一次经过结点时进行的，则是前序遍历；若访问结点均是在第二次(或第三次)经过结点时进行的，则是中序遍历(或后序遍历)。若将搜索路线上所有在第一次、第二次和第三次经过的结点分别列表，即可分别得到该二叉树的前序序列、中序序列和后序序列。上述都是线性序列，

3、有且仅有一个开始结点和一个终端结点，其余结点都有且仅有一个前趋结点和一个后继结点。为区别于树形结构中前趋(即双亲)结点和后继(即孩子)结点的概念，对上述线性序列，要在某结点的前趋和后继之前冠以其遍历次序名称。9数据结构建立左图所示二叉树，其输入的先序序列是：ABD∮∮CE∮∮F∮∮。第034课数据结构1）基本思想   　基于先序遍历的构造，即以二叉树的先序序列为输入构造。9.5.6二叉树的构造和应用9数据结构voidCreateBinTree(BinTree*T){charch；if((ch=getchar())=='')*T=NULL；//读人空格，将相应指针置空else{//读人

4、非空格*T=(BinTNode*)malloc(sizeof(BinTNode))；//生成结点(*T)->data=ch；CreateBinTree(&(*T)->lchild)；//构造左子树CreateBinTree(&(*T)->rchild)；//构造右子树}}第034课数据结构2）构造算法   　假设虚结点输入时以空格字符表示，相应的构造算法为：9数据结构第034课数据结构3）最优二叉树概念树的路径长度：树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。树的带权路径长度(WeightedPathLengthofTree，简

5、记为WPL)结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。9数据结构其中：n表示叶子结点的数目。wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度。树的带权路径长度亦称为树的代价。第034课数据结构树的带权路径长度(WeightedPathLengthofTree)：定义为树中所有叶结点的带权路径长度之和，通常记为：9数据结构WPL=7*2+5*2+2*2+4*2=36第034课数据结构4）最优二叉树或哈夫曼树在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的

6、二叉树称为最优二叉树或哈夫曼树。例如：给定4个叶子结点a，b，c和d，分别带权7，5，2和4。构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为：9数据结构WPL=7*3+5*3+2*1+4*2=46WPL=7*1+5*2+2*3+4*3=35其中c树的WPL最小，它就是哈夫曼树。第034课数据结构9数据结构第034课数据结构由上图比较可以总结得出：叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。最优二叉树中，权越大的叶子离根越近。最优二叉树的形态不唯一，WPL最小5）构造最优二叉树哈夫曼算法   　哈夫曼首先给出了对于给定的叶子

7、数目及其权值构造最优二叉树的方法，故称其为哈夫曼算法。9数据结构第034课数据结构哈夫曼算法基本思想：根据给定的n个权值wl，w2，…，wn构成n棵二叉树的森林F={T1，T2，…，Tn}，其中每棵二叉树Ti中都只有一个权值为wi的根结点，其左右子树均空。在森林F中选出两棵根结点权值最小的树，将这两棵树合并成一棵新树，为了保证新树仍是二叉树，需要增加一个新结点作为新树的根，并将所选的两棵树的根分别作为新根的左右孩子，将这两个孩子的权