二叉树的画法和权值运算
由8个权值构造一棵哈夫曼树,该树有几个结点
8个叶子节点需要4个度为二的结点,然后依次需要2个结点为上面4个结点的根结点,以及1个根结点,总共需要15个。其实画出8个叶子节点的完全二叉树即可,总共有15个结点。给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树。
什么是哈夫曼树?
由五个带权值为9,2,3,5,14的叶子结点构成哈夫曼树,带权路径长度为67。给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
猿考研之数据结构篇二(树型结构与图)
遍历树的路径各有千秋,先序(递归与非递归)、中序和后序,还有层次分明的层序,通过出队、访问和子节点入队,线索二叉树则通过前后驱指针增加效率。数据结构的艺术与应用 其中,哈夫曼树是一棵神奇的树,它由N个带权叶子节点构成,通过合并权值最小的子树构建,拥有2N-1个节点,无度为1的节点。哈...
两道题,求详细过程,讲解的。
nk=(k-1)n0+1 如果nk成为父节点有nk个,n0成为子节点有n0个。对于k叉树而言,每当一个子节点拓展为一个父节点时,则子节点变为父节点即ak+=1同时a0-=1,同时子节点又多了k个即an+=k,两式子联立得每拓展一次时 ak+=1 a0+=k-1 又因为树的根节点是没有父亲的,所以n0要再加1 就得到...
二叉树什么意思
如果文字表达的话就是下面的,若看不懂,可以在百度的图片搜索里输入二叉树找张图对照着比划下,应该能看懂。概念并不是很难。说简单点就是一个点分两个叉,这两个叉又分别分两个叉(搜张图就明白这句了)。~~~树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分...
怎样构造哈夫曼树及其带权路径的求法
(3)在F中删除这两颗树,同时将新得到的二叉树加入F中。(4)重复(2)(3),直到F只含一棵树为止。这棵树就是哈弗曼树。如果有N个叶子节点,则哈弗曼树有M=2*N-1个节点。核心代码 for(i=n+1;i<=m;++i){ Choose(i-1,s1,s2);\/\/求出两个有最小权值的节点 HT[s1].parent=i;...
哈夫曼树的带权路径长度是多少?
哈夫曼树带权路径长度是:WPL =(9 + 12 + 15)*2 + 6 * 3 + (3 + 5)* 4 = 122。1)对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,..., Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空。2)在F...
树- 哈夫曼树及其应用 - 最优二叉树(二)
构造最优二叉树 哈夫曼算法 哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法 故称其为哈夫曼算法 其基本思想是 ( )根据给定的n个权值w l w … w n 构成n棵二叉树的森林F={T T … T n } 其中每棵二叉树T i 中都 只有一个权值为w i 的根结点 其左右子树均空 ( )在...
用Huffman算法求带权为1,4,9,25,36,49的最优二叉树
做法:将最小的两个数取出相加1,4,得到5后将5放回再找最小的两个相加5,9,再将14放回,以此类推。最优二叉树如图:
pascal中二叉树是什么?怎么用,求程序
2叉树就是一种树 图片如下:这就是一颗典型的二叉树。二叉树是很多算法的基础。要好好学!!!IOI中国队的未来就在你身上了!!
泗阳县青可回答: 二叉树的画法可以分为: 1、确定根节点 2、确定该节点的左儿子与右儿子 3、递归下去,直到所有节点都不再有儿子节点根据二叉树具体的存储结构,确定根及儿子节点的方法也不一样 从你这图来看,A-G是按层遍历的,既自顶至下,自左至右的顺序遍历如果是用数组来存,可以表示为 索引 0 1 2 3 4 5 6 7 8 节点 A B C D 空 E F 空 G 其中第一个节点即为根节点 索引号为i的节点的:左儿子索引号2i+1右儿子索引号为2i+2 从根节点开始递归下去,就可以画出整个树;饿如果是链表存储,其物理地址与逻辑地址就没有直接联系了,只能靠节点之间的逻辑来推了
左丘狮18271717092问: 试画一颗带权为23345的最优二叉树.并计算二叉树的权. - ?
泗阳县青可回答:[答案] 带权路径WPL=(2+3)*3+5*2+(3+4)*2=39
左丘狮18271717092问: 画一颗权为3.4.5.6.7.8.9的最优2叉树 - ?
泗阳县青可回答: 最优二叉树,也就是赫夫曼树是把带权值最小的两个数,相加得到它的双亲结点.3513 2210 125 73 41 21,2,3,4,5,6,7,8,9,101、先在序列里找权值两个最小的根结点.选1,2组成一棵二叉数.然后,把1,2去掉.用根结点的权值3加入原序列....
左丘狮18271717092问: 二叉树 明天要考试了 求这题答案要过程试构造一棵二叉树,包含权为1,4,9,16,25,36,49,64,81,100等10 个终端结点,且具有最小的加权路径长度WPL. - ?
泗阳县青可回答:[答案] 其实这就是最优二叉树的构建.1、首先从所有结点中选取权值最小的两个结点.2、然后新建一个结点,结点值为该两个结点值之和,并且将该两个结点分别作为新节点的左右子树、然后从原集合结点中删除该两个结点.3、将新节点添加到结点集...
左丘狮18271717092问: 最优二叉树算法的基本概念 - ?
泗阳县青可回答: 最优二叉树,也称哈夫曼(Haffman)树,是指对于一组带有确定权值的叶结点,构造的具有最小带权路径长度的二叉树.那么什么是二叉树的带权路径长度呢?在前面我们介绍过路径和结点的路径长度的概念,而二叉树的路径长度则是...
左丘狮18271717092问: 如何画二叉树 - ?
泗阳县青可回答: 从root node开始如果数值比current node小就往左下走, 大就往右下走, 直到无路可走, 如果还小就在左边加个含有当前数值的node, 大就右边加一个
左丘狮18271717092问: 这个二叉树怎么画啊 - ?
泗阳县青可回答: 对于这种题有我有一个很简单的方法去做. 就是划线法(我自己给的名字). 因为前序中派第一个树的顶点,中序中子树是分别在定点的两边的. 所以A一定是顶点,中序排序可以分为两个子树EBCD,FHIGJ,我们就将这两个子树分别用一条横线画出来,表示第一层,然后在前序中分别找出两个子树,也用横线画出来,用同样的方法对左子树再分子树,用第二条横线画出来,表示第二层.同样就这样分析.看图:http://img.photo.163.com/7O4F7yEw5xUiDB3QC9jAhQ==/163818436447934705.jpg
左丘狮18271717092问: 知道二叉树遍历怎样画出二叉树 - ?
泗阳县青可回答: 先序你要记住是 根-左-右的顺序,而中序是 左-根-右.对于知道先和中序的情况,首先根据先序可以确定第一个是根结点.然后看这个二叉树是否有右子树,如果有,那么对于中序来说,根结点后面肯定还有结点,且中序中根节点后第一个结点...
左丘狮18271717092问: 二叉树的画法 - ?
泗阳县青可回答: 二叉树的结构有顺序存储和链式存储两种存储结构,其中顺序存储是通过数组实现的,从上到下,从左到右的顺序依次存放根、左孩子、右孩子;链式存储是通过指针实现的,一个结点有三个域:左指针、数据域、右指针.
左丘狮18271717092问: 最优二叉树求权值 - ?
泗阳县青可回答: 总权值是吧. 猜测是哈弗曼树吧 各个结点所在深度(即,所在层数-1)乘以 权值.加起来. 不是具体点,只有权值的内结点不需理会.