A Single Traversal Algorithm for Serializing any Binary Tree

Authors

  • Austin Owino Wetoyi Moi University But currently a research Fellow at Vrije Universiteit Brussel VUB, at Brussels in Belgium

Keywords:

Binary Tree, Tree Traversal, Data Compression, Binary Tree Linearization

Abstract

It is possible to save a binary tree to a file and restore it at a later time. Because these two operations are frequently necessary and therefore important, an efficient algorithm to represent a binary tree in a compact way is very desirable. For special types of binary trees, there are efficient algorithms, otherwise, there is a method that stores both the inorder and either preorder traversal or postorder traversal of the binary tree which requires two traversals of the binary tree during construction of the storage array. In this paper, I present an approach for which only one traversal is sufficient for construction of the storage array.  I also present a more efficient complement algorithm for restoration of the binary tree.

Author Biography

Austin Owino Wetoyi, Moi University But currently a research Fellow at Vrije Universiteit Brussel VUB, at Brussels in Belgium

Lecturer, Department of Information Technology

References

V. V. Muniswamy, Advanced Data Structures and Algorithms in C++, Mumbai: Jaico Publishing House, 2009.

G. Jacobson, "Space-efficient static trees and graphs.," in 30th IEEE Symposium, 1989.

Published

2016-04-15

How to Cite

Wetoyi, A. O. (2016). A Single Traversal Algorithm for Serializing any Binary Tree. Asian Journal of Computer and Information Systems, 4(2). Retrieved from https://www.ajouronline.com/index.php/AJCIS/article/view/3714

Issue

Section

Articles