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 98
- Downloads 0
SOLVING THE CHIEF EXECUTIVE OFFICER SELECTION PROBLEM USING THE FUZZY DECISION SUPPORT SYSTEM
Chief Executive Offi cer (CEO) selection as a subset of personnel selection asks for different characteristic compared to a selection of other personnel. The reason for this is the polymorphic nature of the CEO role. The...
MULTIDIMENSIONAL NUMBERS AND SEMANTIC NUMERATION SYSTEMS:THEORETICAL FOUNDATION AND APPLICATION
In this article, we present a new class of numeration systems, namely Semantic Numeration Systems. The methodological background and theoretical foundations of such systems are considered. The concepts of abstract entity...
Influence of Infor matio n Tec hnologies on the Company’s Competiti ve Advantage on the Market in Conditio ns of the Global Crisis
In the recent decades, there has been recorded a great expansion in the computing and communication field and all the predictions are pointing to the further technological progress when using information technologies (IT...
MODEL FOR MANAGING SOFTWARE DEVELOPMENT PROJECTS BY FIXING SOME OF THE SIX PROJECT MANAGEMENT CONSTRAINTS
This study is focused on the software development process, viewed from perspective of information technology project manager. Main goal of this research is to identify challenges in managing such projects and provide a m...
APPLICATIONS OF SMARTPHONES FOR UBIQUITOUS HEALTH MONITORING AND WELLBEING MANAGEMENT
Advances in smartphone technology and data communications facilitate the use of ubiquitous health monitoring and mobile health application as a solution of choice for the overwhelming problems of the healthcare system. I...