Permutation representation of k-ary trees
type: Item
instance of: scholarly article
title: Permutation representation of k-ary trees
zbMATH Open document ID: 0572.68055
DOI: 10.1016/0304-3975(85)90211-7
author: B. George
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: In this paper, we study the permutation representation of k-ary trees. First, we extend the notion of traversals, from binary trees to k-ary trees. A pair of k-ary tree traversals can be used to assign a permutation of the integers 1,2,... to each k-ary tree T. A pair of traversals is a valid k-ary tree Representation Scheme (k-RS) if it does not assign the same permutation to two distinct k-ary trees. We characterize such pairs of traversals. We also characterize those k-RS which assign permutations that have their lexicographic order being consistent with some well-known 'natural' order defined on the trees they represent.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 3913699
zbMATH Keywords: integer sequences
zbMATH Keywords: traversals
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90211-7
OpenAlex ID: W2073244180
cites work: A numbering system for binary trees
cites work: Q5585020
cites work: Q3741631
cites work: On a correspondence between binary trees and a certain type of permutation
cites work: Generation of Binary Trees from Ballot Sequences
cites work: Stack sortable permutations
cites work: Generating Binary Trees Lexicographically
cites work: Generating t-Ary Trees Lexicographically
cites work: Ranking and Listing Algorithms for k-Ary Trees
cites work: Lexicographic generation of ordered trees
Recommended article: The representation of permutations by trees
Recommended article: Representation of Tree Permutations by Words
Recommended article: Permutrees
Recommended article: Embedding small digraphs and permutations in binary trees and split trees
Recommended article: Some considerations on permutation trees
Recommended article: Q4880985
Recommended article: Q3378235
Recommended article: Q3504762
Recommended article: Perfect trees and bit-reversal permutations
description: scientific article; zbMATH DE number 3913699