Tree

Programming basics

In computer science, a tree is a widely used abstract data type (ADT)—or data structure implementing this ADT—that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.

A tree data structure can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root.

Image of a tree

tree vocabulary

• root node
• parent node
• child node
• leaf node

Practical applications of a tree

• Trees can be used to store data that has an inherent hierarchical structure. For example, an operating system may use a tree for directories, files and folders in its file management system.
• They are dynamic, which means that it is easy to add and delete nodes.
• They are easy to search and sort using standard traversal algorithms.
• They can be used to process the syntax of statements in natural and programming languages so are commonly used when compiling programming code.

Tree - video example

This video provides a basic introduction to trees. It also summarizes, very nicely, other data structures. Please keep in mind the example at the beginning is not a binary tree, but binary trees are discussed later. Ignore the discussion about cousins and uncles. It's ridiculous. But the rest of the video is really good.

code sample

class Node:
    def __init__(self, data):
        self.data = data
        self.children = []

    def add_child(self, child):
        self.children.append(child)

    def __repr__(self):
        return f"Node({self.data})"

class Tree:
    def __init__(self, root_data):
        self.root = Node(root_data)

    def add_node(self, parent_data, child_data):
        parent_node = self.find_node(parent_data)
        if parent_node:
            parent_node.add_child(Node(child_data))
        else:
            print(f"Parent node with data '{parent_data}' not found.")

    def find_node(self, target_data, current_node=None):
        if current_node is None:
            current_node = self.root

        if current_node.data == target_data:
            return current_node

        for child in current_node.children:
            result = self.find_node(target_data, child)
            if result:
                return result

        return None

    def display(self, current_node=None, level=0):
        if current_node is None:
            current_node = self.root

        print(' ' * 4 * level + '|-- ' + str(current_node.data))
        for child in current_node.children:
            self.display(child, level + 1)



    def __repr__(self):
        return f"Tree({self.root})"

# Create a tree with root node data 'A'
tree = Tree('A')

# Add nodes to the tree
tree.add_node('A', 'B')
tree.add_node('A', 'C')
tree.add_node('B', 'D')
tree.add_node('B', 'E')
tree.add_node('C', 'F')
tree.add_node('C', 'G')

# Find a node in the tree
found_node = tree.find_node('F')
print(found_node)  # Output: Node(F)

# Try to add a node with a nonexistent parent
tree.add_node('X', 'Y')  # Output: Parent node with data 'X' not found.

# Display the tree using simple ASCII art
tree.display()

Standards

• Describe how trees operate logically (both binary and non-binary).
• Define the terms: parent, left-child, right-child, subtree, root and leaf.
• State the result of inorder, postorder and preorder tree traversal.
• Sketch binary trees.

See Also

• Abstract data structures
• binary tree

External Links

high level discussion of binary trees

Give a sequence of brief answers with no explanation.

Give a detailed account or picture of a situation, event, pattern or process.

Give the precise meaning of a word, phrase, concept or physical quantity.

Give a specific name, value or other brief answer without explanation or calculation.

Give a specific name, value or other brief answer without explanation or calculation.

Represent by means of a diagram or graph (labelled as appropriate). The sketch should give a general idea of the required shape or relationship, and should include relevant features.