Tree traversal: Difference between revisions

Revision as of 06:20, 3 July 2023

Revision as of 10:44, 23 August 2023

Line 104:

===Depth-first search implementation===

// import visualization libraries {

===={{anchor|Pre-order traversal code|Pre-order traversal code}}Pre-order implementation====

const { Tracer, Array1DTracer, GraphTracer, LogTracer, Layout, VerticalLayout } = require('algorithm-visualizer');

{|

// }

|- style="vertical-align:top;"

|

const G = [ // G[i][j] indicates whether the path from the i-th node to the j-th node exists or not

'''procedure''' preorder(node)

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],

'''if''' node = '''null'''

[1, 0, 1, 0, 0, 0, 0, '''return'''0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],

visit(node)

[0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0],

preorder(node.left)

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],

preorder(node.right)

[0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0],

|

[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],

'''procedure''' iterativePreorder(node)

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],

'''if''' node = '''null'''

[0, 0, 0, 0, 0, 0, 1, '''return'''0, 0, 0, 1],

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],

stack ← '''empty stack'''

[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],

stack.push(node)

];

'''while''' '''not''' stack.isEmpty()

node ← stack.pop()

const T = [ // mapping to G as a binary tree , [i][0] indicates left child, [i][1] indicates right child

visit(node)

[-1, -1],

// right child is pushed first so that left is processed first

[0, 2],

'''if''' node.right ≠ '''null'''

[-1, -1],

stack.push(node.right)

[1, 4],

'''if''' node.left ≠ '''null'''

[-1, -1],

stack.push(node.left)

[3, 8],

|}

[-1, 7],

[-1, -1],

[6, 10],

[-1, -1],

[9, -1],

];

// define tracer variables {

const treeTracer = new GraphTracer('Traversal In-order');

const arrayTracer = new Array1DTracer('Print In-order');

const logger = new LogTracer('Log');

Layout.setRoot(new VerticalLayout([treeTracer, arrayTracer, logger]));

treeTracer.set(G);

treeTracer.layoutTree(5);

arrayTracer.set(new Array(T.length).fill('-'));

Tracer.delay();

// }

let index = 0;

function inOrder(root, parent) {

if (root === -1) {

// logger {

logger.println('No more nodes. Backtracking.');

Tracer.delay();

// }

return;

}

// visualize {

logger.println(`Reached ${root}`);

treeTracer.visit(root, parent);

Tracer.delay();

logger.println(` Going left from ${root}`);

Tracer.delay();

// }

inOrder(T[root][0], root);

// visualize {

logger.println(`Printing ${root}`);

treeTracer.leave(root);

arrayTracer.patch(index++, root);

Tracer.delay();

logger.println(` Going right from ${root}`);

Tracer.delay();

// }

inOrder(T[root][1], root);

}

inOrder(5); // node with key 5 is the root

// logger {

logger.println('Finished');

// }

===={{anchor|Post-order traversal code|Post-order traversal code}}Post-order implementation====