ENUMERATION, RANKING AND GENERATION OF BINARY TREES BASED ON LEVEL-ORDER TRAVERSAL USING CATALAN CIPHER VECTORS
Journal Title: Journal of Information Technology and Application (JITA) - Year 2013, Vol 3, Issue 2
Abstract
In this paper, a new representation of a binary tree is introduced, called the Catalan Cipher Vector, which is a vector of elements with certain properties. It can be ranked using a special form of the Catalan Triangle designed for this purpose. It is shown that the vector coincides with the level-order traversal of the binary tree and how it can be used to generate a binary tree from it. Streamlined algorithms for directly obtaining the rank from a binary tree and vice versa, using the Catalan Cipher Vector during the processes, are given. The algorithms are analyzed for time and space complexity and shown to be linear for both. The Catalan Cipher Vector enables a straightforward determination of the position and linking for every node of the binary tree, since it contains information for both every node’s ancestor and the direction of linking from the ancestor to that node. Thus, it is especially well suited for binary tree generation. Using another structure, called a canonical state-space tableau, the relationship between the Catalan Cipher Vector and the level-order traversal of the binary tree is explained.
Authors and Affiliations
Adrijan Božinovski, Biljana Stojčevska, Veno Pačovski
Keywords
Related Articles
- EP ID EP244506
- DOI 10.7251/JIT1302078B
- Views 88
- Downloads 0
WEB PAGE CHARACTERISTICS OF EDUCATIONAL ADAPTIVE WEB SITES
Educational information about single topic may be found on many different website pages. Those web pages may have different roles, such as the display of information related to teaching, teaching content or routing to ot...
ENUMERATION, RANKING AND GENERATION OF BINARY TREES BASED ON LEVEL-ORDER TRAVERSAL USING CATALAN CIPHER VECTORS
In this paper, a new representation of a binary tree is introduced, called the Catalan Cipher Vector, which is a vector of elements with certain properties. It can be ranked using a special form of the Catalan Triangle d...
USING 3D MODELS FOR IMPROVING FACE RECOGNITION
Face recognition algorithm Principal Component Analysis (PCA) has a signifi cant performance drop when comparing photographs taken from different angle. In this paper a 3D model was used for improving that performance. M...
A CASE STUDY ON INTRODUCING E-LEARNING INTO SEAFARERS’ EDUCATION
This paper considers beginning steps in introducing e-learning into seafarers’ education, as additional mode of acquiring knowledge at the Faculty of Maritime Studies which is a part of the University of Montenegro. Rela...
HYBRID METHODOLOGY OF NONLINEAR GOAL PROGRAMMING
What we demonstrate here is a nonlinear goal-programming (NGP) algorithm based on hybrid connection of the modifi ed simplex method of goal programming, gradient method of feasible directions and method of optimal displa...