1.1 Basic Concepts

A tree is a non-linear data structure consisting of a finite set of nodes (n ≥ 0) that form a hierarchical relationship. It's called a tree because it resembles an inverted tree with the root at the top and leaves at the bottom. Trees have the following characteristics:

• There is a special node called the root node, which has no parent node
• Except for the root node, the remaining nodes are divided into M (M > 0) disjoint sets T1, T2, ..., Tm, where each set Ti (1 ≤ i ≤ m) is itself a tree-like subtree. Each subtree's root node has exactly one parent and can have zero or more children
• Trees are recursively defined

Note: In tree structures, subtrees must not overlap; otherwise, it's not a valid tree structure.

Node Degree: The number of subtrees a node contains is called its degree.

Tree Degree: The maximum degree among all nodes in a tree is called the degree of the tree.

Leaf Nodes: Nodes with degree 0 are called leaf nodes.

Parent Node: If a node has child nodes, it is called the parent of its child nodes.

Child Node: The root node of a subtree is called a child node of its parent.

Root Node: The node without a parent in a tree.

Node Level: Starting from the root as level 1, its children are at level 2, and so on.

Tree Height/Depth: The maximum level of any node in the tree.

2. Binary Trees

2.1 Definition

A binary tree is a finite set of nodes that is either:

1. Empty, or
2. Consists of a root node plus two binary trees called left and right subtrees

From this definition, we can observe:

• No node in a binary tree can have a degree greater than 2
• The subtrees of a binary tree are distinguished as left and right, and their order cannot be reversed, making binary trees ordered trees

Note: Any binary tree is composed of the following cases combined:

2.2 Special Types of Binary Trees

1. Full Binary Tree: A binary tree where every level has the maximum number of nodes. If a binary tree has K levels and 2^K - 1 nodes, it is a full binary tree.
2. Complete Binary Tree: A highly efficient data structure derived from full binary trees. For a binary tree with depth K and n nodes, it is a complete binary tree if and only if each node corresponds to the nodes numbered from 0 to n-1 in a full binary tree of depth K. Note that a full binary tree is a special case of a complete binary tree.

2.3 Properties of Binary Trees

1. If the root node is at level 1, the maximum number of nodes at level i in a non-empty binary tree is 2^(i-1) (i > 0)
2. If a binary tree with only the root node has depth 1, the maximum number of nodes in a binary tree with depth K is 2^K - 1 (K ≥ 0)
3. For any binary tree, if the number of leaf nodes is n0 and the number of nodes with degree 2 is n2, then n0 = n2 + 1
4. The depth k of a complete binary tree with n nodes is ⌈log₂(n+1)⌉
5. For a complete binary tree with n nodes, if all nodes are numbered from 0 in top-to-bottom, left-to-right order, then for a node with index i:
   • If i > 0, the parent index is ⌊(i-1)/2⌋; if i = 0, it's the root node with no parent
   • If 2i + 1 < n, the left child index is 2i + 1; otherwise, there's no left child
   • If 2i + 2 < n, the right child index is 2i + 2; otherwise, there's no right child

2.4 Binary Tree Storage

Binary trees can be stored using sequential storage (arrays) or linked storage (similar to linked lists). Sequential storage will be discussed in the next section.

The linked storage of binary trees connects nodes through references. Common representation methods include binary and ternary representasion:

// Child representation
class TreeNode {
    int data; // Data field
    TreeNode left; // Reference to left child, representing the entire left subtree
    TreeNode right; // Reference to right child, representing the entire right subtree
}

// Child-parent representation
class TreeNode {
    int data; // Data field
    TreeNode left; // Reference to left child
    TreeNode right; // Reference to right child
    TreeNode parent; // Reference to parent node
}

2.5 Basic Binary Tree Operations

2.5.1 Preliminary Notes

Before learning basic binary tree operations, we need to create a binary tree. Since you're still becoming familiar with the binary tree structure, we'll manually create a simple binary tree to quickly get into the operations. Once you understand the structure better, we can explore more sophisticated creation methods.

public class BinaryTree {
    public static class Node {
        Node left;
        Node right;
        int value;
        
        Node(int value) {
            this.value = value;
        }
    }
    
    private Node root;
    
    public void buildBinaryTree() {
        Node nodeA = new Node(1);
        Node nodeB = new Node(2);
        Node nodeC = new Node(3);
        Node nodeD = new Node(4);
        Node nodeE = new Node(5);
        Node nodeF = new Node(6);
        
        root = nodeA;
        nodeA.left = nodeB;
        nodeB.left = nodeC;
        nodeA.right = nodeD;
        nodeD.left = nodeE;
        nodeE.right = nodeF;
    }
}

2.5.2 Binary Tree Traversal

Learning binary tree structure begins with traversal. Traversal means visiting each node in the tree exactly once along a specific path. The operation performed on a node depends on the application (e.g., printing the node value, incrementing the value). Traversal is one of the most important operations on binary trees and forms the basis for other operations.

NLR: Preorder Traversal — Visit the root node, then the left subtree, then the right subtree.

LNR: Inorder Traversal — Visit the left subtree, then the root node, then the right subtree.

LRN: Postorder Traversal — Visit the left subtree, then the right subtree, then the root node.

void preorderTraversal(Node root) {
    if (root == null) {
        return;
    }
    System.out.print(root.value + " ");
    preorderTraversal(root.left);
    preorderTraversal(root.right);
}

void inorderTraversal(Node root) {
    if (root == null) {
        return;
    }
    inorderTraversal(root.left);
    System.out.print(root.value + " ");
    inorderTraversal(root.right);
}

void postorderTraversal(Node root) {
    if (root == null) {
        return;
    }
    postorderTraversal(root.left);
    postorderTraversal(root.right);
    System.out.print(root.value + " ");
}

Level Order Traversal

In addition to preorder, inorder, and potsorder traversals, binary trees can also be traversed level by level. Starting from the root node at level 1, level order traversal visits nodes from left to right at each level, moving from top to bottom through the tree.

2.5.3 Basic Binary Tree Operations

public class BinaryTreeOperations {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;
        
        public TreeNode(char val) {
            this.val = val;
        }
    }
    
    private int count = 0;
    
    public TreeNode buildTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        D.left = H;
        
        return A;
    }
    
    // Preorder traversal
    void preorder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preorder(root.left);
        preorder(root.right);
    }
    
    // Inorder traversal
    void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }
    
    // Postorder traversal
    void postorder(TreeNode root) {
        if (root == null) {
            return;
        }
        postorder(root.left);
        postorder(root.right);
        System.out.print(root.val + " ");
    }
    
    // Count nodes using instance variable
    int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        count++;
        countNodes(root.left);
        countNodes(root.right);
        return count;
    }
    
    // Count nodes using return values
    int countNodesRecursive(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return countNodesRecursive(root.left) + countNodesRecursive(root.right) + 1;
    }
    
    // Count leaf nodes using instance variable
    int leafCount = 0;
    
    int countLeafNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            leafCount++;
        }
        countLeafNodes(root.left);
        countLeafNodes(root.right);
        return leafCount;
    }
    
    // Count leaf nodes using return values
    int countLeafNodesRecursive(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return countLeafNodesRecursive(root.left) + countLeafNodesRecursive(root.right);
    }
    
    // Count nodes at level K
    int countNodesAtLevel(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return countNodesAtLevel(root.left, k - 1) + countNodesAtLevel(root.right, k - 1);
    }
    
    // Calculate tree height
    int treeHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = treeHeight(root.left);
        int rightHeight = treeHeight(root.right);
        return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
    }
    
    // Find node with specific value
    TreeNode findNode(TreeNode root, char value) {
        if (root == null) {
            return null;
        }
        if (root.val == value) {
            return root;
        }
        TreeNode leftResult = findNode(root.left, value);
        if (leftResult != null) {
            return leftResult;
        }
        TreeNode rightResult = findNode(root.right, value);
        if (rightResult != null) {
            return rightResult;
        }
        return null;
    }
}