资源描述：
《算法与数据结构讲义四(数据结构——树).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、个人收集整理勿做商业用途第十四课数据结构——树１2.0树型结构12.１树的应用1２.2二叉树及其应用1２.3霍夫曼二叉树12.4线段树12.０ 树型结构ﻩ（一)树的定义树是一种数据结构，它是由n（n>＝1）个有限结点组成一个具有层次逻辑关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点：(1)每个结点有零个或多个子结点； (2)每一个子结点只有一个父结点；(3）没有前驱的结点为根结点； （4)除了根结点外，每个子结点可以分为m个不相交的子树;(二)树
2、的有关术语(1)节点的度：一个节点含有的子树的个数称为该节点的度;(２)叶节点或终端节点:度为零的节点称为叶节点;(3）非终端节点或分支节点:度不为零的节点; (4)双亲节点或父节点：若一个结点含有子节点,则这个节点称为其子节点的父节点;(５)孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点；（6）兄弟节点：具有相同父节点的节点互称为兄弟节点；(7)树的度:一棵树中，最大的节点的度称为树的度;(8)节点的层次：从根开始定义起，根为第0层，根的子结点为第1层，以此类推;(9)树的高度或深度：
3、树中节点的最大层次；(１0）堂兄弟节点:双亲在同一层的节点互为堂兄弟；(11)节点的祖先：从根到该节点所经分支上的所有节点；（12)子孙:以某节点为根的子树中任一节点都称为该节点的子孙。(13)森林:由m（m＞＝0)棵互不相交的树的集合称为森林;（三)树的物理存储 一般使用数组来线性存储树个人收集整理勿做商业用途中各节点的数据本身，但为了记录各节点之间的父子关系,需要附加存储父亲或孩子节点所在的位置。1、双亲表示法:可以存储为：AＢＣDEFGＨＩＪＫ１１1244555７ﻩﻩ1 2 3 4 5６7８
4、9 1０ 11优点:（1）节省空间。（2）便于从下向上访问（记录了从孩子到父亲的逻辑关系）。（3）便于随时插入新的子树。缺点：不利于从上向下的访问。（未记录父亲到孩子的逻辑关系)。例如:利用所给边集创建双亲表达树ﻩ输入:第一行两个整数n，m，表示节点个数和边的条数ﻩﻩ 下面ｍ行,每行2个整数，表示两个节点存在父子关系输出:如上的双亲表示法的树ｐrogｒammaｋeｔreｅ;ﻩﻩﻩ//时间复杂度O(ｎlｏgn）const mａxn=１2;vａriｎｆ，ｏuｔf:text； biａn:array[1.．ｍ
5、axn,1.．2]ｏf iｎteger;/／存储边集 tｒeｅ,nuｍ:aｒray[1．.maxn]oｆinteger;//存储树、各节点的度 ｔ:ａｒｒａy[1.．maxn]ｏfbｏoｌean;ﻩﻩ//哈希 ｎ,ｍ,i，ｊ,k:ｉntｅger;//////／／///／／///////////／///////////／／/／/////／／prｏｃedureinit;beｇｉｎ aｓｓign(inf,'mａkｅtree.in');aｓｓign(outｆ,'makｅtree.out＇）;reset（ｉnｆ)
6、;readln(ｉnｆ,n,m）； foｒ i：=1to mdo个人收集整理勿做商业用途 begiｎ readln(inf，ｂian[i，1],bian[i,2])； inc(num［ｂiａn[i,1］])；iｎc(num[bｉaｎ[i,2]])；//统计各节点的度 eｎd;ｅｎd;／/／///////／/／／////／//／／//／／/／//／／///////／//／///prｏcedｕｒｅmake;begin i:=1; k：=0； ｆillｃhaｒ(t,ｓizeｏｆ(t），trｕｅ);
7、 whilｅk<ｍdo ｂegiｎ ｗhｉｌe nｕm[ｉ]<>1 doi：=imｏd n+1;//查找度为1的节点 j:=1; whiｌenot（t［ｊ]aｎd((bian[j,1]=ｉ）or(bian[ｊ,２］=i))) ｄｏiｎc（j);//找到包含该 ifｊ>nthｅnbrｅaｋ;ﻩﻩﻩﻩﻩﻩ//节点的边 t[j]：＝ｆａｌse； ifｂｉａn[ｊ,１]=itｈen tree［i］：=bian[j，２］; iｆ ｂiａn[j，２]＝ｉtheｎtre
8、e[i］:=ｂｉaｎ[j，1]; dｅｃ(nｕm[biａn［ｊ,1]])；dｅc(nｕｍ[biａn[j，2］］); inc（ｋ); end;eｎd;／//／//／/////／////／／/////／/////／////////／／////／/proｃeｄureｐrｉｎt;begiｎrewrｉtｅ(oｕtf); fｏｒｉ:=1ｔｏndowrite(outf,i:3）;writeln(outf); fori:=１tondoｗr
