《程序设计竞赛网站集锦》由会员分享，可在线阅读，更多相关《程序设计竞赛网站集锦（17页珍藏版）》请在金锄头文库上搜索。
1、树树形结构（包括树和二叉树）是一种非常重要的结构。由于树形结构中的各子结构与整个结构具有相似的特性，因而其算法大多采用递归形式，这对许多初学者来说是一个难点。1主要内容1、树的定义及基本术语2、二叉树的定义及性质3、满二叉树和完全二叉树及性质5、遍历二叉树4、二叉树的存储结构6、赫夫曼（huffman）树21、树的定义与运算n定义：树T是n个结点构成的有限集合(n0)，其中有一个结点叫根，其余结点可划分为m个互不相交的子集T1,T2Tm (m0)，并且这m个子集本身又构成树，称为T的子树。n注意：本书没有给出空树的概念，即节点数至 少为1。3树结构的表现形式及相关概念n图形表示法：见下图ACD
2、EFBGHn 结点:包含一个数据元素及若干指向其子 树的分支n结点的度:结点拥有的子树n 根结点：例如An叶子结点（终端结点）：度为0的结点n分支结点（非终端结点、内部结点）：度 不为0的结点n孩子节点、父节点、兄弟节点、祖先节点 、后代节点n层次：从根开始定义，根为第一层。n 树的深度（高度）：树中结点的最大层 次n 有序树、无序树：树中结点的各子树看 成从左至右是有次序的（不能互换）为有序 的.最左边的子树的根称为第一个孩子，最 右边的称为最后一个孩子。n 森林:互不相交的树的集合42 、 二叉树n7.2.1 定义：二叉树T是n个结点的有限集合，其中n0,当n=0时，为空树，否则， 其中有
3、一个结点为根结点，其余结点划分为两个互不相交的子集TL、TR，并且 TL、TR分别构成叫作左、右子树的二叉树。n二叉树另一种树型结构，它的特点是每个结点至多只有二棵子树（即二叉树中不 存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。ACDEFBGHIKJMLA的TLB的TL52.1 二叉树性质性质1：在二叉树的第i层上的结点数2i-1（i0）（在二叉树的第i层上至多有2i-1 个结点）性质2：深度为k的二叉树的结点数2k-1（k0）(深度为K的二叉树至多有2k-1个结点)性质3：对任一棵非空的二叉树T，如果其叶子数为n0，度为2 的结点数为n2，则有下面的关系式成立：n
4、0=n2+1 63、满二叉树、完全二叉树n满二叉树的定义：一棵深度为K且有2k-1个结 点的二叉树称为满二叉数特点：是每一层上的结点数都是最大结点数n完全二叉树定义：深度为K的，有N个结点的 二叉树，当且仅当其每一个结点都与深度为K 的满二叉树中编号从1到N的结点一一对应时， 称之为完全二叉树73.1完全二叉树的特点n具有n个结点的完全二叉树的深度为log2n+1n在编号的完全二叉树中，各结点的编号之间的 关系为：编号为i的结点如果存在左孩子，则其 编号为2i，如果存在右孩子，则其编号为2i+1 ，如果存在父结点，则其编号为i/284、 二叉树存储 4.1顺序存储二叉数n按完全二叉树的编号次序
5、进行，即编号为i的结点存储在数组中下标为i的元素中；1345678910 ABCDEFGHIJKLM1211132n若二叉树不是完全二叉树形式，则为了保持结点之间的关系，不得不空 出许多元素来，因为，在最坏的情况下，一个深度为K且只有K个结点的单支树（树中不存在度为2的结点）却需要长度为2k-1的一维数组。这就造成了空间的浪费。为此，依据实际结点数来分配存储空间，这就涉及到了动态链表结构。94.2 二叉链表n二叉链表结构描述： typedef char datatype； typedef struct datatype data;struct Bnode *lchild, *rchild; B
6、node;lchild data rchild存储结点值的 数据域data指向右孩子 结点的指针指向左孩子 结点的指针T105、二叉树的遍历n遍历二叉树是指按某种次序访问二叉树中每个节点一 次且仅一次。TRLT先序TLR 中序LTR 后序LRT先左后右11例题：看下图-+/a*efb-cd先序遍历：-+a*b-cd/ef前缀表达式（波兰式） 中序遍历：a+b*c-d-e/f中缀表达式后序遍历：abcd-*+ef/-后缀表达式（逆波兰式）12遍历算法例题（2）n已知二叉树的先序和中序序列如下，试构造出相应的二叉树。先序：ABCDEFGHIJ中序：CDBFEAIHGJ 原理：先序序列的第一个节点是
7、根节点中序序列根结点处于左右子树的中序序列之间 注意：二叉树的先序和后序序列不能唯一确定一棵二叉树，但由先序和中序或后序和中序序列能唯一确定一棵二叉树。先序：ABCDEFGHIJ 中序：CDBFEAIHGJBCDEF CDBFEGHIJ IHGJACD CDEF FEHI IHJ JACBAJECBFDGHI136、 哈夫曼树（最优二叉树） 设计一个将百分成绩转换为等级制的算法，具 体要求如下： A：90100 B：8089 C：7079 D：6069 E：059S=6 0 S=9 0S=8 0S=70ABC DES=9 0S=8 0S=7 0S=6 0ABCDE如何判断才能最省时间？ 14哈
8、夫曼树n给定一组数值w1，w2，wn作为叶子结点的权值， 构造一棵二叉树。如果wiLi最小，则称此二叉树为最优 二叉树，也称哈夫曼树。并称wiLi为带权路径长度。n哈夫曼算法： v根据给定的n个权值w1,w2,，wn，构成n棵二叉树的 集合T=T1,T2,Tn，其中每个Ti只有一个带权为wi的 根结点，其左右子树均空。 v从T中选两棵根结点的权值最小的二叉树，不妨设为T1 、T2作为左右子树构成一棵新的二叉树T1，并且置新 二叉树的根值为其左右子树的根结点的权值之和。 v将新二叉树T1并入到T中，同时从T中删除T1、T2。v重复(2)、(3)，直到T中只有一棵树为止。15例题n以集合3,4,5
9、,6,8,10,12,18为叶子结点的权值构 造哈夫曼树，并计算其带权路径长度。T= 3456810 12 18第一步第二步T= 3456810 12 187第三步T= 56810 12 1811347第四步T= 56810 12 181134715第五步T= 5681012 18113471521第六步T= 56810121811347152127第七步T= 5681012181134715212739第八步568101218113471521273966WPL（3456）4（810）3 （1218）2186将所有分支结点的值加起来，即6639272115117186v可以证明，任意一棵哈夫曼树的带权路径长度均具有这一性质，即等于所有分支结点权值之和。16重讲堆排序17
