A tree is a hierarchical data structure consisting of n (n≥0) nodes. When n=0, we have an empty tree. For any non-empty tree, there exists exactly one root node, and the remaining nodes are partitioned into m (m>0) disjoint finite sets T1, T2, ..., Tm, where each set itself forms a tree (called a subtree of the root).

Node Classification

Each tree node contains a data element and references to its child branches. The degree of a node equals the number of subtrees it has. Nodes with degree 0 are called leaf nodes or terminal nodes, while nodes with non-zero degree are called non-terminal nodes or branch nodes. The maximum degree among all nodes in a tree defines the tree's degree.

Node Relationships

The child of a node refers to the root of its subtree, while that node is called the child's parent. Nodes sharing the same parent are called siblings.

Additional Tree Properties

• Level: The root node occupies level 1, its children occupy level 2, and so on.
• Ordered vs Unordered Trees: If the children of each node are considered to have a left-to-right ordering that cannot be interchanged, the tree is ordered; otherwise, it is unordered.
• Forest: A collection of m (m≥0) disjoint trees.

Abstract Data Type for Trees

ADT Tree
Data
    A tree consists of a root node and multiple subtrees, all nodes share the same data type with hierarchical relationships.
Operation
    InitTree(*T): Create an empty tree T
    DestroyTree(*T): Remove tree T and release all resources
    CreateTree(*T, definition): Build tree T according to definition
    ClearTree(*T): Reset tree T to empty state if it exists
    TreeEmpty(T): Return true if T is empty, false otherwise
    TreeDepth(T): Return the depth/height of T
    Root(T): Return the root node of T
    Value(T, cur_e): Retrieve the value stored at node cur_e
    Assign(T, cur_e, value): Update the value at node cur_e to value
    Parent(T, cur_e): Return the parent of cur_e if it exists
    LeftChild(T, cur_e): Return the leftmost child of cur_e if it exists
    RightSibling(T, cur_e): Return the right sibling of cur_e if it exists
    InsertChild(*T, *p, i, c): Insert tree c as the i-th subtree of node p
    DeleteChild(*T, *p, i): Remove the i-th subtree of node p
endADT

Binary Trees

A binary tree is either an empty set or consists of a root node with two disjoint binary trees called the left subtree and right subtree.

Binary Tree Variations

Skewed Trees: When all nodes have only left children (left-skewed) or only right children (right-skewed), the structure resembles a linked list with n nodes having depth n.

Full Binary Tree: A binary tree where every non-leaf node has exactly two children and all leaf nodes are at the same level. Key characteristics include: leaves appear only at the lowest level, non-leaf nodes always have degree 2, and among trees of equal depth, full binary trees have the maximum node count and leaf count.

Complete Binary Tree: A binary tree with n nodes numbered by level-order (1 to n), where node i at position i matches the corresponding node in a full binary tree of the same depth. Properties: leaf nodes appear only in the bottom two levels, the bottom level's leaves concentrate on the left side, if a node has degree 1, it must be a left child, and among trees with the same node count, complete binary trees have minimal depth.

Fundamental Properties of Binary Trees

1. The i-th level contains at most 2i-1 nodes (i ≥ 1)
2. A binary tree of depth k contians at most 2k - 1 nodes (k ≥ 1)
3. In any binary tree, if n0 represents leaf count and n2 represents nodes with two children, then n0 = n2 + 1
4. A complete binary tree with n nodes has depth ⌊log2n⌋ + 1
5. For a complete binary tree with n nodes, indexed from 1 to n:
   • Node 1 is the root; for i > 1, its parent is ⌊i/2⌋
   • If 2i ≤ n, node i's left child is at position 2i; otherwise it has no left child
   • If 2i+1 ≤ n, node i's right child is at position 2i+1; otherwise it has no right child

Binary Tree Storage Structure

/* Binary tree node defined as a child-sibling structure */
typedef struct TreeNode {
    ElemType data;              /* Node data field */
    struct TreeNode *left;      /* Pointer to left child */
    struct TreeNode *right;     /* Pointer to right child */
} TreeNode, *BinaryTree;

Binary Tree Traversal

Traversal refers to ssytematically visiting each node exactly once following a specific order.

Preorder Traversal (Root-Left-Right)

Visit the root first, then recursively traverse the left subtree, followed by the right subtree.

/* Preorder traversal implementation */
void Preorder(BinaryTree root)
{
    if (root == NULL) return;
    
    Process(root->data);        /* Handle current node */
    Preorder(root->left);       /* Traverse left subtree */
    Preorder(root->right);      /* Traverse right subtree */
}

Inorder Traversal (Left-Root-Right)

Recursively traverse the left subtree first, visit the root, then traverse the right subtree.

/* Inorder traversal implementation */
void Inorder(BinaryTree root)
{
    if (root == NULL) return;
    
    Inorder(root->left);        /* Traverse left subtree */
    Process(root->data);       /* Handle current node */
    Inorder(root->right);       /* Traverse right subtree */
}

Postorder Traversal (Left-Right-Root)

Recursively traverse both subtrees first, then visit the root node.

/* Postorder traversal implementation */
void Postorder(BinaryTree root)
{
    if (root == NULL) return;
    
    Postorder(root->left);      /* Traverse left subtree */
    Postorder(root->right);     /* Traverse right subtree */
    Process(root->data);        /* Handle current node */
}

Level-Order Traversal

Visit nodes level by level from top to bottom, moving left to right within each level. This typically requires a queue data structure.

Constructing Binary Trees from Sequential Input

/* Build binary tree from preorder input */
/* Use '#' to represent null positions */
void BuildTree(BinaryTree *root)
{
    char input;
    scanf("%c", &input);
    
    if (input == '#') {
        *root = NULL;
    } else {
        *root = (BinaryTree)malloc(sizeof(TreeNode));
        (*root)->data = input;
        BuildTree(&((*root)->left));
        BuildTree(&((*root)->right));
    }
}