pascal中二叉树是什么?怎么用,求程序
2 二叉树 1。二叉树的基本形态: 二叉树也是递归定义的,其结点有左右子树之分,逻辑上二叉树有五种基本形态: (1)空二叉树——(a); (2)只有一个根结点的二叉树——(b); (3)右子树为空的二叉树——(c); (4)左子树为空的二叉树——(d); (5)完全二叉树——(e) 注意:尽管二叉树与树有许多相似之处,但二叉树不是树的特殊情形。 2。两个重要的概念: (1)完全二叉树——只有最下面的两层结点度小于2,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树; (2)满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树,。 如下图: 完全二叉树 ...全部
2 二叉树 1。二叉树的基本形态: 二叉树也是递归定义的,其结点有左右子树之分,逻辑上二叉树有五种基本形态: (1)空二叉树——(a); (2)只有一个根结点的二叉树——(b); (3)右子树为空的二叉树——(c); (4)左子树为空的二叉树——(d); (5)完全二叉树——(e) 注意:尽管二叉树与树有许多相似之处,但二叉树不是树的特殊情形。
2。两个重要的概念: (1)完全二叉树——只有最下面的两层结点度小于2,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树; (2)满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树,。
如下图: 完全二叉树 满二叉树 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为结点编号则 如果IN,则无左儿子; 如果2*I 1N,则无右儿子。
4。二叉树的存储结构: (1)顺序存储方式 type node=record data:datatype l,r:integer; end; var tr:array[1。。n] of node; (2)链表存储方式,如: type btree=^node; node=record data:datatye; lchild,rchild:btree; end; 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); begin if e[t]=0 then exit else begin write(b[t]);e[t]:=0; t:=2*t;tree(t); t:=t 1;tree(t); end; end; begin repeat write('n=');readln(n); until (n>0) and (n0 then search(l); if r'#' do begin case ch of 'A'。
。'Z':begin new(p);p^。da:=ch;p^。l:=nil;p^。r:=nil; if topnil then inorder(head^。l); write(head^。da); if head^。
r=w then hyt(d,right) else hyt(d,left); end; procedure hyt1(p:point); begin with p^ do begin if leftnil then hyt1(right); end end; begin first:=nil;k:=true; for i:=1 to 8 do hyt(a[i],first); hyt1(root);writeln; end。
3。堆排序 堆:设有数据元素的集合(R1,R2,R3,。。。Rn)它们是一棵顺序二叉树的结点且有 Ri=) 堆的性质:堆的根结点上的元素是堆中的最小元素,且堆的每一条路径上的元素都是有序的。
堆排序的思想是: 1)建初始堆(将结点[n/2],[ n/2]-1,。。。3,2,1分别调成堆) 2)当未排序完时 输出堆顶元素,删除堆顶元素,将剩余的元素重新建堆。 程序如下: program duipx; const n=8; type arr=array[1。
。
n] of integer; var a:arr;i:integer; procedure sift(var a:arr;l,m:integer); var i,j, t:integer; begin i:=l;j:=2*i;t:=a[i]; while ja[j 1]) then j:=j 1; if t>a[j] then begin a[i]:=a[j];i:=j;j:=2*i; end else exit; end; a[i]:=t; end; begin for i:=1 to n do read(a[i]); for i:=(n div 2) downto 1 do sift(a,i,n); for i:=n downto 2 do begin write(a[1]:4); a[1]:=a[i]; sift(a,1,i-1); end; writeln(a[1]:4); end。收起