A taxonomy of binary tree traversals

DOI10.1007/BF01933706MaRDI QIDQ1085614zbMATH OpenOpenAlexFDO

Authors Alfs Berztiss

Publication date 1986

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01933706

zbMATH Keywords

data structureprogram schema

Mathematics Subject Classification ID

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10)

Review text

A survey of the literature shows that eleven binary tree traversals have been defined. We systematize this work by proposing a classification that consists of twenty-six traversals grouped into seven categories. Three generator schemas are provided that allow all of the traversals to be implemented.

Recommendations

• Morris' tree traversal algorithm reconsidered
• Parallel algorithms for tree traversals
• A study of binary tree traversal algorithms and a tag-free threaded representation
• Generation of binary trees from (0-1) codes
• scientific article; zbMATH DE number 4062616

Cites work

• Addressless Units for Carrying Out Loop-Free Computations
• Another representation of binary tree traversal
• Co-expression in Icon
• Depth-first K-trees and critical path analysis
• Depth-First Search and Linear Graph Algorithms
• scientific article; zbMATH DE number 3750256 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3497312 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• scientific article; zbMATH DE number 3400425 (Why is no real title available?)
• Marking algorithms
• Nonrecursive traversals of trees
• Some ideas on data types in high-level languages

Cited in

(10)

• Morris' tree traversal algorithm reconsidered
• A unified approach to parallel depth-first traversals of general trees
• Breadth-first traversal of trees and integer sorting in parallel
• Object-oriented tree traversal with JJForester.
• The Expected Performance of Traversal Algorithms in Binary Trees
• Constructing a binary tree efficiently from its traversals
• A COST-OPTIMAL EREW BREADTH-FIRST ALGORITHM FOR ORDERED TREES, WITH APPLICATIONS∗
• scientific article; zbMATH DE number 844505 (Why is no real title available?)
• Vectorization of tree traversals
• Optimal binary search trees

This page was built for publication: A taxonomy of binary tree traversals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1085614)