Scribd
Upload
10 views

Week 07 Algorithms

Uploaded by

lujainmahesar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views

Week 07 Algorithms

Uploaded by

lujainmahesar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Algorithm: PREORDER (INFO, LEFT, RIGHT, ROOT)

A binary tree T is in memory, the algorithm does a preorder traversal of T, applying an


operation PROCESS to each of its nodes. An array STACK is used to temporarily hold
the address of nodes.

1. [initially push NULL onto STACK, and initialize PTR]


Set TOP = 1, STACK [1] = NULL and PTR = ROOT
2. Repeat Steps 3 to 5 while PTR ≠ NULL
3. Apply PROCESS to INFO [PTR]
4. [Right Child?]
If RIGHT [PTR] ≠ NULL, then [Push on STACK]
Set TOP = TOP + 1, and STACK [TOP] = RIGHT [PTR]
[End of If Structure]
5. [Left Child?]
If LEFT [PTR] ≠ NULL, then
Set PTR = LEFT [PTR]
Else: [Pop from STACK]
Set PTR = STACK [TOP] and TOP = TOP - 1
[End of If structure]
[End of Step 2 loop]
6. Exit.
Algorithm: INORDER (INFO, LEFT, RIGHT, ROOT)

A binary tree T is in memory, this algorithm does an inorder traversal of T, applying an


operation PROCESS to each of its nodes. An array STACK is used to temporarily hold
the address of nodes.

1. [Push NULL onto STACK and Initialize PTR]


Set TOP = 1, STACK [1] = NULL and PTR = ROOT
2. Repeat while PTR ≠ NULL: [Pushes left-most path onto STACK.]
a. Set TOP = TOP + 1 and STACK [TOP] = PTR. [Saves Node]
b. Set PTR = LEFT [PTR]. [Updates PTR]
[End of loop]
3. Set PTR = STACK [TOP] and TOP = TOP - 1. [Pops node from STACK]
4. Repeat Steps 5 to 7 while PTR ≠ NULL: [Backtracking]
5. Apply PROCESS to INFO [PTR]
6. [Right Child?] If RIGHT [PTR] ≠ NULL, then:
a. Set PTR = RIGHT[PTR]
b. Go to Step 2.
[End of If Structure.]
7. Set PTR = STACK [TOP] and TOP = TOP - 1[Pops node]
[End of Step 4 loop]
8. Exit.
Algorithm: POSTORDER (INFO, LEFT, RIGHT, ROOT)

A binary tree T is in memory, this algorithm does a postorder traversal of T, applying


an operation PROCESS to each of its nodes. An array STACK is used to temporarily
hold the address of nodes.

1. [Push NULL onto STACK and initialize PTR]


Set TOP = 1, STACK [1] = NULL and PTR = ROOT
2. [Push left-most path onto STACK]
Repeat Steps 3 to 5 while PTR ≠ NULL
3. Set TOP = TOP + 1 and STACK [TOP] = PTR [Pushes PTR on STACK]
4. If RIGHT [PTR] ≠ NULL, then; [Push on STACK]
Set TOP = TOP + 1 and STACK [TOP] = -RIGHT [PTR]
[End of If Structure]
5. Set PTR = LEFT [PTR]. [Updates pointer PTR]
[End of Step 2 loop]
6. Set PTR = STACK [TOP] and TOP = TOP - 1 [Pops node from STACK]
7. Repeat while PTR > 0
a. Apply PROCESS to INFO [PTR]
b. Set PTR = STACK [TOP] and TOP = TOP - 1
[Pops node from STACK]
[End of loop]
8. If PTR < 0, then
a. Set PTR = -PTR
b. Go to Step 2
[End of if structure]
9. Exit

You might also like