5.1树的概念树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树1.树的度——也即是宽度，简单地说，就是结点的分支数。

以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。

树中度不为零的结点称为分枝结点或非终端结点。

除根结点外的分枝结点统称为内部结点。

2.树的深度——组成该树各结点的最大层次，如上图，其深度为4；3.森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林；4.有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。

5.树的表示树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。

如上图可写成如下形式： (A(B(E(K,L),F),C(G),D(H(M),I,J)))5. 2 二叉树1.二叉树的基本形态：二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：(1)空二叉树——(a)；(2)只有一个根结点的二叉树——(b)；(3)右子树为空的二叉树——(c)；(4)左子树为空的二叉树——(d)；(5)完全二叉树——(e)注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。

2.两个重要的概念：(1)完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；(2)满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树,。

如下图：完全二叉树1页满二叉树3.二叉树的性质(1) 在二叉树中，第i层的结点总数不超过2^(i-1)；(2) 深度为h的二叉树最多有2h-1个结点(h>=1)，最少有h个结点；(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；(4) 具有n个结点的完全二叉树的深度为int（log2n）+1(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：若I为结点编号则如果I<>1，则其父结点的编号为I/2；如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。

4.二叉树的存储结构：(1）顺序存储方式type node=recorddata:datatypel,r:integer;end;vartr:array[1..n] of node;(2)链表存储方式，如：type btree=^node；node=recorddata:datatye;lchild,rchild:btree;end;2页5.普通树转换成二叉树：凡是兄弟就用线连起来，然后去掉父亲到儿子的连线，只留下父母到其第一个子女的连线。

6.二叉树的遍历运算（递归定义）(1)先序遍历（根左右）访问根；按先序遍历左子树；按先序遍历右子树(2)中序遍历（左根右）按中序遍历左子树；访问根；按中序遍历右子树(3)后序遍历（左右根）按后序遍历左子树；按后序遍历右子树；访问根例1.用顺序存储方式建立一棵有31个结点的满二叉树，并对其进行先序遍历。

program erchashu1;var b:array[1..31] of char;e:array[1..63] of byte;n,h,i,k:integer;procedure tree(t:integer);beginif e[t]=0 then exitelsebeginwrite(b[t]);e[t]:=0;t:=2*t;tree(t);t:=t+1;tree(t);end;end;beginrepeatwrite('n=');readln(n);until (n>0) and (n<6);fillchar(e,sizeof(e),0);k:=trunc(exp(n*ln(2)))-1;for i:=1 to k do e[i]:=1;for i:=1 to 26 do b[i]:=chr(64+i);for i:=1 to 5 do b[26+i]:=chr(48+i);h:=1 ;tree(h);writeln;end.例2.用顺序存储方式建立一棵如图所示的二叉树，并对其进行先序遍历。

3页program tree1;const n=15;type node=recorddata:char;l,r:0..n;end;vartr:array[1..n] of node;e:array[1..n] of 0..1;i,j:integer;procedure jtr;var i:integer;beginfor i:=1 to n dowith tr[i] doreadln(data,l,r);end;procedure search(m:integer);beginwith tr[m] dobeginwrite(data);if l<>0 then search(l);if r<>0 then search(r);end;end;beginjtr;search(1);writeln;end.例3 用链表存储方式生成上述二叉树，中序遍历之。

1.将上述二叉树用广义表表示为A(B(D,E(G)),C(F(,H)))2.根据广义表串（以#结束）生成二叉树。

program ltree;const n=8;type trlist=^node;4页node=recordda:char;l,r:trlist;end;var s:array[1..n] of trlist;p,root:trlist;ch:char;top,k:integer;procedure creat(varhead:trlist);beginread(ch);top:=0;while ch<>'#' dobegincase ch of'A'..'Z':begin new(p);p^.da:=ch;p^.l:=nil;p^.r:=nil; if top<>0 thencase k of1:s[top]^.l:=p;2:s[top]^.r:=p;endend;'(':begin top:=top+1;s[top]:=p;k:=1;end;')': top:=top-1;',': k:=2;end;read(ch);end;head:=s[1];end;procedure inorder(head:trlist);beginif head^.l<>nil then inorder(head^.l);write(head^.da);if head^.r<>nil then inorder(head^.r);end;beginwrite('Input tree string:');creat(root);inorder(root);end.5页5.3 二叉树的应用1. 哈夫曼树与哈夫曼码树的路径长度：一棵树的每一个叶结点到根结点的路径长度的和。

带权二叉树：给树的叶结点赋上某个实数值（称叶结点的权）。

带权路径长度：各叶结点的路径长度与其权值的积的总和。

哈夫曼树（最优二叉树）：带权路径长度最小的二叉树。

如何构建哈夫树：（思想是：权越大离跟越近）program gojiantree;const n=4;m=7;type node=recordw:real;parent,lchild,rchild:0..mend;htree=array[1..m] of node;var htree1:htree;procedure gjtree(varht:htree);vari,j:integer;small1,small2:real;p1,p2:0..m;beginfor i:=1 to m dowith ht[i] dobeginw:=0;lchild:=0;rchild:=0;parent:=0;end;for i:=1 to n do read(ht[i].w);for i:=n+1 to m dobeginp1:=0;p2:=0;small1:=1000;small2:=1000;for j:=1 to i-1 doif ht[j].parent=0 thenif ht[j].w<small1 thenbegin small2:=small1;small1:=ht[j].w;p2:=p1;p1:=j endelse if ht[j].w<small2 then begin small2:=ht[j].w;p2:=j end;6页ht[p1].parent:=i;ht[p2].parent:=i;ht[i].lchild:=p1;ht[i].rchild:=p2;ht[i].w:=ht[p1].w+ht[p2].w;end;end;begingjtree(htree1);end.哈夫曼码：哈夫曼树的非叶结点到左右孩子的路径分别用0，1 表示，从根到叶的路径序列即为哈夫曼码。

哈夫曼码是不会发生译码多义性的不等长编码，广泛应用实际中。

（原因是任何一字符的编码不是更长编码的前缀部分，为什么？）2.排序二叉树排序二叉树：每一个参加排列的数据对应二叉树的一个结点，且任一结点如果有左（右）子树，则左（右）子树各结点的数据必须小（大）于该结点的数据。

中序遍历排序二叉树即得排序结果。

程序如下：program pxtree;consta:array[1..8] of integer=(10,18,3,8,12,2,7,3);type point=^nod;nod=recordw:integer;right,left:point ;end;varroot,first:point;k:boolean;i:integer;procedure hyt(d:integer;var p:point);beginif p=nil thenbeginnew(p);with p^ do begin w:=d;right:=nil;left:=nil end;if k then begin root:=p; k:=false end;endelse with p^ do if d>=w then hyt(d,right) else hyt(d,left);7页end;procedure hyt1(p:point);beginwith p^ dobeginif left<>nil then hyt1(left);write(w:4);if right<>nil then hyt1(right);endend;beginfirst:=nil;k:=true;for i:=1 to 8 do hyt(a[i],first);hyt1(root);writeln;end.3.堆排序堆：设有数据元素的集合（R1,R2,R3,...Rn)它们是一棵顺序二叉树的结点且有Ri<=R2i 和Ri<=R2i+1(或>=)堆的性质：堆的根结点上的元素是堆中的最小元素，且堆的每一条路径上的元素都是有序的。