完全二叉树的定义？排序二叉树

完全二叉树定义完全二叉树(Complete Binary Tree)若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。完全二叉树是由满二叉树而引出来的。对于深度为K的，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。若一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。

请等一下 我在看你的程序。。。。。我也搞过OI能补充一下问题是什么吗。。？ 我的机子上没有FP要帮您调试的话稍等下 经过我简单的调试发现ins过程中少了一的exit导致201暴栈如果没有其他错误因该是在da[v].val:=a;后加一个exit;我本人写c++的 pascal可能写不好。。。。正确程序:type my=record val,l,r:longint; end;var n,i,root,a,ppool:longint; da:array[0..100010]of my;procedure print(v:longint);begin if v=0 then exit; print(da[v].l); write(da[v].val,’ ’); print(da[v].r);end;procedure ins(var v:longint;a:longint);begin if v=0 then begin inc(ppool); v:=ppool; da[v].val:=a; exit; end; if a《=da[v].val then ins(da[v].l,a) else ins(da[v].r,a);end;beginassign(input,’px.in’);reset(input);assign(output,’px.out’);rewrite(output);readln(n);for i:=1 to n do begin read(a); ins(root,a); end;print(root);writeln;close(output);end. 顺便补充一下10000的大小排序二叉树容易退化成链使用treap或sbt avl什么的效果会跟好 program cao;const maxn=101000; maxm=5000; range=maxint;type node=record left,right,total,key,value,fa:longint; end; Ttreap=object t:array[0..maxn] of node; total,root:longint; constructor init; procedure turn(father,son:longint); procedure insert(x:longint); procedure delete(x:longint); function find(x:longint):longint; end;var treap:Ttreap; a,b,c,data,origin,ans:array[0..maxn] of longint; i,j,k,l,n,m,tmp,p,q:longint;procedure swap(var a,b:longint);begin tmp:=a; a:=b; b:=tmp;end;function min(a,b:longint):longint;begin if a》b then exit(b) else exit(a);end;function max(a,b:longint):longint;begin if a》b then exit(a) else exit(b);end;constructor Ttreap.init;begin randomize; total:=1; with t[total] do begin total:=1; key:=-1; value:=-1; fa:=0; end; root:=1;end;procedure Ttreap.turn(father,son:longint);begin t[son].fa:=t[father].fa; if t[t[father].fa].right=father then t[t[father].fa].right:=son else t[t[father].fa].left:=son; t[father].fa:=son; if t[father].right=son then begin t[t[son].left].fa:=father; t[father].right:=t[son].left; t[son].left:=father; end else begin t[t[son].right].fa:=father; t[father].left:=t[son].right; t[son].right:=father; end; t[son].total:=t[father].total; t[father].total:=t[t[father].left].total+t[t[father].right].total+1;end;procedure Ttreap.insert(x:longint);var i,last:longint;begin i:=root; while i《》0 do begin last:=i; inc(t[i].total); if x》t[i].value then i:=t[i].right else i:=t[i].left; end; inc(total); with t[total] do begin total:=1; key:=random(range); value:=x; left:=0; right:=0; fa:=last; end; if x》t[last].value then t[last].right:=total else t[last].left:=total; while t[total].key《t[t[total].fa].key do turn(t[total].fa,total);end;procedure Ttreap.delete(x:longint);var i,last,h,j,k:longint;begin i:=root; while i《》0 do begin last:=i; dec(t[i].total); if x》t[i].value then i:=t[i].right else begin h:=i; i:=t[i].left; end; end; t[h].value:=t[last].value; t[h].key:=t[last].key; if t[last].left=0 then k:=t[last].right else k:=t[last].left; j:=t[last].fa; t[k].fa:=j; if t[j].left=last then t[j].left:=k else t[j].right:=k;end;function Ttreap.find(x:longint):longint;var i:longint;begin i:=t[root].right; while x》0 do begin if t[t[i].left].total+1=x then exit(t[i].value); if t[t[i].left].total》=x then i:=t[i].left else begin x:=x-t[t[i].left].total-1; i:=t[i].right; end; end;end;procedure qsort(left,right:longint);var i,j,x,xx:longint;begin i:=left; j:=right; x:=a[(i+j) shr 1]; xx:=b[(i+j) shr 1]; while i《j do begin while (a[i]《x)or((a[i]=x)and(b[i]《xx)) do inc(i); while (a[j]》x)or((a[j]=x)and(b[j]》xx)) do dec(j); if i《=j then begin swap(a[i],a[j]); swap(b[i],b[j]); swap(c[i],c[j]); swap(origin[i],origin[j]); inc(i); dec(j); end; end; if i《right then qsort(i,right); if j》left then qsort(left,j);end;procedure init;begin read(n,m); for i:=1 to n do read(data[i]); for i:=1 to m do begin origin[i]:=i; read(a[i],b[i],c[i]); end;end;procedure main;begin qsort(1,m); treap.init; b:=-1; for i:=1 to m do begin for j:=a[i-1] to min(b[i-1],a[i]-1) do treap.delete(data[j]); for j:=max(b[i-1]+1,a[i]) to b[i] do treap.insert(data[j]); ans[origin[i]]:=treap.find(c[i]); end;end;procedure print;begin for i:=1 to m do writeln(ans[i]);end;begin init; main; print;end.这是个treap的代码题目是vijos1081你可以看一下treap怎么写。。

二叉树(binarytree)是另一种树型结构，它的特点是每个结点至多只有二棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒.二叉树是一种数据结构（有好多类型）从根节点开始，每一个节点都有2个或2个以下的子节点。在数据结构中用指针进行操作。就像是一个父亲有两个儿子儿子们又各有自己的儿子（可以是两个也可以是一个）像树枝一样分叉