文档介绍：第十四课数据结构——树 树型结构 树的应用 二叉树及其应用 霍夫曼二叉树 线段树 树型结构(一)树的定义树是一种数据结构,它是由 n( n>=1 )个有限结点组成一个具有层次逻辑关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树, 也就是说它是根朝上, 而叶朝下的。它具有以下的特点: (1) 每个结点有零个或多个子结点; (2) 每一个子结点只有一个父结点; (3) 没有前驱的结点为根结点; (4) 除了根结点外,每个子结点可以分为 m个不相交的子树; (二)树的有关术语(1) 节点的度:一个节点含有的子树的个数称为该节点的度; (2) 叶节点或终端节点:度为零的节点称为叶节点; (3) 非终端节点或分支节点:度不为零的节点; (4) 双亲节点或父节点:若一个结点含有子节点,则这个节点称为其子节点的父节点; (5) 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; (6) 兄弟节点:具有相同父节点的节点互称为兄弟节点; (7) 树的度:一棵树中, 最大的节点的度称为树的度; (8) 节点的层次:从根开始定义起,根为第 0 层,根的子结点为第 1 层,以此类推; (9) 树的高度或深度:树中节点的最大层次; (10) 堂兄弟节点:双亲在同一层的节点互为堂兄弟; (11) 节点的祖先:从根到该节点所经分支上的所有节点; (12) 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。(13) 森林:由 m( m>=0 )棵互不相交的树的集合称为森林; (三)树的物理存储一般使用数组来线性存储树中各节点的数据本身,但为了记录各节点之间的父子关系,需要附加存储父亲或孩子节点所在的位置。 1、双亲表示法: 可以存储为: 123456789 10 11 优点: (1) 节省空间。(2) 便于从下向上访问(记录了从孩子到父亲的逻辑关系)。(3) 便于随时插入新的子树。缺点:不利于从上向下的访问。(未记录父亲到孩子的逻辑关系)。例如:利用所给边集创建双亲表达树输入:第一行两个整数 n,m ,表示节点个数和边的条数下面 m 行,每行 2 个整数,表示两个节点存在父子关系输出:如上的双亲表示法的树 program maketree; // 时间复杂度 O(nlogn) const maxn=12; var inf,outf:text; bian:array[1..maxn,1..2]of integer; // 存储边集 tree,num:array[1..maxn]of integer; // 存储树、各节点的度 t:array[1..maxn]of boolean; // 哈希 n,m,i,j,k:integer; /////////////////////////////////////////////// procedure init; begin assign(inf,''); assign(outf,'');reset(inf); read ln (inf,n,m); for i:=1 tom do begin read ln (inf,bian[i,1],bian[i,2]); ABCDEFGHIJK 1112445557 inc(num[bian[i,1]]); inc(num[bian[i,2]]); // 统计各节点的度 end; end; /////////////////////////////////////////////// procedure make; begin i:=1; k:=0; fillchar(t,sizeof(t),true); while k<m do begin while num[i]<>1 do i:=i mod n+1; // 查找度为 1 的节点 j:=1; while not(t[j]and((bian[j,1]=i)or(bian[j,2]=i))) do inc(j); // 找到包含该 if j>n then break; // 节点的边 t[j]:=false; if bian[j,1]=i then tree[i]:=bian[j,2]; if bian[j,2]=i then tree[i]:=bian[j,1]; dec(num[bian[j,1]]); dec(num[bian[j,2]]); inc(k); end; end; /////////////////////////////////////////////// procedure print; begin rewrite(outf); for i:=1 ton do write(ou