Trees

  • A tree is an abstract data type 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.

  • As a data structure implementing that ADT, a tree is a graph (a set of nodes and edges that connect them).

  • The nodes are connected is such a way that there is exactly one path between any two nodes.

  • In a rooted tree, each node can have zero or more children. Each node has one parent, except for the root, which has no parents.

  • Here are some more definitions:

    • A leaf is a node with no children.

    • An internal node is a node that is not a leaf. In other words, it is a node that has one or more children.

    • Two nodes are siblings if they have the same parent. The root cannot have any siblings.

    • The ancestors of a node dd are the nodes on the path from dd to the root. These include dd, dd's parent, dd's parent’s parent and so on up to the root. The root is an ancestor of every node in the tree.

    • If aa is an ancestor of dd, then dd is a descendant of aa.

    • The length of a path is the number of edges in the path.

    • The depth of a node nn is the length of the path from nn to the root. The depth of the root is zero. The depth of any node is the depth of its parent + 1.

    • The height of a node nn is the length of the path from nn to its deepest descendant. In other words, it is the longest path from nn to a leaf. The height of a leaf node is zero. The height of an internal node is the largest height among its children + 1.

    • The height of a tree is the height of the root, also the depth of the tree’s deepest node.

    • The subtree rooted at node nn is the tree formed by nn and its descendants.

    • A binary tree is a tree in which no node has more than two children, and every child is either a left child or a right child, even if it’s the only child its parent has.

Binary Tree Representation

  • A binary tree is a rooted tree wherein no node has more than two children. Additionally, every child is either a left child or a right child of its parent, even if it is its parent’s only child.

  • In the most popular binary tree representation, each tree node has three pointers to neighboring tree nodes:

    1. A parent pointer.

    2. A left pointer.

    3. A right pointer.

    (For some algorithms, the parent pointers are unnecessary.)

  • Each node also has a key (or item) reference.

    template <typename T>
class BinaryTreeNode {
    T item;
    BinaryTreeNode *parent;
    BinaryTreeNode *left;
    BinaryTreeNode *right;
};

    To represent the tree, we have a pointer to the node that is the root of the tree. We can also keep track of the tree’s size with an integer.

    template <typename T>
class BinaryTree {
    BinaryTreeNode<T> *root;
    int size;
};

  • We sometimes represent trees in other ways. For example, we use an array to represent a binary heap, which is based on a complete binary tree. To represent disjoint sets, we can use an array with links only from children to parents.

Traversals

  • A traversal is an algorithm (often defined recursively) to visit each node in a tree once.

  • Traversals can be used in many applications: printing each node’s value or performing some calculation on all nodes, for example.

  • There are four main ways to traverse the nodes of a tree:

    • Pre-order traversal: node, left, right.

    • Post-order traversal: left, right, node.

    • In-order traversal: left, node, right.

    • Level-order traversal: start at root, go down each level left to right.

  • Pre-order, post-oder and in-order traversals are examples of depth-first search. Level-order traversal is an example of breadth-first search.

Pre-Order Traversal

  • In the pre-order traversal, we first visit the root and then recursively traverse the root’s children from left to right.

  • An application is printing the structure of a file directory.

  • Pseudocode for binary trees:

    preOrder(node):
    if node ≠ nil:
        visit(node.key)
        preOrder(node.left)
        preOrder(node.right)

Post-Order Traversal

  • In the post-order traversal, we recursively traverse the root’s children from left to right subtree and then we visit the root itself.

  • An application is summing the disk space taken by directories.

  • Pseudocode for binary trees:

    postOrder(node):
    if node ≠ nil:
        postOrder(node.left)
        postOrder(node.right)
        visit(node.key)

In-Order Traversal

  • In the in-order traversal, we first recursively traverse the root’s left subtree (rooted at the left child), then we visit the root itself, then traverse the root’s right subtree.

  • This traversal is specific to binary trees.

  • An application is an expression tree with infix operators.

  • Pseudocode for binary trees:

    inOrder(node):
    if node ≠ nil:
        inOrder(node.left)
        visit(node.key)
        inOrder(node.right)

Level-Order Traversal

  • In the level-order traversal, we first visit the root, then all nodes with depth 1, then all nodes with depth 2, etc.

  • This traversal is not a naturally recursively algorithm.

  • An application is finding the shortest path between two nodes (if the path length is measured by the number of edges).

  • Another application is serialization/deserialization of a binary tree (as opposed to serialization in sorted order), allowing the tree to be re-constructed in an efficient manner.

  • Pseudocode for binary trees, using a queue:

    levelOrder(node):
    q = empty queue
    q.enqueue(node)
    while q is not empty:
        node = q.dequeue()
        visit(node)
        if node.left ≠ nil:
            q.enqueue(node.left)
        if node.right ≠ nil:
            q.enqueue(node.right)

    Interestingly, if we use a stack instead of a queue and push children onto the stack from right to left instead of from left to right, we will get pre-order traversal.

results matching ""

    No results matching ""