Anonymous user
Tree traversal: Difference between revisions
Added solution for Action!
m (→JS ES6) |
(Added solution for Action!) |
||
Line 555:
(let ((levels (flatten-level-r1 tree 0 nil)))
(flatten-level-r2 levels (len levels))))</lang>
=={{header|Action!}}==
Action! language does not support recursion. Therefore an iterative approach with a stack has been proposed.
The user must type in the monitor the following command after compilation and before running the program!<pre>SET EndProg=*</pre>
{{libheader|Action! Tool Kit}}
<lang Action!>CARD EndProg ;required for ALLOCATE.ACT
INCLUDE "D2:ALLOCATE.ACT" ;from the Action! Tool Kit. You must type 'SET EndProg=*' from the monitor after compiling, but before running this program!
DEFINE PTR="CARD"
DEFINE TREE_NODE_SIZE="5"
TYPE TreeNode=[BYTE tData PTR left,right]
DEFINE QUEUE_NODE_SIZE="4"
TYPE QueueNode=[PTR qData,qNext]
DEFINE STACK_NODE_SIZE="4"
TYPE StackNode=[PTR sData,sNext]
Type Tree=[PTR root] ;TreeNode POINTER
TYPE Stack=[PTR top] ;StackNode POINTER
TYPE Queue=[PTR front,rear] ;QueueNode POINTER
PROC QueueInit(Queue POINTER q)
q.front=0 q.rear=0
RETURN
BYTE FUNC QueueIsEmpty(Queue POINTER q)
IF q.front=0 THEN RETURN (1) FI
RETURN (0)
PROC QueuePush(Queue POINTER q TreeNode POINTER d)
QueueNode POINTER node,tmp
node=Alloc(QUEUE_NODE_SIZE)
node.qData=d
node.qNext=0
IF QueueIsEmpty(q) THEN
q.front=node
ELSE
tmp=q.rear
tmp.qNext=node
FI
q.rear=node
RETURN
PTR FUNC QueuePop(Queue POINTER q)
QueueNode POINTER node
TreeNode POINTER d
IF QueueIsEmpty(q) THEN
PrintE("Error: queue is empty!")
Break()
FI
node=q.front
d=node.qData
q.front=node.qNext
Free(node,QUEUE_NODE_SIZE)
RETURN (d)
PROC StackInit(Stack POINTER s)
s.top=0
RETURN
BYTE FUNC StackIsEmpty(Stack POINTER s)
IF s.top=0 THEN
RETURN (1)
FI
RETURN (0)
PROC StackPush(Stack POINTER s TreeNode POINTER d)
StackNode POINTER node
node=Alloc(STACK_NODE_SIZE)
node.sData=d
node.sNext=s.top
s.top=node
RETURN
PTR FUNC StackPop(Stack POINTER s)
StackNode POINTER node
TreeNode POINTER d
IF StackIsEmpty(s) THEN
PrintE("Error stack is empty!")
Break()
FI
node=s.top
d=node.sData
s.top=node.sNext
Free(node,STACK_NODE_SIZE)
RETURN (d)
PTR FUNC CreateTreeNode(BYTE d TreeNode POINTER l,r)
TreeNode POINTER node
node=Alloc(TREE_NODE_SIZE)
node.tData=d
node.left=l
node.right=r
RETURN (node)
PROC BuildTree(Tree POINTER t)
TreeNode POINTER t2,t3,t4,t5,t6,t7,t8,t9
t7=CreateTreeNode(7,0,0)
t4=CreateTreeNode(4,t7,0)
t5=CreateTreeNode(5,0,0)
t2=CreateTreeNode(2,t4,t5)
t8=CreateTreeNode(8,0,0)
t9=CreateTreeNode(9,0,0)
t6=CreateTreeNode(6,t8,t9)
t3=CreateTreeNode(3,t6,0)
t.root=CreateTreeNode(1,t2,t3)
RETURN
PROC DestroyTree(Tree POINTER t)
TreeNode POINTER n
Queue q
IF t.root=0 THEN RETURN FI
QueueInit(q)
QueuePush(q,t.root)
WHILE QueueIsEmpty(q)=0
DO
n=QueuePop(q)
IF n.left#0 THEN
QueuePush(q,n.left)
FI
IF n.right#0 THEN
QueuePush(q,n.right)
FI
Free(n,TREE_NODE_SIZE)
OD
t.root=0
RETURN
PROC VisitNode(TreeNode POINTER n)
PrintB(n.tData) Put(32)
RETURN
PROC PreOrder(Tree POINTER t)
TreeNode POINTER n
Stack s
StackInit(s)
StackPush(s,t.root)
WHILE StackIsEmpty(s)=0
DO
n=StackPop(s)
VisitNode(n)
IF n.right#0 THEN
StackPush(s,n.right)
FI
IF n.left#0 THEN
StackPush(s,n.left)
FI
OD
RETURN
PROC InOrder(Tree POINTER t)
TreeNode POINTER n
Stack s
StackInit(s)
n=t.root
DO
DO
IF n.right#0 THEN
StackPush(s,n.right)
FI
StackPush(s,n)
IF n.left#0 THEN
n=n.left
ELSE
EXIT
FI
OD
n=StackPop(s)
WHILE StackIsEmpty(s)=0 AND n.right=0
DO
VisitNode(n)
n=StackPop(s)
OD
VisitNode(n)
IF StackIsEmpty(s) THEN EXIT FI
n=StackPop(s)
OD
RETURN
PROC PostOrder(Tree POINTER t)
TreeNode POINTER n
Stack s,tmp
StackInit(s)
StackInit(tmp)
StackPush(s,t.root)
WHILE StackIsEmpty(s)=0
DO
n=StackPop(s)
StackPush(tmp,n)
IF n.left#0 THEN
StackPush(s,n.left)
FI
IF n.right#0 THEN
StackPush(s,n.right)
FI
OD
WHILE StackIsEmpty(tmp)=0
DO
n=StackPop(tmp)
VisitNode(n)
OD
RETURN
PROC LevelOrder(Tree POINTER t)
TreeNode POINTER n
Queue q
QueueInit(q)
QueuePush(q,t.root)
WHILE QueueIsEmpty(q)=0
DO
n=QueuePop(q)
IF n.left#0 THEN
QueuePush(q,n.left)
FI
IF n.right#0 THEN
QueuePush(q,n.right)
FI
VisitNode(n)
OD
RETURN
PROC Main()
Tree t
Put(125) PutE() ;clear screen
AllocInit(0)
BuildTree(t)
Print("pre-order: ") PreOrder(t) PutE()
Print("in-order: ") InOrder(t) PutE()
Print("post-order: ") PostOrder(t) PutE()
Print("level-order: ") LevelOrder(t) PutE()
DestroyTree(t)
RETURN</lang>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Tree_traversal.png Screenshot from Atari 8-bit computer]
<pre>
pre-order: 1 2 4 7 5 3 6 8 9
in-order: 7 4 2 5 1 8 6 9 3
post-order: 7 4 5 2 8 9 6 3 1
level-order: 1 2 3 4 5 6 7 8 9
</pre>
=={{header|Ada}}==
| |||