例：若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。

 输入格式 

第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。

以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Ai和Bi具有亲戚关系。

接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。

 输出格式 

P行，每行一个‘Yes‘或‘No‘。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

program family;

var c:array[0..5000]of longint;

    i,j,m,n,p,x,y,a,b:longint;

function find(x:longint):longint;

  begin

    find:=c[x];

  end;

procedure union(a,b:longint);

  begin

    for i:=1 to n do

    if c[i]=b then c[i]:=a;

  end;

begin

  read(n,m,p);

  for i:= 1 to n do c[i]:=i;

  for j:= 1 to m do

    begin

      read(x,y);

           a:=find(x);

      b:=find(y);

      if a<>b then union(a,b);

    end;

  for i:= 1 to p do

    begin

      read(x,y);

      if c[x]=c[y] then writeln(‘Yes‘)

                         else writeln(‘No‘);

    end;

end.

programex2_b1;（链表解法）

type

 pointer=^rec;

 rec=record

        data，count:longint;

        next:pointer;

      end;

var

 k,n,i:longint;

 s,h:pointer;

procedure search(x:longint);

var q,p1,p2:pointer;

begin

 new(q); q^.data:=x; inc(q^.count);

 if x<h^.data then begin q^.next:=h;h:=q;end

   else begin

         p2:=h;

         while(x>p2^.data)and(p2^.next<>nil) do begin p1:=p2;p2:=p2^.next; end;

         if p2^.data=http://www.mamicode.com/x then>

           else if x<p2^.data thenbegin  p1^.next:=q; q^.next:=p2; end

                    else begin p2^.next:=q;q^.next:=nil end

         end;

end;

procedure printlist(p:pointer);

begin

  whilep<>nil do begin writeln(p^.data,‘ ‘,p^.count);p:=p^.next; end;

end;

begin

 assign(input,‘count3.in‘); reset(input);

 assign(output,‘count.out‘); rewrite(output);

 readln(n);

 new(h);readln(h^.data);h^.count:=1;h^.next:=nil;

 for i:=1 to n-1 do begin readln(k);search(k); end;

 printlist(h);

 close(input);close(output);

end.

program lx212;（数组解法）

      var a:array[1..200001] of longint;
                   i,j,k,m,n:longint;
          procedure qsort(s,t:longint);
          var i,j,mid,temp:longint;
            begin
              i:=s;j:=t;mid:=a[(s+t) div 2];
              while i<=j do
                  begin
                     while a[i]<mid do inc(i);
                     while a[j]>mid do dec(j);
                     if i<=j then
                         begin
                             temp:=a[i];a[i]:=a[j];a[j]:=temp;
                              inc(i);dec(j);
                         end;
                 end;
            if i<t then qsort(i,t);
            if j>s then qsort(s,j);
          end;
          begin

         assign(input,‘count.in‘);
             reset(input);
             assign(output,‘count.out‘);
             rewrite(output);
             readln(n);
             for i:=1 to n do readln(a[i]);
             qsort(1,n);
             a[n+1]:=maxlongint;
             k:=1;
             for i:=2 to n+1 do
             if a[i]<>a[i-1] then begin writeln(a[i-1],‘ ‘,k); k:=1;end
                                  else k:=k+1; 

            close(input);
            close(output);
          end.

第四章 树

树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。

4.1基本概念
　树结构的特点是：它的每一个结点都可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前趋。

1. 定义：一棵树是由n（n>0）个元素组成的有限集合，其中：

（1）每个元素称为结点(node)；

（2）有一个特定的结点，称为根结点或树根（root）；

（3）除根结点外，其余结点能分成m（m>=0）个互不相交的有限集合T0,T1,T2,……Tm-1

其中的每个子集又都是一棵树，这些集合称为这棵树的子树。

如下图是一棵典型的树：

2. 树的表示

  ①广义表表示法：(A(B(E(K,L),F),C(G),D(H(M),I,J)))

②树形表示法：
　　　　　　　

3. 有关术语   

①结点名称——根、支结点、叶子。

②结点的关系——前缀（双亲）、后继（孩子）、兄弟（同一层双亲的孩子）。

③结点的层次——根为第一层，它的孩子为第二层……。

④树的深度——组成该树各结点的最大层次，如上图，其深度为4。

⑤树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。

⑥子树——树的一部分称为原树的子树。

⑦森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的三棵子树T1、T2、T3的集合{T1,T2,T3}就为森林。

⑧有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。

4.2 二叉树

1. 定义：二叉树是结点的有限集合，这个集合或是空的，或是由一个根结点和两棵互不相交的称之为左子树和右子树的二叉树组成。

2. 二叉树的五种基本形态。

（a）    空二叉树；(b)只有一个结点的二叉树；(c)只有左子树的二叉树；(d)只有右子树的二叉树；(e)左右完全的二叉树。

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

完全二叉树                                       满二叉树

 4. 二叉树的主要性质

(1) 二叉树的的i层上最多只有个结点()。

证明：当i=1 时，=  2⁰  =1 显然成立；

假设第 i=k层时命题成立，即第k层上最多有2^k-1 个结点。

当i=k+1时，由于第k层的2^k-1个结点每个最多有2个子结点，故最多有 2*2^k-1 =2^(k+1)-1个结点 。

(2) 深度为 k的二叉树至多有 2^k–1 个结点（k>=1），最少有k个结点。

即：1+2+4+8+……+2^k-1  =  

（3）对于任意一棵二叉树，如果其叶结点数为n0，而度数为2的结点总数为n2，则n0=n2+1；

证明：假设ni(i=0、1、2)，为度是i的结点数，即：n= n0+ n1+ n2

设 B为二叉树的前驱个数，则B=n-1 ②（二叉树只有根没有前驱），所有这些前驱同时又是度为1和2的结点的后继，故B= n1+2*n2,③

由③代②得：n= n1+2*n2+1。

由④代①得：n1+2*n2+1 = n0+ n1+ n2  即：n0=n2+1

 5. 树或森林转换为二叉树

  ① 普通树 → 二叉树  方法： 左链联孩子，右链联兄弟

  例：

② 森林 → 二叉树  方法： 将森林每颗树的根视为兄弟，以第一棵树的根为二叉树的根，左链联孩子，右链联兄弟的方法转换即可。

     例：

  由于树和森林可方便唯一的转换成二叉树，故以后主要讨论二叉树。

4.3  树的存储结构（顺序存储结构和链表存储结构）

4.3.1二叉树的存储结构

 1． 顺序存储结构（满二叉树，完全二叉树一般采用存顺序储结构）

Const  m= 树中结点树的上限；

Type  node= record

      Data :datatype;

      Prt ,lch, rch : 0..m;

      End;

Treetype= array[1..m] of node;

Vartree : treetype;

例：采用数组tree存储满二叉树

2． 链式存储结构（一般二叉树通常采用链式存储结构）

语言描述：                                    结点结构：

type tree=^node;                               

    node=record

      data:char;

      lchild,rchild:tree

    end;

var bt:tree;

例：采用链表存储二叉树

4.3.2树的存储结构

（1）顺序存储方式

           Const

             n=树的度；

             m=结点数的上限；            

type node=record

                     data:datatype

                     child:array[1..n] of integer;

                    end;        

            var  tree:array[1..m] of  node;

 (2) 链表存储方式

Const

             n=树的度；
　　　　　 type  btree=^node；

                  node=record

                      data:datatye;

                      next:array[1..n] of btree;

                  end;

         var  root: btree

n度数的结点结构为 

4.4树的遍历

一、二叉树的遍历

⑴ 遍历：就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

⑵ 遍历的方式：设 L：遍历左子树

R：遍历右子树

D：访问根结点

则所有可能的遍历方式为LDR，LRD，RDL，RLD,DLR, DRL

若考虑先左后右则方式为：DLR（前序遍历），LDR（中序遍历），LRD（后序遍历）。

1、前序遍历的操作定义如下：                         

若二叉树为空，则空操作，否则

① 访问根结点

② 先序遍历左子树

③ 先序遍历右子树

先序遍历右图结果为：124753689

2、中序遍历的操作定义如下：

若二叉树为空，则空操作，否则

① 中序遍历左子树

② 访问根结点

③ 中序遍历右子树

中序遍历右图结果为：742513869

3、后序遍历的操作定义如下：

若二叉树为空，则空操作，否则

① 后序遍历左子树

② 后序遍历右子树

③ 访问根结点

后序遍历右图结果为：745289631

习题1：上面的图表示的二叉树的前序遍历序列：______________________ 中序遍历序列：____________________ 后续遍历序列:______________________ 。

从根出发，逆时针外像绕行全树，按第一次经过的时间次序列出各结点即为前序列表、按叶结点第一次经过时列出，内部结点第二次经过时列出即为中序列表、按最后一次经过的次序列表即为后序列表。

习题2：在磁盘的目录结构中,我们将与某个子目录有关联的目录数称为度。例如下图：

该图表达了A盘的目录结构:Dl,Dll_…D2均表示子目录的名字.在这里,根目录的度为2。Dl子目录的度为2，D1l子目录的度为3, D12,D2,Dlll,D112,D113的度均为0。若不考虑子目录的名字.则可简单的图示为如下的树结构:若知道一个磁盘的目录结构中.度为2的子目录有2度为3的子目录有l个,度为4的子目录有3个。

试问：度为1的子目录共有几个。

习题3：设M叉树采用列表法表示,即每棵子树对应一个列表,列表的结构为:子树根结点的值部分(设为一个字符)和用“（）”括起来的各子树的列表(如有子树的话),各子列表问用“，”分隔。例如下面的三叉树可用列表a(b(c,d),e,f(g,h,i))表示。

写出右图的三叉树用列表形式表示的结果：________________________________________。

⑶遍历算法：

① 链表算法：

procedurepreorder(bt:tree);{先序遍历根结点为 bt 的二叉树的递归算法}

begin

  if bt<>nil then begin

write(bt^.data);

preorder(bt^.lchild);

preorder(bt^.rchild);

               end;

end;

② 数组算法：

procedurepreorder(i:integer);

begin

  if i<>0 then begin

write(tree[i].data);

preorder(tree[i].lchild);

preorder(tree[i].rchild);

               end;

end;

大家很容易就可以改写出中序和后序遍历的递归过程。当然，我们还可以把递归过程改成用栈实现的非递归过程，以先序遍历为例，其它的留给作者完成。

Procedureinorder(bt:tree);      {先序遍历bt所指的二叉树}

Var  stack:array[1..n] of tree;

Top:integer;  P:tree;

begin

top:=0;

While not ((bt=nil)and(top=0)) do

Begin

          While bt<>nil do begin 

Write(bt^.data);

Top:=top+1;

Stack[top]:=bt^.rchild

                           bt:=bt^.lchild;

                         end;

          If top<>0 then begin

          b:=stack[top];

top:=top-1;

       End;

End;

End;

二、二叉树的其它重要操作：

（1）、建立一棵二叉树

Procedure pre_crt(var bt:tree);{按先序次序输入二叉树中结点的值，生成

begin                       二叉树的单链表存储结构，bt为指向根结点的指针,’’表示空树}

 Read(ch);

  Ifch=’.’ then bt:=nil

  Elsebegin

        New(bt);                  {建根结点}

        Bt^.data:=ch;

        Pre_crt(bt^.lchild);     {建左子树}

        Pre_crt(bt^.rchild);     {建右子树}

      End;

End;

（2）、删除二叉树

Procedure dis(var bt:tree);  {删除二叉树}

Begin

  Ifbt<>nil then begin

Dis(bt^.lchild);         {删左子树}

Dis(bt^.rchild);         {删右子树}

Dispose(bt);             {释放父结点}

              End;

End;

（3）、插入一个结点到二叉树中

Procedure insert(var bt:tree;n:integer);  {插入一个结点到二叉树中}

Begin

  Ifbt=nil then begin

new(bt); 

bt^.data:=n; 

bt^.lchild:=nil;

bt^.rchild:=nil;

             End

           Else if n<bt^.data then insert(bt^.lchild,n)

                             else if n>bt^.data theninsert(bt^.rchild,n); 

End;

（4）、在二叉树中查找一个数，找到返回该结点,否则返回nil

Function find(bt:tree;n:integer):tree;{在二叉树中查找一个数，

Begin                               找到返回该结点,否则返回nil }

  ifbt=nil then find:=nil

         else if n<bt^.data then find(bt^.lchild,n)

else if n>bt^.data then find(bt^.rchild,n)

                                         else find:=bt;

end;

（5）、用嵌套括号表示法输出二叉树

Procedure print(bt:tree);  {用嵌套括号表示法输出二叉树}

Begin

  If bt<>nil  then begin

Write(bt^.data);

If(bt^.lchild<>nil)or(bt^.rchild<>nil)  then 

                         Begin

                            Write(‘(’);

                            Print(bt^.lchild);

                            If bt^.rchild<>nilthen write(‘,’);

                            Print(bt^.rchild);

                            Write(‘)’);

                         End;

                  End;

End;

例：输入一颗二叉树，分别输出前序、中序、后序遍历的结果。

如：二叉树                              应在键盘输入：AB.C.D..EF..GH..IJ…

参考程序：program lx61(input,output);{指针类型}

type

  tpointer=^node;

  node=record

       lch,rch:tpointer;

       data:char

       end;

var

  root:tpointer;

  ch:char;

  procedure preorder(p:tpointer);

   begin

     if p<>nil then

       begin write(p^.data);preorder(p^.lch);preorder(p^.rch);end;

   end;

  procedure inorder(p:tpointer);

   begin

     if p<>nil then

       begininorder(p^.lch);write(p^.data);inorder(p^.rch);end;

   end;

   procedure postorder(p:tpointer);

   begin

     if p<>nil then

       beginpostorder(p^.lch); postorder(p^.rch);write(p^.data); end;

   end;

  procedure create(var p:tpointer);

   begin

     read(ch);

     if ch<> ‘.‘then

       beginnew(p);p^.data:=ch;create(p^.lch);create(p^.rch) end

      else p:=nil

   end;

begin

    write(‘input node= ‘);create(root);

   preorder(root);writeln;inorder(root);writeln;postorder(root);writeln

end.

program lx61;  {数组类型}                                          

const m=100;

type node=record

         data:char;

         lch,rch:0..m;

         end;

var tree:array[1..m]of node;

    n,i,j:1..m;

procedure preorder(i:integer);

  begin

  if i<>0 then

   begin write(tree[i].data:4);preorder(tree[i].lch);preorder(tree[i].rch)end;

  end;

procedure inorder(i:integer);

  begin

  if i<>0 then

   begininorder(tree[i].lch);write(tree[i].data:4);inorder(tree[i].rch) end;

  end;

procedure postorder(i:integer);

  begin

  if i<>0 then

   beginpostorder(tree[i].lch);postorder(tree[i].rch);write(tree[i].data:4) end;

  end;

begin

  readln(n);

  for i:=1 to n do

    begin

     read(tree[i].data);

     read(tree[i].lch);

     readln(tree[i].rch);

    end;

  preorder(1);writeln;inorder(1);writeln;postorder(1);writeln;

end.

三、普通有序树的另一种遍历方法

   先根遍历：转化为对应的二叉树后由前序遍历实现。

            ABEKLFCGDHIJ

   后根遍历：转化为对应的二叉树后由中序遍历实现。

            KLEFRGCHIJDA

例：P83输入一颗普通有序树，输出该树的先根次序和后根次序。  

参考程序：programlx83;

 constm=100;

 type

    node=record

         data:char;

         prt,lch,rch:1..m;

         end;

var tree:array[1..m]of node;

   i,j,p,n:1..m;

procedure preorder(i:integer);

  begin

    ifi<>0 then  begin

                    write(tree[i].data:3);

                    preorder(tree[i].lch);

                    preorder(tree[i].rch);

                  end;

  end;

procedure inorder(i:integer);

  begin

    ifi<>0 then  begin

                    inorder(tree[i].lch);

                    write(tree[i].data:3);

                    inorder(tree[i].rch);

                  end;

  end;

begin

 fillchar(tree,sizeof(tree),0);

 readln(n);

  fori:=1 to n do

   begin

     read(tree[i].data);

     read(j);

     if j<>0 then begin

                    tree[i].lch:=j;tree[j].prt:=i;

                    p:=j;

                     repeat

                       read(j);

                       if j<>0 then begin

                                     tree[p].rch:=j;tree[j].prt:=p;

                                      p:=j;

                                    end;

                      until j=0;

                   end;

     readln;

   end;

 preorder(1);writeln;inorder(1);

end.

四、 由二叉树的两种遍历顺序确定树结构

结论：已知前序序列和中序序列可以确定出二叉树；

已知中序序列和后序序列也可以确定出二叉树；

但，已知前序序列和后序序列却不可以确定出二叉树；为什么？举个 3个结点的反例。

例如：已知结点的前序序列为 ABCDEFG，中序序列为 CBEDAFG。构造出二叉树。过程见下图：

例：输入二叉树的前序与中序，输出二叉树的后序。

参考程序：

program lx89;

var c1,c2:string;

procedure solve2(s1,s2:string);

var k:integer;

  begin

   k:=pos(s2[1],s1);

    ifk>1 then solve2(copy(s1,1,k-1),copy(s2,2,k));

    ifk<length(s1) then solve2(copy(s1,k+1,length(s1)-k),copy(s2,k+1,length(s2)-k));

   write(s2[1]);

  end;

begin

 write(‘input inorder=‘); readln(c1);

 write(‘input preorder=‘); readln(c2);

 solve2(c1,c2);

end.

例：输入二叉树的中序与后序，输出二叉树的前序。

参考程序：

program lx88;

var c1,c2:string;

procedure solve(s1,s2:string);

  vark:integer;

  begin

    iflength(s2)=1 then write(s2)

     else begin

            k:=pos(s2[length(s2)],s1);

            write(s1[k]);

            if k>1 then solve(copy(s1,1,k-1),copy(s2,1,k-1));

            if k<length(s1) thensolve(copy(s1,k+1,length(s1)-k),copy(s2,k,length(s2)-k));

          end;

  end;

begin

 write(‘input inorder=‘); readln(c1);

 write(‘input postorder=‘); readln(c2);

 solve(c1,c2);

end.

4.5 二叉树的重要应用

（1）二叉排序树

①定义：二叉排序树是空树或具有以下性质：

        若根结点的左子树不空，则左子树的所有结点值均小于根结点值。

       若根结点的右子树不空，则右子树的所有结点值均大于根结点值。

       根结点的左右子树也分别为二叉排序树。

②应用：中序遍历二叉排序树，即可顺序输出各结点。

   例：输入 n (1≤n ≤100)

           a1, a2, …. An

       输出： 排序后的结果

program lx91;

const m=1000;

type benode=record     {用于存储树的结构}

            data:integer;

           lch,rch:1..m;

           end;

 varb:array[1..m]of benode;

    p,n,i:1..m;   a:array[1..m]ofinteger;  {用于保存输入的n个数}

 procedure createtree;

  begin

    fillchar(b,sizeof(b),0);

    b[1].data:=a[1];

    for i:=2 to n do

      begin

        b[i].data:=a[i]; p:=1;

        while true do

        begin

         if a[i]<b[p].data then

           if b[p].lch<>0 then p:=b[p].lch

              else begin b[p].lch:=i; break; end

           else if b[p].rch<>0 then p:=b[p].rch

                    else begin b[p].rch:=i;break end;

        end;

      end;

   end;

 procedure inorder(i:integer);

  begin

     ifi<>0 then begin

                    inorder(b[i].lch);

                    write(b[i].data:5);

                    inorder(b[i].rch);

                  end;

  end;

 begin

  write(‘n= ‘);readln(n);

  write(‘a[i]= ‘); for i:=1 to n do read(a[i]); writeln;

  createtree;

  inorder(1);

 end.

构造二叉排序树的平均时间复杂度为（n long ₂^N），优于选择排序和冒泡排序算法的（n²）

（2）最优二叉树

①定义：在具有n个带权叶子结点的二叉树中，使所有叶子结点的带权路径长度之和为最小的二叉树称为最小二叉树（或哈夫曼树）。  即：最小二叉树使 L =达到最小。

( 其中W_k表示第k个叶结点的权值，P _k表示第个k叶结点的路径长)

例：以下四棵二叉树中，叶结点为A、B、C、D、E，权值分别为7、5、2、4、6。

L=3(7+5)+2(2+4+6)=60   L=4(4+2)+3*5+2*6+7=58  L=7+2*5+3*2+4*5+6*5=63  L=2(7+5+6)+3(2+4)=54

②最优二叉树的构造方法：将n个结点看着是n个二叉树的根，则得到森林 F={T1, T2, ….Tn}

                        在F中取出权值最小的两棵树合并成新树，其根值为两棵子树根之和。

                        用新树代替原来的两棵树构成新的森林。

                        重复以上两步，直到森林合并成一颗树为止。

例：全校学生的成绩由百分制转换为五等分制，在五个等级上的分布不均匀，分布规律如下表：

分布范围：    0~59    60~69     70~79     80~89    90~100

分布情况%：   5        15        35        30        15

如果给出sum（1≤sum≤100000）个学生的百分制成绩，将它们转换成五分制成绩，至少要经过多少次比较，其中每个等次成绩的最少比较多少次。

输入：sum

     w1, w2, w3, w4, w5 (五个等级的成绩的分布规律)

输出：最少比较次数

      5个整数，分别为每个等次成绩的最少比较次数。

参考程序

program lx95;

const n=5;

     m=2*n-1;

type

 node=record

      data:integer;

      prt,lch,rch,lth:0..m;

      end;

wtype=array[1..n]of integer;

treetype=array[1..m]of node;

var tree:treetype;

   w:wtype;

    bt,m1,i,j,k,p,sum:integer;

procedure hufm(w:wtype;var tree:treetype;varbt:integer);

 function min(h:integer):integer;

    vari:integer;

   begin

     m1:=maxint;

     for p:=1 to h do

       if (tree[p].prt=0)and(m1>tree[p].data)

         then begin i:=p;m1:=tree[p].data;end;

     min:=i;

   end;

  begin

   fillchar(tree,sizeof(tree),0);

    fori:=1 to n do tree[i].data:=w[i];

    fork:=n+1 to m do begin

                        i:=min(k-1);tree[i].prt:=k;tree[k].lch:=i;

                         j:=min(k-1);tree[j].prt:=k;tree[k].rch:=j;

                        tree[k].data:=tree[i].data+tree[j].data;

                       end;

   bt:=m;

  end;

procedure ht(t:integer);

  begin

    ift=m then tree[t].lth:=0 else tree[t].lth:=tree[tree[t].prt].lth+1;

    iftree[t].lch<>0 then begin ht(tree[t].lch);ht(tree[t].rch) end;

  end;

begin

 readln(sum);

  fori:=1 to 5 do read(w[i]);

 hufm(w,tree,bt);

 ht(bt);

 writeln(sum*tree[bt].data);

  fori:=1 to 5 do write(sum*tree[i].lth*tree[i].data:7);

end.

第五章图

5.1 概念
1、定义：图是由顶点V的集合和边E的集合组成的二元组记G=（V，E）

下图是一无向图(顶点的前后顺序不限）

                 图1

V={V1,V2,V3,V4,V5}

 E={(V1,V2),(V2,V3),(V3,V4),(V4,V5),(V5,V1),(V2,V5),(V4,V1)}

下图是一有向图（顶点分先后顺序）

V={V1,V2,V3,V4}

E={<V1,V2>,<V2,V4>,<V1,V3>,<V3,V4>,<V4,V1>}

2、完全图（每一对不同的顶点都有一条边相连,n个顶点的完全图共有n（n-1）/2条边）
3、顶点的度：与顶点关联的边的数目，有向图中等于该顶点的入度与出度之和。
入度——以该顶点为终点的边的数目和
出度——以该顶点为起点的边的数目和

 度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。
[定理1] 图G中所有顶点的度数之和等于边数的2倍。因为计算顶点的度数时。每条边均用到2次。
[定理2] 任意一个图一定有偶数个奇点。

4、路径和连通集
    在图G=（V，E）中，如果对于结点a，b，存在满足下述条件的结点序列x1……xk(k>1)
        ⑴ x1=a，xk=b
        ⑵ (xi，xi+1)∈E         i=1¨k-1
则称结点序列x1=a，x2，…，xk=b为结点a到结点b的一条路径，而路径上边的数目k-1称为该路径的长度，并称结点集合{x1，…，xk}为连通集。

5、简单路径和回路
如果一条路径上的结点除起点x1和终点xk可以相同外，其它结点均不相同，则称此路径为一条简单路径。上图1中v1→v2→v3是一条简单路径，v1→v2→v5→v1→v4不是简单路径。x1=xk的简单路径称为回路（也称为环）。例如上图2中，v1→v2→v4→v1为一条回路。

6、有根图
在一个有向图或无向图中，若存在一个结点w，它与其他结点都是连通的，则称此图为有根图，结点w即为它的根。上图1为有根图，v1、v2、v3、v4都可以作为根。

7、连通图和最大连通子图
对于无向图而言，若其中任两个结点之间的连通，则称该图为连通图。一个无向图的连通分支定义为此图的最大连通子图。上图(a)所示的图是连通的，它的最大连通子图即为其本身。

8、强连通图和强连通分支
若对于有向图的任意两个结点vi、vj间（vi≠vj），都有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称该有向图是强连通的。有向图中强连通的最大子图称为该图的强连通分支。 

5.2图的存储

1.邻接矩阵

        1(或权值)   表示 顶点i和顶点j有边(i和j的路程)

A(i,j)={

        0 表示顶点i和顶点j无边

  如图1的矩阵表示为

2.邻接表

  数组方法：

顶点      相邻顶点       邻接顶点数

 v[i]       d[i,j]            c[i]

链表方法：

3.边目录

如图2

  6.３图的遍历
1.深度优先遍历

  遍历算法：

 1)从某一顶点出发开始访问,被访问的顶点作相应的标记,输出访问顶点号.

  2)从被访问的顶点出发,搜索与该顶点有边的关联的某个未被访问的邻接点

再从该邻接点出发进一步搜索与该顶点有边的关联的某个未被访问的邻接点,直到全部接点访问完毕.如图1从V1开始的深度优先遍历序列为V1，V2，V3，V4，V5。图2从V1开始的深度优先遍历序列为V1，V2，V4，V3。

算法过程：

procedure shendu(i);

begin

 write(i);

 v[i]:=true;

 for j:=1 to n do

  if (a[i,j]=1) and not(v[j]) then shendu(j);

end;

2.广度优先遍历

遍历算法：

1）从某个顶点出发开始访问，被访问的顶点作相应的标记，并输出访问顶点号；

2）从被访问的顶点出发，依次搜索与该顶点有边的关联的所有未被访问的邻接点，并作相应的标记。

3）再依次根据2）中所有被访问的邻接点，访问与这些邻接点相关的所有未被访问的邻接点，直到所有顶点被访问为止。如图3的广度优先遍历序列为C1,C2,C3,C4,C5,C6。

算法过程：

procedure guangdu(i);

 begin

  write(i);

  v[i]:=true;

  i进队;

  repeat

   队首元素出队设为k

   for j:=1 to n do

    if (a[k,j]=1) and (not v[j]) then

     begin

      write(j);

      v[j]:=true;

      j进队;

     end;

  until 队列q为空;

6.3 图的应用

例1:有A，B，C，D，E 5本书，要分给张、王、刘、赵、钱5位同学，每人只选一本。每人将喜爱的书填写下表，输出每人都满意的分书方案。

用递归方式程序如下:

program allotbook;
 type five=1..5;
 const like:array[five,five] of 0..1=
  ((0,0,1,1,0),(1,1,0,0,1),(0,1,1,0,0),(0,0,0,1,0),(0,1,0,0,1));
  name:array[five] of string[5]=(‘zhang‘,‘wang‘,‘liu‘,‘zhao‘,‘qian‘);
  var book:array[five] of five;
  flag:set of five;
  c:integer;
 procedure print;
 var i:integer;
 begin
  inc(c);
  writeln(‘answer‘,c,‘:‘);
  for i:=1 to 5 do
   writeln(name[i]:10,‘:‘,chr(64+book[i]));
 end;
 procedure try(i:integer);
 var j:integer;
 begin
  for j:=1 to 5 do
   if not(j in flag) and (like[i,j]>0) then
    begin flag:=flag+[j];
          book[i]:=j;
          if i=5 then print elsetry(i+1);
          flag:=flag-[j];
   end
end;
begin
 flag:=[];
 c:=0;
 try(1);
 readln;
end.

用非递归方法编程如下:

program allotbook;
 type five=1..5;
 const like:array[five,five] of 0..1=
  ((0,0,1,1,0),(1,1,0,0,1),(0,1,1,0,0),(0,0,0,1,0),(0,1,0,0,1));
  name:array[five] of string[5]=(‘zhang‘,‘wang‘,‘liu‘,‘zhao‘,‘qian‘);
  var book:array[five] of five;
  flag:set of five;
  c,dep,r:integer;
  p:boolean;
 procedure print;
 var i:integer;
 begin
  inc(c);
  writeln(‘answer‘,c,‘:‘);
  for i:=1 to 5 do
   writeln(name[i]:10,‘:‘,chr(64+book[i]));
 end;
begin
 flag:=[];
 c:=0;dep:=0;
 repeat
  dep:=dep+1;
  r:=0;
  p:=false;
  repeat
  r:=r+1;
  if not(r in flag) and (like[dep,r]>0) then
   begin
    flag:=flag+[r];
    book[dep]:=r;
    if dep=5 then print else p:=true
   end
   else if r>=5 then
    begin
     dep:=dep-1;
     if dep=0 then p:=true else beginr:=book[dep];flag:=flag-[r] end;
    end else p:=false;
  until p=true;
until dep=0;
 readln;

在应用树结构解决问题时，往往要求按照某种次序获得树中全部结点的信息，这种操作

叫作树的遍历。遍历的方法有多种，常用的有：

A、先序（根）遍历：先访问根结点，再从左到右按照前序思想遍历各棵子树。

如上图前序遍历的结果为：ABEKLFCGDHMIJ；

B、后序（根）遍历：先从左到右遍历各棵子树，再访问根结点。如上图后序

遍历的结果为：KLEFBGCMHIJDA;

C、层次遍历：按层次从小到大逐个访问，同一层次按照从左到右的次序。

如上图层次遍历的结果为：ABCDEFGHIJKLM；

大家可以看出，AB 两种方法的定义是递归的，所以在程序实现时往往也是采用递归的

思想。既通常所说的“深度优先搜索”。如用前序遍历编写的过程如下：

procedure tra1(t,m)   {递归}

begin

if t <>nil then begin

              write(t^.data,’  ’);      {访问根结点}

              for I:=1to m do             {前序遍历各子树}

tra1(t^.child[I],m);

end;

end;

C 这种方法应用也较多，实际上是我们将的“广度优先搜索”。思想如下：若某个结点

被访问，则该结点的子结点应登录，等待被访问。顺序访问各层次上结点，直至不再有未访

问过的结点。为此，引入一个队列来存储等待访问的子结点，设一个队首和队尾指针分别表

示出队、进队的下标。程序框架如下：

Const n=100;

Var hend,tail,I:integer;

   Q:array[1..n] of tree;

   P:tree;

Begin

 Tail:=1;head:=1;

 Q[tail]:=t;                      {t进队}

 Tail:=tail+1;

  While( head<tail) do             {队列非空}

   Begin

     P:=q[head];                   {取出队首结点}

     Head:=head+1;

     Write(p^.data,‘   ‘);      {访问某结点}

     For I:=1 to m do              {该结点的所有子结点按顺序进队}

        If p^.child[I]<>nil  then  begin 

q[tail]:=p^.child[I];

tail:=tail+1;

                                      end;

   End;

End;

 Chaobs编辑，转载请注明出处