一、二叉树的基础概念

1. 非线性结构的特性

树结构（包含二叉树）属于非线性结构，区别于队列、链表等线性结构，核心特性如下：
        每个节点是一个非空集合，仅有一个前驱节点，但可拥有多个后继节点；
        无父节点的节点为根节点，非根节点有且仅有一个父节点；
        除根节点外，每个子节点可分为多个不相交的子树。

2. 二叉树的专属定义

        二叉树是特殊的树结构，核心约束为：每个节点最多含有两个子树（左子树、右子树）。

3. 关键术语

节点的度：一个节点包含的子节点个数（二叉树中节点的度最大为 2）；
树的度：树中所有节点的度的最大值；
叶节点（终端节点）：度为 0 的节点（无左右子树）；
节点的层次：从根节点开始，根为第 1 层，根的子节点为第 2 层，依次类推；
树的深度（高度）：树中节点的最大层次；
路径长度：从根节点到该节点的路径上的边数。

4. 二叉树的数学特性

第i层上最多有2^(i-1)个节点（如第 3 层最多有2^(3-1)=4个节点）；
深度为k的二叉树，最多有2^k - 1个节点（满二叉树的节点总数）。

二、二叉树的分类

1. 按节点顺序划分

        无序树（自由树）：节点的子节点无顺序关系；
        有序树：节点的子节点（左 / 右）有明确顺序，二叉树本质上是有序树（左子树、右子树不可互换）。

2. 按结构完整性划分

        满二叉树：深度为k的满二叉树，所有层的节点数都达到最大值（第i层有2^(i-1)个节点），总节点数为2^k - 1；
        完全二叉树：除最后一层外，其余层节点数均为最大值，且最后一层的节点从左到右连续排列（满二叉树是特殊的完全二叉树）；
        非完全二叉树：不满足完全二叉树结构的二叉树（最后一层节点不连续）。

3. 按功能特性划分

        平衡二叉树（AVL 树）：任意节点的左右子树的高度差不大于 1，核心目的是防止树退化成链表，保证查找效率；
        二叉搜索树（排序二叉树 / 有序二叉树）：左子树所有节点值小于根节点值，右子树所有节点值大于根节点值，用于快速排序与检索；
        哈夫曼树（最优二叉树）：带权路径长度最短的二叉树，核心用于信息编码（哈夫曼编码）；
        B 树：多叉平衡查找树（超出二叉范畴），优化读写操作，适用于数据库、文件系统等场景。

三、二叉树的存储方式

        二叉树的存储需兼顾 “节点数据” 与 “节点间的关系”，主要有两种存储方式：

1. 顺序存储

        底层实现（Python 视角）：存储节点对象的引用（地址）；
        逻辑结构（数据结构视角）：通过数组下标关联节点关系（如第i个节点的左子节点为2i，右子节点为2i+1）；
        优缺点：访问节点快，但易造成空间浪费（非完全二叉树需补空节点）。

2. 链式存储

        底层实现（Python 视角）：每个节点存储 “数据 + 左子节点引用 + 右子节点引用”；
        逻辑结构（数据结构视角）：通过指针（引用）关联父节点与子节点；
        优缺点：空间利用率高，易查找子节点 / 父节点，但需额外存储引用地址。

四、二叉树的实现（Python）

        基于链式存储方式，我们可以封装二叉树类，实现节点添加与遍历功能，核心代码结构如下：

1. 节点类定义

class Node(object):
    def __init__(self, data):
        self.data = data  # 节点数据域
        self.LeftChild = None  # 左子节点引用
        self.RightChild = None  # 右子节点引用

2. 二叉树核心类

class BinaryTree(object):
    def __init__(self, node=None):
        self.root = node  # 根节点初始化

    # 添加节点（广度优先策略，按层填充）
    def add(self, data):
        new_node = Node(data)
        if self.root is None:  # 根节点为空时，直接设为根
            self.root = new_node
            return
        queue = [self.root]  # 队列辅助找空缺位置
        while True:
            node = queue.pop(0)
            # 左子树为空则添加
            if node.LeftChild is None:
                node.LeftChild = new_node
                return
            else:
                queue.append(node.LeftChild)
            # 右子树为空则添加
            if node.RightChild is None:
                node.RightChild = new_node
                return
            else:
                queue.append(node.RightChild)

五、二叉树的遍历方法

        遍历是二叉树的核心操作，目的是按特定顺序访问所有节点，主要分为广度优先遍历和深度优先遍历两类。

1. 广度优先遍历（层序遍历）

        核心思路：按层次从根节点开始，一层一层遍历节点（先遍历第 1 层，再第 2 层，依次类推），借助队列实现。

def breadth(self):
    if self.root is None:
        return
    queue = [self.root]
    while len(queue) != 0:
        node = queue.pop(0)
        print(node.data, end=" ")  # 访问当前节点
        # 左子节点入队
        if node.LeftChild is not None:
            queue.append(node.LeftChild)
        # 右子节点入队
        if node.RightChild is not None:
            queue.append(node.RightChild)

2. 深度优先遍历

        深度优先遍历以 “先深入子树，再回溯” 为核心，分为前序、中序、后序三种方式，均基于递归实现：

        （1）前序遍历（根→左→右）

                先访问根节点，再递归遍历左子树，最后递归遍历右子树：

def preorder(self, root):
    if root is not None:
        print(root.data, end=" ")  # 访问根节点
        self.preorder(root.LeftChild)  # 遍历左子树
        self.preorder(root.RightChild)  # 遍历右子树

        （2）中序遍历（左→根→右）

                先递归遍历左子树，再访问根节点，最后递归遍历右子树（二叉搜索树的中序遍历为有序序列）：

def inorder(self, root):
    if root is not None:
        self.inorder(root.LeftChild)  # 遍历左子树
        print(root.data, end=" ")  # 访问根节点
        self.inorder(root.RightChild)  # 遍历右子树

        （3）后序遍历（左→右→根）

                先递归遍历左子树，再递归遍历右子树，最后访问根节点：

def posorder(self, root):
    if root is not None:
        self.posorder(root.LeftChild)  # 遍历左子树
        self.posorder(root.RightChild)  # 遍历右子树
        print(root.data, end=" ")  # 访问根节点

六、演示示例

if __name__ == '__main__':
    tree = BinaryTree()
    # 依次添加节点 1-10
    for i in range(1, 11):
        tree.add(i)
    
    # 广度优先遍历
    print("广度优先遍历结果：", end=" ")
    tree.breadth()  # 输出：1 2 3 4 5 6 7 8 9 10
    
    # 深度优先-前序
    print("\n前序遍历结果为：", end=" ")
    tree.preorder(tree.root)  # 输出：1 2 4 8 9 5 10 3 6 7
    
    # 深度优先-中序
    print("\n中序遍历结果为：", end=" ")
    tree.inorder(tree.root)  # 输出：8 4 9 2 10 5 1 6 3 7
    
    # 深度优先-后序
    print("\n后序遍历结果为：", end=" ")
    tree.posorder(tree.root)  # 输出：8 9 4 10 5 2 6 7 3 1