A Single Traversal Algorithm for Serializing any Binary Tree

Austin Owino Wetoyi

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.


Keywords


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

Full Text:

PDF

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.




DOI (PDF): https://doi.org/10.24203/ajcis.v4i2.3714.g1962

Refbacks

  • There are currently no refbacks.