Non-recursive implementation of preorder traversal, Data Structure & Algorithms

Assignment Help:

For preorder traversal, in the worst case, the stack will rise to size n/2, where n refer to number of nodes in the tree. Another method of traversing binary tree non-recursively that does not employ stack requires pointers to the parent node (called threaded binary tree).

A threaded binary tree is a binary tree wherein every node which does not have a right child has a THREAD (a third link) to its INORDER successor. By doing this threading we ignore the recursive method of traversing a tree and employ of stack, that makes use of many memory and time.

A node structure of threaded binary is following :

For a threaded binary tree the node structure varies a bit and its like this -

struct NODE *leftchild;

int node_value;

struct NODE *rightchild;

struct NODE *thread;  /* third pointer to its inorder successor */

}


Related Discussions:- Non-recursive implementation of preorder traversal

Sorting, how to do a merge sorting

how to do a merge sorting

What are circular queues, What are circular queues?  Circular queue: St...

What are circular queues?  Circular queue: Static queues have a very large drawback that once the queue is FULL, even though we erase few elements from the "front" and relieve

Algorithm, Describe different methods of developing algorithms with example...

Describe different methods of developing algorithms with examples.

Complete trees, This is a k-ary position tree wherein all levels are filled...

This is a k-ary position tree wherein all levels are filled from left to right. There are a number of specialized trees. They are binary trees, AVL-trees, binary search trees, 2

String pattern matching, Document processing is quickly becoming one of the...

Document processing is quickly becoming one of the dominant functions of computers. Computers are utilized to edit, search & transport documents over the Internet, and to display d

Binary tree with depth 3, Q. Construct a complete binary tree with depth 3 ...

Q. Construct a complete binary tree with depth 3 for this tree which is maintained in the memory using the linked representation. Make the adjacency list and adjacency matrix for t

Explain about the abstract data type, Explain about the Abstract data type ...

Explain about the Abstract data type Abstract data type (ADT) A set of values (the carrier set) and operations on those values

What do you understand by structured programming, What do you understand by...

What do you understand by structured programming Structured Programming  This term is used for programming design that emphasizes:- (1) Hierarchical design of programmi

Balance theorem, Question 1 Discuss the following theorems with respect to...

Question 1 Discuss the following theorems with respect to Splay Trees- Balance Theorem Dynamic Finger Theorem   Question 2 Write a C program for implementation

What is class invariants assertion, What is Class invariants assertion ...

What is Class invariants assertion A class invariant is an assertion which should be true of any class instance before and after calls of its exported operations. Generally

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