What Is a Tree Data Structure

A tree represents a non-linear data structure composed of n (n>=0) finite nodes organized in a hierarchical manner. The hierarchical nature means the structure is no longer one-to-one like linear structures, but rather one-to-many, where the number of elements at each level varies based on relationships with parent and child nodes.

The name "tree" derives from the fact that its structure resembles an inverted real tree.

Essential Tree Terminology

1.Node: Contains a data element and references to its child branches;

2.Degree of a Node: The number of subtrees a node possesses;

3.Leaf or Terminal Node: A node with degree 0;

4.Internal Node or Branch Node: A node with non-zero degree;

5.Degree of a Tree: The maximum degree among all nodes in the tree;

Family relationship terminology is also applied:

6.Child Node: The root of a node's subtree is called its child node;

7.Parent Node: A node containing children is the parent of those child nodes;

8.Sibling Nodes: Nodes sharing the same parent are siblings;

9.Ancestor Node: All nodes along the path from the root to a given node;

10.Descendant Node: Any node within a node's subtree;

11.Level of a Node: The root is at level 1, its children at level 2, and so on;

12.Cousin Nodes: Nodes whose parents are at the same level;

13.Depth or Height of a Tree: The maximum level among all nodes;

14.Forest: A collection of m (m>=0) disjoint trees;

15.Ordered and Unordered Trees: If node subtrees have a left-to-right order that cannot be interchanged, the tree is ordered; otherwise, its unordered;

16.Path and Path Length: A path consists of a sequence of nodes between two nodes, with path length being the number of edges traversed.

Fundamental Tree Properties

• Any tree consists of a root and subtrees—where subtrees are themselves trees—making trees recursively defined
• The root node has no predecessor; all other nodes have exactly one predecessor (parent)
• Nodes have zero or multiple successors
• Subtrees do not intersect
• When a node has no subtrees, it becomes a leaf node

Core Tree Formulas

Node Count

For a tree with n nodes: n = I + L, where I represents internal nodes and L represents leaf nodes.

Edge Count

A tree with n nodes contains exactly n-1 edges.

Storage Structures for Trees

1. Parent Pointer Representation

Each node stores its parent's index or pointer. An array is used where each element represents a node and contains the index of its parent.

• Structure:

parent[i] indicates the parent of node i

• Example:

Node:      0  1  2  3  4  5
Parent:   -1  0  0  1  1  2  (-1 indicates root)

• Advantages: Simple implementation, fast parent lookup
• Disadvantages: Slow child lookup requires scanning the entire array

2. Child List Representation

Each node maintains references to all its children. This uses linked lists or arrays where each node contains a pointer to its child list.

• Structure:

children[i] represents the child list of node i

• Example:

Node:    0   1   2   3   4   5
Children: [1,2] [3,4] [5] [] [] []

• Advantages: Fast child lookup
• Disadvantages: Slow parent lookup requires additional tracking

3. Left-Child Right-Sibling Representation

When a node may have numerous children, the left-child right-sibling representation proves useful. The root points only to its first child, while that first child manages references to remaining siblings. This representation transforms trees into binary trees, with each node storing its leftmost child and right sibling.

• Structure:

Node: node
Left-Child: leftChild
Right-Sibling: rightSibling

• Example:

Original:
    node:    0
           / \
          1   2
         / \
        3   4
Transformed:
    node:    0
           /  \
          1    2
         /
        3
         \
          4

• Advantages: Enables conversion of any tree to a binary tree, leveraging binary tree traversal algorithms
• Disadvantages: Requires two pointers, increasing memory overhead

4. Adjacency List Representation

Commonly used for graphs but applicable to trees as well. Each node records its adjacent nodes (both children and parent).

• Structure:

adjList[i] represents the adjacency list of node i

• Example:

Node:     0  1  2  3  4  5
Adjacency: [1,2] [0,3,4] [0,5] [1] [1] [2]

• Advantages: Well-suited for tree and graph traversal operations
• Disadvantages: Requires additional processing to distinguish between children and parents

5. Adjacency Matrix Representation

Uses a two-dimensional array to represent connections between nodes. Typically suited for dense graphs but can apply to trees.

• Structure:

adjMatrix[i][j] indicates whether an edge exists between nodes i and j (0 or 1)

• Example:

Node:  0  1  2  3  4  5
Adjacency Matrix:
[0, 1, 1, 0, 0, 0]
[1, 0, 0, 1, 1, 0]
[1, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0]

• Advantages: Straightforward, enables constant-time edge existence checks
• Disadvantages: High memory consumption, unsuitable for sparse trees

Each storage approach presents distinct trade-offs. Selection depends on specific requirements: whether parent or child lookups occur more frequently, and whether memory constraints are a primary concern.

Basic Tree Operations Implementation

#include <stdio.h>
#include <stdlib.h>

// Tree node structure definition
typedef struct TreeNode {
    int value;
    struct TreeNode* firstChild;
    struct TreeNode* nextSibling;
} TreeNode;

// Create a new node
TreeNode* initializeNode(int value) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    if (!node) {
        printf("Memory allocation failed\n");
        return NULL;
    }
    node->value = value;
    node->firstChild = NULL;
    node->nextSibling = NULL;
    return node;
}

// Additional operations
TreeNode* addChild(TreeNode* parent, int value);
TreeNode* locateNode(TreeNode* root, int value);
void traverseTree(TreeNode* root);

Pure tree structures have limited direct applications due to the complexity of managing variable child counts. However, trees form the foundation for file systems, directory structures, and hierarchical organizational systems.

In optimized data structures, binary trees—where each node has at most two children—see significantly more use and will be covered in the next section.