２分木を中順でなぞりたいのですが（pascal)
課題で「２分探索木にデータを挿入する手続きを定義し、作った木を中順になぞって出力せよ」というのが出されました。
6
/ \
4 7
/ \
2 9
\ / \
3 8 10
\
11
\
12
このような木を考えプログラムを組み実行できたのですが、結果が「2,3,4,6,7,8,9,10,11,12」となってしまいます。中順だと「3,2,4,6,8,9,12,11,10,7」のはずなので合いません。
どこがおかしいのかご指摘お願いします。
ソースは以下の通りです。
program tree_search (input,output);
type elementtype = integer;
pointertype = ^celltype;
celltype = record
element : elementtype;
leftson : pointertype;
rightson: pointertype
end;
var root : pointertype;
procedure inorder( node:pointertype);
begin
if (node <> nil) then
begin
inorder( node^.leftson);
write( node^.element);
inorder( node^.rightson)
end
end; ｛中順になぞる｝
procedure insert( x:integer; var p:pointertype);
begin
if ( p = nil) then
begin
new( p );
p^.element := x;
p^.leftson := nil;
p^.rightson := nil
end
else if ( x < p^.element ) then
insert( x,p^.leftson)
else if ( x > p^.element ) then
insert( x,p^.rightson)
end; ｛木に挿入する｝
procedure create( var p:pointertype );
begin
p:= nil
end; ｛空の木を作る｝
begin
create(root);
insert( 6,root );
insert( 4,root );
insert( 2,root );
insert( 3,root );
insert( 7,root );
insert( 9,root );
insert( 8,root );
insert( 10,root );
insert( 11,root );
insert( 12,root );
inorder( root )
end.
お礼
確かに高さが増える場合の計算時間なら、納得いきます。でも、可能性としては高さが増える場合は小さいですから、しっくりきませんね（笑）でも、すっきりしました。ありがとうございます。