69 lines
1.7 KiB
Text
69 lines
1.7 KiB
Text
def \Node\ Left, Data, Right;
|
|
|
|
proc PreOrder(Node); \Traverse tree at Node in preorder
|
|
int Node;
|
|
[if Node # 0 then
|
|
[IntOut(0, Node(Data)); ChOut(0, ^ );
|
|
PreOrder(Node(Left));
|
|
PreOrder(Node(Right));
|
|
];
|
|
];
|
|
|
|
proc InOrder(Node); \Traverse tree at Node in inorder
|
|
int Node;
|
|
[if Node # 0 then
|
|
[InOrder(Node(Left));
|
|
IntOut(0, Node(Data)); ChOut(0, ^ );
|
|
InOrder(Node(Right));
|
|
];
|
|
];
|
|
|
|
proc PostOrder(Node); \Traverse tree at Node in postorder
|
|
int Node;
|
|
[if Node # 0 then
|
|
[PostOrder(Node(Left));
|
|
PostOrder(Node(Right));
|
|
IntOut(0, Node(Data)); ChOut(0, ^ );
|
|
];
|
|
];
|
|
|
|
proc LevelOrder(Node); \Traverse tree at Node in level-order
|
|
int Node;
|
|
def S=100*3; \size of queue (must be a multiple of 3 for wrap-around)
|
|
int Q(S), \queue (FIFO)
|
|
F, E; \fill and empty indexes
|
|
|
|
proc EnQ(Node); \Enqueue Node
|
|
int Node;
|
|
[Q(F):= Node(Left); F:= F+1;
|
|
Q(F):= Node(Data); F:= F+1;
|
|
Q(F):= Node(Right); F:= F+1;
|
|
if F >= S then F:= 0;
|
|
];
|
|
|
|
proc DeQ; \Dequeue Node
|
|
[Node(Left):= Q(E); E:= E+1;
|
|
Node(Data):= Q(E); E:= E+1;
|
|
Node(Right):= Q(E); E:= E+1;
|
|
if E >= S then E:= 0;
|
|
];
|
|
|
|
[F:= 0; E:= 0; \empty queue
|
|
EnQ(Node);
|
|
while E # F do
|
|
[DeQ;
|
|
IntOut(0, Node(Data)); ChOut(0, ^ );
|
|
if Node(Left) # 0 then
|
|
EnQ(Node(Left));
|
|
if Node(Right) # 0 then
|
|
EnQ(Node(Right));
|
|
];
|
|
];
|
|
|
|
int Tree;
|
|
[Tree:= [[ [[0,7,0],4,0], 2, [0,5,0]], 1, [ [[0,8,0], 6, [0,9,0]], 3, 0 ]];
|
|
Text(0, "preorder: "); PreOrder(Tree); CrLf(0);
|
|
Text(0, "inorder: "); InOrder(Tree); CrLf(0);
|
|
Text(0, "postorder: "); PostOrder(Tree); CrLf(0);
|
|
Text(0, "level-order: "); LevelOrder(Tree); CrLf(0);
|
|
]
|