6．33 PROGRAM ancestor(input,output);
{本程序判断结点j 是否是结点i 的子孙}
{假定结点数据是结点编号，否则设结点结构为
{RECORD lch,rch:integer;
dada:datatype END;将结点置于向量中}
CONST
n=9;
VAR L,r,t:ARRAY[1..n] OF
integer;
{L[1..n]和R[1..n] 是二叉树的存储结构}
{L[i]和R[i] 分别指示结点i的左孩子和右孩子,0 表示空}
i,j,k,ll,rr,j1: integer;
flag:boolean;
{FUNCTION
f(i,j:integer):integer;
{这是递归算法, 查j 是否是i的子孙}
VAR
k:integer;
BEGIN
IF NOT flag AND
(i<>0)
THEN
IF j=i THEN flag:=true
ELSE BEGIN k:=f(L[i],j);
IF
NOT flag THEN k:=f(r[i],j );
END;
END;
BEGIN
FOR i:=1 TO n DO read(L[i]);
FOR i:=1 TO n DO read(r[i]);{读入左右子女}
flag:=false; read
(i,j);
k:=f(i,j);
{调用递归子程序}
IF flag THEN writeln(j,’ 是’ ,i, ‘的子孙’)
ELSE writeln(j,’
不是’ ,i, ‘的子孙’);
END.}
{以下是非递归程序,先由L[1..n]和R[1.n] 建立其双亲向量T[1..n]}
BEGIN
FOR i:=1 TO n DO
READ(L[i],r[i]); FOR i:=1 TO n DO
t[i]:=0;
FOR i:=1 TO n DO
{建立其双亲向量}
BEGIN
LL:=L[i];
IF LL<>0 THEN t[LL]:=i;
rr:=r[i];
IF rr<>0 THEN t[rr]:=i;
END;
read(i,j);
j1:=j;{给定结点j, 其双亲t[j], 直到找到祖先i, 或到根失败}
WHILE (j<>i) AND
(j<>0) DO j:=t[j];
IF j<>0 THEN
writeln(i,' is ancestor of ',j1)
ELSE writeln(i,' is NOT
ancestor of
',j1);
END.
6.37
PROC preorder(bt:bit;var
ss:string);
{本算法非递归前序遍历二叉树，遍历序列置于ss中，ss初值为空，串联接符用’+’ }
IF bt<>NIL THEN {
若二叉树为空，则空操作}
[initstack(s);{栈初始化，栈中元素为二叉树结点指针}
PUSH(s,bt);
WHILE NOT
empty(s)
DO
[ p:=POP(s);{初退栈}
ss:=ss+p^.data;
IF p^.rchild<>NIL THEN
PUSH(s,p^.rchild);
{右子树非空，则右子树进栈}
IF p^.lchild<>NIL THEN
PUSH(s,p^.lchild);
]
FOR i:=1 TO LENGTH(ss) DO
write(ss[i]:4);]
ENDP；
IF
bt<>NIL THEN
{以下为非递归中序遍历算法}
[
p;=bt, initstack(s);
REPEAT
WHILE p<>nil DO [PUSH(s,p); p:=p^.lchild ]
IF NOT EMPTY(s) THEN
[p:=POP(s);
ss:=ss+p^.data;
p:=p^.rchild]]
UNTIL (p=nil) AND EMPTY(s)
]
6.38
TYPE
bnode=RECORD
ht:bitree; tag: char;{‘l’表示左分支，’r’表示右分支}
END
PROC postorder(ht:bitree);
{本算法非递归遍历二叉树，由于最后访问根结点，必须先把根结点指针进栈，以后序遍}
{历方式，访问完左子树和右子树后，才能将根从栈中退出并访问。为了区分从左子树回}
{来还是从右子树回来，加一标记tag.栈s存放bnode型元素, q是bnode型变量;}
IF ht<>NIL THEN
[initstack(s); p:=ht;{初始化}
REPEAT
WHILE p<>nil DO [ q.ht:=p; q.tag:=’l’; push(s,q); p:=p^.lchild]
{根结点及左子树进栈}
IF NOT EMPTY(s) THEN
[ q:=pop(s); p:=q.ht;
IF
q.tag=’r’{右子树已遍历，访问根结点}
THEN [write(p^.data); p:=nil;{不再进左子树} ]
ELSE[q.tag=’r’; PUSH(s,q); p:=p^.lchild]{右子树根进栈，再去遍历该根的左子树}
]
UNTIL (p=nil) AND
EMPTY(s)
6.43
PROC exchange (VAR
ht:bitree);
{ht是二叉树的根结点的指针，本算法递归交换二叉树中的所有结点的左右子树}
IF ht<>nil
THEN
[ p:=ht^.lchild; ht^.lchild:=ht^.rchild; ht^.rchild:=p; ] {交换根结点的左右子树}
IF
ht^.lchild<>nil
THEN exchange
(ht^.lchild); {递归交换左子树中所有结点的左右子树}
IF ht^.rchild<>nil
THEN exchange
(ht^.rchild); {递归交换右子树中所有结点的左右子树}
ENDP
6.47
PROC levelorder (ht:bitree; VAR
ss:string);
{本算法按层次遍历二叉树ht；ss 返回遍历序列，串的联接运算用‘+’}
IF ht<>nil THEN
[ iniqueue(q); {处始化队列，队列元素为二叉树节点的指针}
assign(ss,’’); {初始化遍历序列，SS为空}
enqueue(q,ht); {根节点指针入队列}
while not empty(q) do
[
p:=delqueue(q);
ss:=ss+p^.data;
IF p^.lchild<>nil then
enqueue(q,p^.lchild);
{若左子女非空，则左子女入队列}
IF p^.rchild<>nil then
enqueue(q,p^.rchild)
{若右子女非空，则右子女入队列}
]
FOR i:=1 to length(ss)
do write
(ss[i]:4);
]
ENDP;
6．49
FUNC completree
(ht:bitree):boolean;
{本算法判别二叉树ht是否为完全二叉树，如是，返回TRUE，否则返回FALSE。根据}
{完全二叉树的定义，其叶子节点最多出现在最下两层上，且任何结点左子树高度均与}
{其右子树的高度或者相等，或者多1。本算法仿照层次遍历思想。}
IF ht=nil THEN
completree:=TRUE
ELSE [
iniTqueue(q); enqueue(q,ht); flag:=true;
while not empty(q)
and flag DO
[ p:=delqueue(q);
IF p<>NIL THEN [ enqueue(p^.lchild); enqueue(p^.rchild)
]
else while not empty(q)
AND flag
DO
[p:=delqueue(q); IF q<>NIL THEN
flag:=FALSE]
]
completree:=flag;
ENDF;
6.54
PROC BuildBiTree (sa:sqbitree;VAR bt:bitree;
i:1..n);
{sa是含有n个结点的完全二叉树的顺序存储结构，bt是由sa建立的以二叉链表表示的}
{二叉树根结点的指针
，i为完全二叉树结点在顺序存储中的序号，初始调用时i=1}
IF I<=sa.last
THEN
[ new(bt);
bt^.data:=sa.elem[i];
{建立根结点}
IF 2*i>sa.last then bt^.lchild:=NIL
ELSE BuildBiTree (sa, bt^.lchild,2*i) ; {递归建立左子树}
IF 2*i+1>sa.last then bt^.rlchild:=NIL
ELSE BuildBiTree
(sa,bt^.rlchild,2*I+1) ; {递归建立右子树}
]
ENDP；
{以下是非递归算法，用队列。由此可看出队列和栈可用于同一问题中}
PROC BuildBiTree (sa:sqbitree;VAR bt:bitree;
n:integer);
IF n=0 THEN bt:=NIL {完全二叉树有0个结点，二叉树为空}
ELSE
[INITQUEUE(q); ENQUEUE(q,bt); I:=1;
WHILE NOE
EMPTY(q) DO
[bt:=DELQUEUE(q);
new(bt); bt^.data:=sa[I]; bt^.lchild:=NIL;
bt^.rchild:=NIL;
IF 2*i<=n THEN bt^.lchild:=NIL
ELSE ENQUEUE ( q,bt^.lchild); {为左子女分配空间}
IF 2*i+1<=n THEN bt^.rlchild:=NIL
ELSE ENQUEUE ( q,bt^.rchild); {为右子女分配空间}
i:=i+1;
]
ENDP;
6.65
PROC CreateBiTree(VAR
bt:bitree;pre,ino:arr;L1,h1,L2,h2:0..n);
{本算法由二叉树前序遍历序列和中序遍历序列建立其二叉链表的存储结构.bt是建立}
{的二叉树的根结点的指针.二叉树前序遍历序列和中序遍历序列,分别存于向量pre}
{和向量ino中,其下标范围分别是L1..h1和L2..h2,初始调用本过程时L1=L2=1;h1=h2=n}
IF L1<=h1 THEN {二叉树建立尚未完成}
[ new(bt);
bt^.data:=pre[L1];
{前序遍历第一元素肯定是根}
i:=L2;
WHILE ino[i]<>pre[L1] DO i:=i+1; {在中序遍历序列中找根}
IF i=L2 THEN bt^.lchild=NIL {以pre[L1]为根的二叉树无左子树}
ELSE CreateBiTree
(bt^.lchild,pre,ino,L1+1,L1+(i-L2),L2,i-1);
{ino中ino[L2..i-1]为以pre[L1]为根的二叉树的左子树}
IF i=h2 THEN bt^.rchild:=NIL {以pre[L1]为根的二叉树无右子树}
ELSE
CreateBiTree
(bt^.rchild,pre,ino,L1+(i-L2)+1,h1,i+1,h2)
{ino中ino[i+1..h2]为以pre[L1]为根的二叉树的右子树}
]
ENDP;
6.66
PROC CreateCSTreel (VAR t:CSTree;
pt:PTree);
{t是树的孩子兄弟链表表示法的根结点指针,pt是树的双亲表示法的向量,本算法已知pt,要}
{求建立t,,不失一般性,设向量中第一个元素为根,编号为1,其双亲为0,且树至少有一结点。}
new(t); t^.data:=pt[1].data; t^.fch:=nil; t^.nsib:=nil;
{建立根结点}
initqueue(q);
enqueue(q,t);{树根入队列}
while not empty(q) DO
[ p:=delqueue(q);
i:=2;查双亲为p的结点}
WHILE (i<=n) DO
IF
pt[pt[i].parent].data<>p^.data THEN i:=i+1
ELSE
{找到p的第一子女,在孩子兄弟链表中建立该结点,并插入队列}
[ new(p^.lchild); s:=p^.lchild; s
^.data;=pt[I].data; s ^.fch:=nil; s
^.nsib:=nil;
enqueue(q,
s); i:=i+1;
WHILE I<=n DO
{找结点的p的兄弟}
IF pt[pt[I].parent].data<>p^.data THEN i:=i+1
ELSE {找到s的兄弟,建立结点,并入队列}
[new(s^.nsib); s ^.fch:= s ^.nsib:=NIL; s ^.data;=pt[i].data; s:= s
^.nsib;
Enqueue(q, s)
;
]
]
]
ENDP;
6.66_1
PROC CreatePTree(VAR pt:PTree;
t:CSTree);
{本算法将n个结点的树由孩子兄弟链表表示法,转化为双亲表示法.算法的基}
{本思想是,设孩子兄弟链表t非空,则根结点为双亲表示法pt中第一元素,且无}
{双亲.将t入队列,进入循环：删除队头元素,确定其在pt中的下标i,若其有子女}
{则子女依次存入向量pt, 并入队列,其双亲均为i,之后再回到循环开始：出队,…..,}
{直至队列为空.}
initqueue(q);enqueue(q,t);{队列初始化,队列元素为二叉树中结点的指针}
pt[1].data:=t^.data;
pt[1].parent;=0;
k:=1;{k为已转到pt中的结点数}
WHile not empty(q) do
[ p:=delqueue(q);
i:=index(p^.data); { index函数查p^.data在pt中的位序}
IF p^.fch<>nil then {p有子女 }
[s:=p^.fch;
pt[k+1].data;=s^.data; pt[k+1].parent;=i; {子女的双亲为p}
k:=k+1;enqueue(q,s);{pt中元素增1, s入队列}
s:=s^.nsib;{查第一子女有无兄弟}
WHILE s<>nil do
{兄弟的双亲均为i,存入pt,并入队列}
[ pt[k+1].data:= s^.data;
pt[k+1].parent:=I; k:=k+1;enqueue(q,s);]
]
]
ENDP;
func
index(x:datatype):integer;
found:=false; j:=1;
WHILE (j<=k) AND NOT
found DO
IF pt[j].data<>x THEN j:=j+1 ELSE found:=true;
INDEX:=j;
ENDF;
6.66_2
PROC CreatePTree(VAR
pt:Ptree;t:CSTree);
{本算法同6.66_1,但使用栈.按前序遍历原则}
INITSTACK(S);
PUSH(S,t);
pt[1].data:=t^.data;
pt[1].parent:=0;
k:=1;{k为已转到pt中的结点数}
WHILE NOT EMPTY(S) DO
[p:=POP(S);
REPEAT
IF p^.nsib<>NIL THEN PUSH（S,p^.nsib）;
IF p^.fc<>NIL THEN { 处理左子女}
[ I:=INDEX(p^.data); {确定p^.data
在pt 中的位序}
p:=p^.fch; pt[k+1].data:=p^.data; pt[k+1].parent:=I; k:=k+1
]
ELSE
{处理本结点}
[
I:=PARENT(p^.data); {确定p^.data
的双亲在pt 中的位序}
pt[k+1].data:=p^.data; pt[k+1].parent:=I; k:=k+1
]
UNTIL
p^.fch=NIL
]
ENDP;
FUNC
parent(x:datatype):integer;
found:=false; j:=1;
WHILE (j<=k) AND NOT
found DO
IF pt[j].data<>x THEN j:=j+1 ELSE found:=true;
parent:=pt[j].parentj;
ENDF;