zbMATH — the first resource for mathematics

Generation of binary trees from (0-1) codes. (English) Zbl 0742.68024
Summary: A binary tree can be represented by a code reflecting the traversal of the corresponding regular binary tree in a given monotonic order. A different coding scheme based on the branches of a regular binary tree with \(n\)-nodes is proposed. It differs from the coding scheme generally used and makes no distinction between internal nodes and terminal nodes. A code of a regular binary tree with \(n\)-nodes is formed by labeling the left branches by 0’s and the right branches by 1’s and then traversing these branches in pre-order. The root is always assumed to be on a left branch. Different order of traversals yield different codes. An efficient nonrecursive Pascal program of \(O(n \log_ 2 n)\) time complexity using the backtracking approach is given to generate these codes in colexicographic order.

68W10 Parallel algorithms in computer science
68R05 Combinatorics in computer science
68P05 Data structures
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] DOI: 10.1145/322169.322170
[2] DOI: 10.1145/359423.359434 · Zbl 0345.68025
[3] DOI: 10.1145/322077.322082 · Zbl 0379.68029
[4] Knuth D.E., The art of computer programming 1 (1983)
[5] Rusky F., SIAM J.Comput 7 pp 745– (1978)
[6] DOI: 10.1137/0208006 · Zbl 0406.05026
[7] DOI: 10.1080/00207168508803477 · Zbl 0655.68080
[8] DOI: 10.1016/0304-3975(80)90073-0 · Zbl 0422.05026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.