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 86
- Downloads 0
MANAGEMENT OF INDUCTION (ASYNCHRONOUS) MOTORS USING PLC
This paper describes the management of an induction (asynchronous) motor using PLC and VSD. For the realization of the practical part of this paper Schneider Electric equipment was used, which makes a complete system tha...
EVALUATION OF THE PERIOD OF SENSORS MOTION PARAMETERS OF THE TRAIN
The choice of polling period sensors for measuring the speed and acceleration of the train can be produced using the spectral representation of functions of velocity and acceleration from time to time. Using the spectral...
ROAD SAFETY MANAGEMENT IN LOCAL COMMUNITIES
The research of coordination of activities and responsibility-sharing at the appropriate level of road safety management, conducted by analyzing responses from the prepared Questionnaire, in the period before and after t...
PSYCHOLOGICAL CONNECTION BETWEEN COLORS AND CERTAIN CHARACTERISTIC TERMS
This paper presents results of a research on psychological connection between 40 offered colors and 91 terms from everyday life. Similar researches have been conducted and published in a number of instances in domestic a...
E-TEXTBOOK DEVELOPMENT CAPACITIES WITHIN THE CURRENT CONTEXT IN THE REPUBLIC OF SERBIA
The study is a short sublimation of the e-book and e-textbook development. In digital age and with the adoption of new technologies, new educational digital platform has become an integral part of our everyday life and e...