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 96
- Downloads 0
E-COMMERCE IN DINACARD SYSTEM
This paper presents the status of e-commerce in Serbia with the focus on the domestic DinaCard system, its architecture and participants in the system. We reported results on Internet transaction in DinaCard system in 20...
CRM PERFORMANCES ACCENTED WITH THE IMPLEMENTATION OF DATA WAREHOUSING AND DATA MINING TECHNOLOGIES
Customer Relationship Management (CRM) has become more and more a key strategy for large and small businesses. It supports marketing, sales, services and involves direct and indirect customer interaction. Customers are p...
SOFTWARE SIMULATIONS USAGE IN BUSINESS DECISION MAKING EDUCATION
Because of great importance in improving business decision making teaching process in educational institutions, a large number of software simulators are developed. Based on that information, it was necessary to present...
EU SERVICE DIRECTIVE, DIGITAL IDENTITY AND ID DOCUMENTS IN BOSNIA AND HERZEGOVINA
Abstract: In 2006, the European Union adopted the Services Directive, which establishes the obligation to establish unique points of contact through which citizens and businesses receive certain services from government...
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...