Same fringe: Difference between revisions

Content added Content deleted
(→‎{{header|Tcl}}: Added zkl)
m (→‎version 1.1: changed some comments, simplified some IF statements.)
Line 1,710: Line 1,710:
:::* combined subroutines   '''attleft'''   and   '''attright'''   into one
:::* combined subroutines   '''attleft'''   and   '''attright'''   into one
:::* streamlined the   '''make_tree'''   subroutine
:::* streamlined the   '''make_tree'''   subroutine
<lang rexx>/*REXX program examines the leaves of two binary trees (shown below). */
<lang rexx>/*REXX program examines the leaves of two binary trees (as shown below).*/
_=left('',28); say _ ' A A '
_=left('',28); say _ " A A "
say _ ' / \ ◄────1st tree / \ '
say _ " / \ ◄════1st tree / \ "
say _ ' / \ / \ '
say _ " / \ / \ "
say _ ' / \ / \ '
say _ " / \ / \ "
say _ ' B C B C '
say _ " B C B C "
say _ ' / \ / 2nd tree────► / \ / '
say _ " / \ / 2nd tree════► / \ / "
say _ ' D E F D E F '
say _ " D E F D E F "
say _ ' / / \ / / \ '
say _ " / / \ / / \ "
say _ 'G H I G δ I '
say _ "G H I G δ I "
say
say; #=0 /*#: # of leaves. */
parse var # done. 1 node. /*set all these variables to zero*/
#=0; done.=0; node.=0 /*initialize # leaves,DONE.,NODE.*/
call make_tree 1 /*define tree number 1 (1st tree)*/
call make_tree 1 /*define tree number 1 (1st tree)*/
call make_tree 2 /* " " " 2 (2nd " )*/
call make_tree 2 /* " " " 2 (2nd " )*/
z1=root.1; L1=node.1.z1; done.1.z1=1 /*L1 is a leaf on tree #1. */
z1=root.1; L1=node.1.z1; done.1.z1=1 /*L1 is a leaf on tree number 1. */
z2=z1; L2=node.2.z2; done.2.z2=1 /*L2 " " " " " #2. */
z2=z1; L2=node.2.z2; done.2.z2=1 /*L2 " " " " " " 2. */


do # % 2 /*loop for the number of leaves. */
do # % 2 /*loop for the number of leaves. */
if L1==L2 then do
if L1==L2 then do
if L1==0 then call sayX 'The trees are equal.'
if L1==0 then call sayX 'The trees are equal.'
say ' The ' L1 " leaf is identical in both trees."
say ' The ' L1 " leaf is identical in both trees."
do until \done.1.z1
do until \done.1.z1
z1=go_next(z1,1); L1=node.1.z1
z1=go_next(z1,1); L1=node.1.z1
end
end
done.1.z1=1
done.1.z1=1
do until \done.2.z2
do until \done.2.z2
z2=go_next(z2,2); L2=node.2.z2
z2=go_next(z2,2); L2=node.2.z2
end
end
done.2.z2=1
done.2.z2=1
end
end
Line 1,748: Line 1,748:
exit
exit
/*──────────────────────────────────GO_NEXT subroutine──────────────────*/
/*──────────────────────────────────GO_NEXT subroutine──────────────────*/
go_next: procedure expose node.; arg q,t /*find next node.*/
go_next: procedure expose node.; arg q,t /*find next node.*/
next=0
next=.
if node.t.q._Lson\==0 then /*is there a left branch in tree?*/
if node.t.q._Lson\==0 &, /*is there a left branch in tree?*/
if node.t.q._Lson.done==0 then do /*has this node been visited yet?*/
node.t.q._Lson.vis==0 then do /*has this node been visited yet?*/
next=node.t.q._Lson /*──► next node. */
next=node.t.q._Lson /*──► next node. */
node.t.q._Lson.done=1 /*mark Lson done.*/
node.t.q._Lson.vis=1 /*leftside done. */
end
end
if next==0 then
if next==. &,
if node.t.q._Rson\==0 then /*is there a right tree branch ? */
node.t.q._Rson\==0 &, /*is there a right tree branch ? */
if node.t.q._Rson.done==0 then do /*has this node been visited yet?*/
node.t.q._Rson.vis==0 then do /*has this node been VISited yet?*/
next=node.t.q._Rson /*──► next node*/
next=node.t.q._Rson /*──► next node. */
node.t.q._Rson.done=1 /*mark Rson don*/
node.t.q._Rson.vis=1 /*rightside done.*/
end
end
if next==0 then next=node.t.q._dad /*process the father node. */
if next==. then next=node.t.q._dad /*process the father node. */
return next /*the next node (or 0, if done).*/
return next /*the next node (or 0, if done).*/
/*──────────────────────────────────MAKE_NODE subroutine────────────────*/
/*──────────────────────────────────MAKE_NODE subroutine────────────────*/
Line 1,769: Line 1,769:
return q /*number of the node just created*/
return q /*number of the node just created*/
/*──────────────────────────────────MAKE_TREE subroutine────────────────*/
/*──────────────────────────────────MAKE_TREE subroutine────────────────*/
make_tree: procedure expose node. root. #; arg tree /*build a tree.*/
make_tree: procedure expose node. root. #; parse arg tree /*build trees*/
if tree==1 then hhh='H'
if tree==1 then hhh='H' /* [↓] must be a wood duck*/
else hhh='δ' /*the odd duck in the whole tree.*/
else hhh='δ' /*the odd duck in the whole tree.*/
a=make_node('A',tree); root.tree=a
a=make_node('A', tree); root.tree=a
b=make_node('B',tree); call son 'L',b,a,tree
b=make_node('B', tree); call son 'L', b,a,tree
c=make_node('C',tree); call son 'R',c,a,tree
c=make_node('C', tree); call son 'R', c,a,tree
d=make_node('D',tree); call son 'L',d,b,tree
d=make_node('D', tree); call son 'L', d,b,tree
e=make_node('E',tree); call son 'R',e,b,tree
e=make_node('E', tree); call son 'R', e,b,tree
f=make_node('F',tree); call son 'L',f,c,tree
f=make_node('F', tree); call son 'L', f,c,tree
g=make_node('G',tree); call son 'L',g,d,tree
g=make_node('G', tree); call son 'L', g,d,tree
/*quacks like a duck?*/ h=make_node(hhh,tree); call son 'L',h,f,tree
/*quacks like a duck?*/ h=make_node(hhh, tree); call son 'L', h,f,tree
i=make_node('I',tree); call son 'R',i,f,tree
i=make_node('I', tree); call son 'R', i,f,tree
return
return
/*──────────────────────────────────SAYX subroutine─────────────────────*/
/*──────────────────────────────────SAYX subroutine─────────────────────*/
Line 1,787: Line 1,787:
son: procedure expose node.; parse arg ?,son,dad,t; LR = '_'?"SON"
son: procedure expose node.; parse arg ?,son,dad,t; LR = '_'?"SON"
node.t.son._dad=dad; q=node.t.dad.LR /*define which son [↑] */
node.t.son._dad=dad; q=node.t.dad.LR /*define which son [↑] */
if q\==0 then do; node.t.q._dad=son; node.t.son.LR=q; end
if q\==0 then do; node.t.q._dad=son; node.t.son.LR=q; end
node.t.dad.LR=son
node.t.dad.LR=son
if ?=='R' then if node.t.dad.LR>0 then node.t.le._brother=node.t.dad.LR
if ?=='R' & node.t.dad.LR>0 then node.t.le._brother=node.t.dad.LR
return</lang>
return</lang>
'''output'''
'''output'''
Retrieved from "https://rosettacode.org/wiki/Same_fringe"