Concept of a Tree

A tree is a abstract data type (ADT) or a data structure implementing this ADT that simulates a hierarchical tree structure with a set of linked nodes. It consists of n (n ≥ 1) finite nodes organized in a hierarchical relationship. It is called a "tree" because it resembles an upside-down tree, with the root at the top and the leaves at the bottom. Key characteristics include:

• Each node can have zero or more child nodes.
• A node without a parent is called the root node.
• Every non-root node has exactly one parent node.
• Except for the root, each child node can be divided into multiple disjoint subtrees.

For example:

Tree Terminology

• Degree of a node: The number of subtrees a node has is called the degree of the node.
• Degree of the tree: The maximum degree among all nodes in a tree is the degree of the tree.
• Leaf node or terminal node: A node with degree zero.
• Parent node: If a node contains child nodes, its called the parent of those children.
• Child node: The root node of a subtree of a given node is called a child node of that node.
• Siblings: Nodes sharing the same parent are called siblings.
• Level of a node: Defined from the root, which is level 1; its children are level 2, and so on.
• Height or depth of the tree: The maximum level among all nodes.
• Cousins: Nodes whose parents are on the same level are cousins to each other.
• Ancestors of a node: All nodes on the branch from the root to that node.
• Descendants: Any node in the subtree rooted at a given node is a descendant of that node.
• Forest: A set of m (m ≥ 0) disjoint trees is called a forest.

Types of Trees

• Unordered tree: A tree where there is no order relationship among the child nodes of any node; also called a free tree.
• Ordered tree: A tree where the child nodes of each node have a specific order.
  • Binary tree: Each node has at most two subtrees.
    • Complete binary tree: For a binary tree of depth d (d > 1), all levels except possibly level d are completely filled, and all nodes on level d are as far left as possible. A full binary tree is a special complete binary tree where every node has either 0 or 2 children and all leaves are at the deepest level.
    • Balanced binary tree (AVL tree): A binary tree where the height difference between the left and right subtrees of any node is at most 1.
    • Binary search tree (ordered or sorted binary tree): A binary tree where for each node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater.
  • Huffman tree (used for data encoding): A binary tree with the minimum weighted path length, also known as an optimal binary tree.
  • B-tree: A self-balancing tree data structure optimized for read and write operations, keeping data sorted and allowing more than two children per node.

Storage and Representation of Trees

Sequential storage: Data structures are stored in fixed-size arrays. Although it has some advantages in traversal speed, it occupies more space and is not mainstream for binary trees. Binary trees are typically stored using linked structures.

Linked storage:

Since the number of nodes is often unpredictable, common tree representations are converted to binary trees for processing, with a maximum of two children per node.

Common Application Scenarios of Trees

1. Parsers for XML, HTML, etc., inevitably use trees.
2. Routing protocols use tree algorithms.
3. MySQL database indexes.
4. Directory structure of file systems.
5. Many classic AI algorithms are essentially tree searches; moreover, the decision tree in machine learning is also a tree structure.

Binary Tree

Basic Concept of Binary Tree

A binary tree is a tree structure in which each node has at most two subtrees, usually referred to as the left subtree and the right subtree.

Properties (Characteristics) of Binary Trees

Property 1: The maximum number of nodes on level i of a binary tree is 2(i-1) (i > 0).
Property 2: A binary tree of depth k has at most 2k - 1 nodes (k > 0).
Property 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.
Property 4: The depth of a complete binary tree with n nodes is ⌊log2(n+1)⌋.
Property 5: In a complete binary tree, if nodes are numbered from top to bottom and left to right starting from 1, then for a node numbered i, its left child is numbered 2i, its right child is numbered 2i+1, and its parent is numbered ⌊i/2⌋ (except when i=1, the root).

(1) Complete binary tree — If a binary tree has height h, all levels except possibly level h are completely filled, and on level h the leaf nodes are packed as far left as possible.

(2) Full binary tree — A binary tree in which every node other than the leaves has two children, and all leaves are at the deepest level.

Node Representation and Tree Creation

By defining a TreeNode class with three attributes: the value itself, a left child reference, and a right child reference.

def insert(self, value):
    """Insert a node using level-order (breadth-first) placement."""
    node = TreeNode(value)
    if self.root is None:
        self.root = node
    else:
        queue = [self.root]
        while queue:
            current = queue.pop(0)
            if current.left is None:
                current.left = node
                return
            elif current.right is None:
                current.right = node
                return
            else:
                queue.append(current.left)
                queue.append(current.right)

</div>Binary Tree Traversals
======================

Traversing a tree is an important operation that involves visiting every node exactly once. The two main traversal patterns are depth-first traversal and breadth-first traversal. Depth-first is often implemented with recursion (or a stack), while breadth-first typically uses a queue.

Depth-First Traversal
---------------------

For a binary tree, depth-first search (DFS) traverses nodes along the depth, exploring as far as possible along each branch. There are three common methods that differ in the order nodes are visited: preorder, inorder, and postorder.

- Preorder traversal: Visit the root node first, then recursively traverse the left subtree, and finally recursively traverse the right subtree.
    
    Root → Left → Right

<div>```
def pre_order(self, node):
    """Recursive preorder traversal."""
    if node is None:
        return
    print(node.value, end=' ')
    self.pre_order(node.left)
    self.pre_order(node.right)

Left → Root → Right

Left → Right → Root

Starting from the root, traverse the entire tree level by level from top to bottom and left to right.

def level_order(self): """Level-order traversal using a queue.""" if self.root is None: return q = deque([self.root]) while q: cur = q.popleft() print(cur.value, end=' ') if cur.left is not None: q.append(cur.left) if cur.right is not None: q.append(cur.right)

</div>![](https://images2017.cnblogs.com/blog/1256425/201712/1256425-20171214184115935-1615657334.png)

Complete example:

<div>```
class TreeNode:
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

class BinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        node = TreeNode(value)
        if self.root is None:
            self.root = node
        else:
            queue = [self.root]
            while queue:
                current = queue.pop(0)
                if current.left is None:
                    current.left = node
                    return
                if current.right is None:
                    current.right = node
                    return
                queue.append(current.left)
                queue.append(current.right)

    # Level-order (breadth-first) traversal: e.g., 0 1 2 3 4 5 6 7 8 9
    def level_order(self):
        if self.root is None:
            return
        from collections import deque
        q = deque([self.root])
        while q:
            cur = q.popleft()
            print(cur.value, end=" ")
            if cur.left is not None:
                q.append(cur.left)
            if cur.right is not None:
                q.append(cur.right)

    def depth_first_demo(self):
        """Helper to start postorder traversal from root."""
        self.post_order(self.root)

    # Preorder:  0 1 3 7 8 4 9 2 5 6
    def pre_order(self, node):
        if node is None:
            return
        print(node.value, end=" ")
        self.pre_order(node.left)
        self.pre_order(node.right)

    # Inorder:   7 3 8 1 9 4 0 5 2 6
    def in_order(self, node):
        if node is None:
            return
        self.in_order(node.left)
        print(node.value, end=" ")
        self.in_order(node.right)

    # Postorder: 7 8 3 9 4 1 5 6 2 0
    def post_order(self, node):
        if node is None:
            return
        self.post_order(node.left)
        self.post_order(node.right)
        print(node.value, end=" ")

if __name__ == '__main__':
    tree = BinaryTree()
    for i in range(10):
        tree.insert(i)
    tree.depth_first_demo()   # postorder
    # tree.level_order()      # uncomment for level-order