资源描述：
《信息学奥赛必读--二叉树及其应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、二叉树及其应用雅礼朱全民二叉树二叉树是一种特殊的树型结构，它的特点是每个节点至多只有两个子节点。二叉树每个节点的子树有左右之分，其次序不能任意颠倒。二叉树也有特殊形式，例如满二叉树、完全二叉树等。例如右图就是一棵二叉树，并且是一棵完全二叉树。二叉树的存储结构常用的存储结构typebitree=^nodenode=recorddata:datatype;lchild,rchild:bitree;end;二叉树的遍历遍历(先序遍历,中序遍历,后序遍历)Procpreorder(bt:bitree);ifbt<>Nilthen[visit(bt^)preorder(b
2、t^.lchild);preorder(bt^.rchild);]endP二叉树的性质在二叉树的第i层上最多有2i-1个结点深度为K的二叉树最多有2k-1个结点在二叉树中,叶子结点的总数总比为度数为2的结点多1有n个结点的完全二叉树的结点按层序编号,则对任意一结点i,有(1)如果i=1,则结点i是二查树的根，无双亲；如果i>1，则双亲是[i/2](2)如果2i>n，则结点i无左孩子，否则左孩子为2i(3)如果2i+1>n，则结点i无右孩子，否则右孩子为2i+1树、森林转化为二叉树用“孩子兄弟表示法”可以将任意一棵树转化为二叉树的形式森林转化为二叉树如果F={T1
3、,T2,…,Tm}是森林，则可按如下规则转化为一棵二叉树。1)若F为空，即m=0,则B为空树2)若F非空，即m<>0,则B的根root即为森林中第一棵树的根root(T1),B的左子树为从T1中子树森林F1={T11,T12,…,T1i}转换而成的二叉树；其右子树Rb是从森林F={T2,…,Tm}中转换出来的二叉树树的儿子兄弟表示法在一棵树中，拥有同一个父结点的结点互称为兄弟。我们不妨假设树中每个结点的子结点是有序的（就像二叉树一样），则我们可以将一棵树这样转化成二叉树：二叉树中每个结点对应原树的每个结点对于二叉树中的某个结点它的左子结点对应原树中该结点的第一个
4、子结点；它的右子结点对应原树中该结点的下一个兄弟。原树转化后的树树的儿子兄弟表示法这样我们可以类似于二叉树的链式结构写出树的儿子兄弟表示法的存储结构：TYPEtree=^node;node=recorddata:datatype;parent,child,brother:tree;//分别记录父亲、第一个儿子、下一个兄弟end;树的儿子兄弟表示法给定m个实数w1,w2,…,wm,(m>=2),要求一个具有m个外部节点的扩充二叉树，每个外部ki节点有一个wi与之对应，作为它的权,使得带权外部路径长度最小，其中li是从根到外部节点的路径长度。最优二叉树(哈夫曼树)算
5、法1.构造m个只有1个节点的树2.找两个最小的权3.以这两个节点为左右儿子构造一个二叉树，并将该数的根节点权之为左右儿子权值之和4.继续第二步，直到剩下一棵树为止讨论最优k叉树就是指在一个节点最多可以有k个叶子节点的时候，假设有n（n>=k）个权值{w1,w2,….wn},试构造出一棵有ｎ个叶子节点的k叉树。每个叶子节点有一个不同的权值ｗi。其中树的带权路径长度最小的那棵树叫做最优k叉树。怎么构造??分析最优k叉树必须具备的性质：每个节点如果不是叶子节点，那么一定有k个儿子节点。权值大的节点不能在比权值小的节点下方。就是权值大的节点到树根的长度要小于等于权值小的
6、节点到树根的长度。算法根据给定的n个权值wl，w2，…，wn构成n棵k叉树的森林F={T1，T2，…，Tn}，其中每棵k叉树Ti中都只有一个权值为wi的根结点，其左右子树均空。在森林F中选出k棵根结点权值最小的树(当这样的树不止k棵树时，可以从中任选k棵)，将这k棵树合并成一棵新树，为了保证新树仍是k叉树，需要增加一个新结点作为新树的根，并将所选的k棵树的根分别作为新根的左右孩子，将这k个孩子的权值之和作为新树根的权值。对新的森林F重复(2)，直到森林F中只剩下一棵树为止。这棵树便是最优k叉树。反例假设k=3,当n=5时，这样做是对的。但是当n=4时，用刚才的方
7、法得到的“最优3叉树”，但是，明显右图的那颗树会比左图的那颗树优。分析原因错误的原因：主要是左边的这棵树它并没有排满。可以把第3层的一个节点拉到第2层去，而这样做肯定会让WPL更小。那么肯定要让第一次合并的时候，少合并几个点，后面的操作就和上面所说得算法一样。并且让最后一次合并能合并n棵树。从而让上面排满。那么第一次要合并多少个点呢？首先每次合并会让树的总数减少k-1棵，而最后还有n棵。那么完成了第一次合并后，剩下的树的个数正好模k-1后等于1。那么第一次合并的树的个数就应该是(n-2)mod(k-1)+2。而当k=2时，k-1=1，此时第一次合并的个数总是为2
8、。改进算法根据给定的n个
