Non-recursive implementation of binary tree traversals, Data Structure & Algorithms

Assignment Help:

As we have seen, as the traversal mechanisms were intrinsically recursive, the implementation was also easy through a recursive procedure. Though, in the case of a non-recursive method for traversal, it need to be an iterative process; meaning, all of steps for the traversal of a node need to be under a loop so that the similar can be applied to all the nodes in the tree.

Algorithm: Non-recursive preorder binary tree traversal

Stack S

push root onto S

repeat until S is empty

{

v = pop S

if v is not NULL

visit v

push v's right child onto S

push v's left child onto S

}

Program 5 illustrates the program segment for the implementation of non- recursive preorder traversal.

 

/* preorder traversal of a binary tree, implemented via a stack */

void preorder(binary_tree_type *tree)

{

stack_type *stack;

stack = create_stack();

push(tree, stack);          /* push the first element of the tree onto the stack */

while (!empty(stack))

{

tree = pop(stack);

visit(tree);

push(tree->right, stack); /* push right child onto the stack */

push(tree->left, stack);    /* push left child onto the stack */

}

}


Related Discussions:- Non-recursive implementation of binary tree traversals

2 Flow Charts, 1.Create a flowchart to show the process that will allow the...

1.Create a flowchart to show the process that will allow the implementation of Stack, Push, and Pop operations. 2.Create a flowchart to show the process that will allow the impleme

Sorting algorithm for singly linked lists, Q. Which sorting algorithm can b...

Q. Which sorting algorithm can be easily adaptable for singly linked lists? Explain your answer as well.        Ans: The simple Insertion sort is sim

Explain depth-first traversal, Depth-first traversal A depth-first t...

Depth-first traversal A depth-first traversal of a tree visit a node and then recursively visits the subtrees of that node. Likewise, depth-first traversal of a graph visits

Explain about hidden-surface, Explain about Hidden-surface Hidden-line...

Explain about Hidden-surface Hidden-line removal refers to wire-frame diagrams without surface rendering and polygonal surfaces with straight edges. Hidden-surface removal ref

Need it urgently, Write an assembly program to separate the number of posit...

Write an assembly program to separate the number of positive numbers and negative numbers from a given series of signed numbers.

Rotations in binary tree, H o w can you r ot a t e a B i n a r y...

H o w can you r ot a t e a B i n a r y Tr e e? E x pl a i n r i g h t a n d l eft r ot a tion s by taking an e x a mpl e.   If after

Write an algorithm insert, Q. Write an algorithm INSERT which takes a point...

Q. Write an algorithm INSERT which takes a pointer to a sorted list and a pointer to a node and inserts the node into its correct position or place in the list.  Ans: /* s

Write an algorithm for binary search, Q.1 Write procedures/ Algorithm to in...

Q.1 Write procedures/ Algorithm to insert and delete an element in to array. Q.2. Write an algorithm for binary search. What are the conditions under which sequential search of

Pipelining., How branching takes place in Instruction pipeline. Explain wit...

How branching takes place in Instruction pipeline. Explain with suitable examples

The two famous methods for traversing, The two famous methods for traversin...

The two famous methods for traversing are:- a) Depth first traversal b) Breadth first

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd