pascal中二叉树是什么?怎么用,求程序
var
t,i,j:longint;
begin
t:=0;
for i:=1 to n do
begin
if i mod 20
then begin
inc(t);
j:=t;
writeln(a[i,j]);
end;
end;
end.
二叉树是另一种树型结构,它的特点是每个结点至多只有二棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。
一棵深度为k且有2(k)-1个结点的二叉树称为满二叉树,给每个结点编号,如果有深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称之为完全二叉树。
用途:
当问题结点最多有两个分支时,
或要将一个大问题分解两个相同小问题:如表达式求值
将一很长的表达式分解为:左操作数,操作符,右操作数
左操作数可能又是一个表达式,继续分解,右操作数也一样
又如:双路合并排序,快速排序,是非题推断等。。。
2叉树就是一种树
图片如下:
这就是一颗典型的二叉树。
二叉树是很多算法的基础。
要好好学!!!!!!!
IOI中国队的未来就在你身上了!!
二叉树是一种重要的数据结构(LZ不懂的话可以去查百度百科)
二叉树的遍历
遍历是对树的一种最基本的运算,所谓遍历二叉树,就是按一定的规则和顺序走遍二叉树的所有结点,使每一个结点都被访问一次,而且只被访问一次。由于二叉树是非线性结构,因此,树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
设L、D、R分别表示遍历左子树、访问根结点和遍历右子树, 则对一棵二叉树的遍历有三种情况:DLR(称为先根次序遍历),LDR(称为中根次序遍历),LRD (称为后根次序遍历)。
以下是Pascal递归实现遍历的过程(在这里,所有的二叉树都以数组的形式储存)
先序遍历
procedure first(i:longint);
begin
write(a[i]);
if a[i*2]<>0 then first(i*2);
if a[i*2+1]<>0 then first(i*2+1);
end;
中序遍历
procedure mid(i:longint);
begin
if a[i*2]<>0 then mid(i*2);
write(a[i]);
if a[i*2+1]<>0 then mid(i*2+1);
end;
后序遍历
procedure last(i:longint);
begin
if a[i*2]<>0 then last(i*2);
if a[i*2+1]<>0 then last(i*2+1);
write(a[i]);
end;
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为结点编号则 如果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=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 (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.用顺序存储方式建立一棵如图所示的二叉树,并对其进行先序遍历。
program tree1;
const n=15;
type node=record
data:char;
l,r:0..n;
end;
var tr:array[1..n] of node;
e:array[1..n] of 0..1;
i,j:integer;
procedure jtr;
var i:integer;
begin
for i:=1 to n do
with tr[i] do
readln(data,l,r);
end;
procedure search(m:integer);
begin
with tr[m] do
begin
write(data);
if l<>0 then search(l);
if r<>0 then search(r);
end;
end;
begin
jtr;search(1);writeln;
end.
例3 用链表存储方式生成上述二叉树,中序遍历之。
1.将上述二叉树用广义表表示为A(B(D,E(G)),C(F(,H)))
2.根据广义表串(以#结束)生成二叉树。
program ltree;
const n=8;
type trlist=^node;
node=record
da:char;
l,r:trlist;
end;
var s:array[1..n] of trlist;
p,root:trlist;
ch:char;
top,k:integer;
procedure creat(var head:trlist);
begin
read(ch);
top:=0;
while ch<>'#' do
begin
case ch of
'A'..'Z':begin new(p);p^.da:=ch;p^.l:=nil;p^.r:=nil;
if top<>0 then
case k of
1:s[top]^.l:=p;
2:s[top]^.r:=p;
end
end;
'(':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);
begin
if head^.l<>nil then inorder(head^.l);
write(head^.da);
if head^.r<>nil then inorder(head^.r);
end;
begin
write('Input tree string:');
creat(root);
inorder(root);
end.
5.3 二叉树的应用
1. 哈夫曼树与哈夫曼码
树的路径长度:一棵树的每一个叶结点到根结点的路径长度的和。
带权二叉树:给树的叶结点赋上某个实数值(称叶结点的权)。
带权路径长度:各叶结点的路径长度与其权值的积的总和。
哈夫曼树(最优二叉树):带权路径长度最小的二叉树。
如何构建哈夫树:(思想是:权越大离跟越近)
program gojiantree;
const n=4;m=7;
type node=record
w:real;
parent,lchild,rchild:0..m
end;
htree=array[1..m] of node;
var htree1:htree;
procedure gjtree(var ht:htree);
var i,j:integer;
small1,small2:real;
p1,p2:0..m;
begin
for i:=1 to m do
with ht[i] do
begin
w:=0;lchild:=0;rchild:=0;parent:=0;
end;
for i:=1 to n do read(ht[i].w);
for i:=n+1 to m do
begin
p1:=0;p2:=0;
small1:=1000;small2:=1000;
for j:=1 to i-1 do
if ht[j].parent=0 then
if ht[j].w<small1 then
begin small2:=small1;small1:=ht[j].w;p2:=p1;p1:=j end
else if ht[j].w<small2 then begin small2:=ht[j].w;p2:=j end;
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;
begin
gjtree(htree1);
end.
哈夫曼码:哈夫曼树的非叶结点到左右孩子的路径分别用0,1 表示,从根到叶的路径序列即为哈夫曼码。
哈夫曼码是不会发生译码多义性的不等长编码,广泛应用实际中。
(原因是任何一字符的编码不是更长编码的前缀部分,为什么?)
2.排序二叉树
排序二叉树:每一个参加排列的数据对应二叉树的一个结点,且任一结点如果有左(右)子树,则左(右)子树各结点的数据必须小(大)于该结点的数据。中序遍历排序二叉树即得排序结果。程序如下:
program pxtree;
const
a:array[1..8] of integer=(10,18,3,8,12,2,7,3);
type point=^nod;
nod=record
w:integer;
right,left:point ;
end;
var root,first:point;k:boolean;i:integer;
procedure hyt(d:integer;var p:point);
begin
if p=nil then
begin
new(p);
with p^ do begin w:=d;right:=nil;left:=nil end;
if k then begin root:=p; k:=false end;
end
else with p^ do if d>=w then hyt(d,right) else hyt(d,left);
end;
procedure hyt1(p:point);
begin
with p^ do
begin
if left<>nil then hyt1(left);
write(w:4);
if right<>nil 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<=R2i 和Ri<=R2i+1(或>=)
堆的性质:堆的根结点上的元素是堆中的最小元素,且堆的每一条路径上的元素都是有序的。
堆排序的思想是:
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 j<=m do
begin
if (j<m) and (a[j]>a[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.
利用二叉排序树,统计随机从键盘上输入的字符个数,然后输出字符和对应...
编写一个程序,由键盘输入一个字符串,统计该字符串中出现的字符及其次数。然后输出结果。要求用一个二叉树来保存处理结果,字符串中每个不同的字符用树的结点表示,结点应该包含四个域:该字符、该字符出现的次数、左子树指针、右子树指针;其中左子树的字符的ASCII码均小于该字符,右子树的字符的ASCII码...
9月计算机二级MS office测试题及答案(2)
【解析】根据二叉树的性质3:在任意一棵二叉树中,度为0的叶子结点总是比度为2的结点多一个,所以本题中度为2的结点是5-1=4个,所以度为1的结点的个数是25-5-4=16个。4.B 【解析】数据库系统的三级模式是概念模式、外模式和内模式。概念模式是数据库系统中全局数据逻辑结构的描述,是全体用...
哈夫曼树与哈夫曼编码、集合
前缀码(prefix code):任何字符的编码都不是另一字符编码的前缀,可以无二义地解码 用二叉树进行编码:(1)左右分支:0、1 (2)字符只在叶结点上 只要待编字符在叶结点上,其二叉树编码都不是另一字符编码的前缀 由哈夫曼树构造一棵编码代价最小的树 例:集合运算:交集、并集、...
可变长编码(赫夫曼编码,UTF-8编码)
赫夫曼树的定义:假设有 n 个权值{w1 ,w2 ,... ,w n },试构造一颗有 n 个叶子结点的二叉树,每个叶子结点带权为w i ,则其中带权路径长度WPL最小的二叉树称为 最优二叉树 或 霍夫曼树 。举个例子:假如现在有A ,B ,C ,D ,E这五个字符,它们分别出现的频率(即权值)为5,4,3,2...
patricia tree是什么
因此PAT tree有点像二叉查找树 ,最坏情况下是单支树(如上图例子),此时的时间复杂度是O(n-1),n为字符串的长度。最好情况下是平衡二叉树 结构,时间复杂度是O(log2(N))。另外,作为压缩的二叉查找树,其存储的空间代价大大减少了。PAT tree的实际应用 PAT tree在子串匹配上有很好的效率,这...
第17届信息学奥赛
2.字符“A”的ASCII码为十六进制41,则字符“Z”的ASCII码为十六进制的( )。 A.66 B.5A C.50 D.视具体的计算机而定3.右图是一棵二叉树,它的先序遍历是( )。A.ABDEFC B.DBEFAC C.DFEBCA D.ABCDEF 4.寄存器是( )的重要组成部分。 A.硬盘 B.高速缓存 C.内存 D.中央处理器(CPU)5.广度优先搜索...
下半年计算机二级c语言基础试题
根据分析,可画出右子树,故二叉树深度为4层。答案选择B选项。 7. 设有定义:struct{intn;floatx;}s[2],m[2]={{10,2.8},{0,0.0}};,则以下赋值语句中正确的是( )。 A. s[0]=m[1]; B. s=m; C.s.n=m.n; D. s[2].x=m[2].x; 【答案】A 【解析】定义了结构体类型数组s,长度为2...
第十三届全国青少年信息学奥林匹克联赛初赛试题及答案及答案_百度知 ...
A.二叉树 B.多叉树 C.哈希表 D.二维表 3.在下列各项中,只有( )不是计算机存储容量的常用单位。A.Byte B.KB C.UB D.TB 4.ASCII码的含义是( )。A.二→十进制转换码 B.美国信息交换标准代码 C.数字的二进制编码 D.计算机可处理字符的唯一编码...
悬赏!急!pascal竞赛普及组模拟试题
由树转换成的二叉树中,顶点N的左右子女分别是N在原树里对应顶点的( )。A. 最左子顶点\/最邻近的右兄弟B. 最右子顶点\/最右的兄弟C.最邻近的右兄弟\/最左的兄弟D.最邻近的左兄弟\/最邻近的右兄弟F. 最邻近的右兄弟\/最右的兄弟二、 问题解答:(共2题,每题5分,共10分)1、 光明中学开设数学、英语和信息学...
2017年全国计算机网络等级考试二级MS OFFICE高级应用考试真题
解析:二叉树中,度为0的节点数等于度为2的节点数加1,即n2=n0-1,叶子节点即度为0,则n2=79,总结点数为n0+n1+n2=80+70+79=229,答案为B。 (4)对长度为10的线性表进行冒泡排序,最坏情况下需要比较的次数为 A)9 B)10 C)45D)90 解析:冒泡法是在扫描过程中逐次比较相邻两个元素的大小,最坏的情况是每...
蓍郑速平: 二叉树是另一种树型结构,它的特点是每个结点至多只有二棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒.一棵深度为k且有2(k)-1个结点的二叉树称为满二叉树,给每个结点编号,如果有深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称之为完全二叉树.用途:当问题结点最多有两个分支时,或要将一个大问题分解两个相同小问题:如表达式求值 将一很长的表达式分解为:左操作数,操作符,右操作数 左操作数可能又是一个表达式,继续分解,右操作数也一样 又如:双路合并排序,快速排序,是非题推断等...
五莲县17758523339: pascal语言的二叉树是怎么回事啊??
蓍郑速平: 1.二叉树的基本形态: 二叉树也是递归定义的,其结点有左右子树之分,逻辑上二叉树有五种基本形态:
五莲县17758523339: pascal二叉树 - ?
蓍郑速平: 我来告诉你啊.前序的顺序是:根,左,右 中序的顺序是:左,根,右 后序的顺序是:左,右,根 如果你要求中序,那么我出个例子 前序ABCDE 后序CEBDA 中序就是:CBAED 推断过程就是:第一步,确定根A(因为后序的最后一个字母和...
五莲县17758523339: Pascal 二叉树?
蓍郑速平: 前序遍历就是先访问根节点,然后分别访问左右子节点完全二叉树是除最后一层以外,其他各层的节点数都达到最到的树,也就是说对于一颗高度为h的树,1~h-1层是一棵满二叉树,1 < 第h层的节点数 < 2^(h-1).满二叉树就是树的所有层节点都达到最到,任何一个节点都有2个子节点,总结点数=2^h-1,h是树高. “最到”应该是“最大”,这个拼音输入法不好用
五莲县17758523339: FBI树 pascal?
蓍郑速平: Var n:longint; function dg(n:longint):char; Var ch,ch1,ch2:char; Begin if n=0 Then Begin read(ch); if ch='1' Then ch:='I' else ch:='B'; End else Begin ch1:=dg(n-1); ch2:=dg(n-1); if ch1=ch2 Then ch:=ch1 else ch:='F'; End; write(ch); exit(ch); End; Begin readln(n); dg(n); writeln; End.
五莲县17758523339: pascal的二叉树算法?
蓍郑速平: (11)PS:2^11=2048<2381,2^12=4096>2381所以该树深度为12,又根节点为0,所以是11
五莲县17758523339: pascal中二叉树遍历 - ?
蓍郑速平: 哈,我也是编程爱好者,用Pascal,在北京.看看一下网址吧!经常不间断更新!http://www.mydrs.org/program/ 给你一个——二叉树后根遍历:Program Tree (input,output); Var p : Word; Mid,Pre : String; Procedure Init; Begin Write('In-order:'); ...
五莲县17758523339: 在free pascal中,怎样用顺序存储结构输入一个二叉树?多谢!! - ?
蓍郑速平: 提供两个思路 第一个 就类似heap那样开一个足够大的数组 a:array [1..maxn] of Tnode; 然后把 a[1..maxn div 2]是它的左子树 a[maxn div 2+1..maxn]是它的右子树 第二个 就是开一个大数组自己去模拟动态数据结构 type Tnode=record data,lptr,rptr:integer; end; data就是节点的数据 lptr就是左节点在数组中的下标,rptr就是右节点在数组中的下标
五莲县17758523339: 用PASCAL怎么编写二叉树不用链表?
蓍郑速平: 用3维数组,按先或中或后续遍历存储,不过没那么方便了,【father,date,son】
五莲县17758523339: PASCAL二叉树的建立 - ?
蓍郑速平: 已知先序中序: procedure Solve(pre,mid:string); var i:integer; begin if (pre='') or (mid='') then exit; i:=pos(pre[1],mid); solve(copy(pre,2,i),copy(mid,1,i-1)); solve(copy(pre,i+1,length(pre)-i),copy(mid,i+1,length(mid)-i)); post:=post+pre[1]; {加上根,递...