数据结构与算法分析：树与哈希表（一）-EW帮帮网

遇到的问题，都有解决方案，希望我的博客能为你提供一点帮助。

一、概述

背景：链表处理大量数据时，线性访问耗时多。二叉查找树多数操作平均运行时间为 O (log N)，相对于链表树更加高效。

1.预备知识

1.1. 树的定义与基本概念

树（Tree）: 非线性数据结构，由节点（Node）和边（Edge）组成，满足以下条件：
- 存在唯一根节点（Root），无父节点。
- 除根节点外，每个节点有且仅有一个父节点。
- 从根到任意节点有唯一路径，无环路。
关键术语：
- 根节点（Root）：树的顶端节点，没有父节点。
- 子节点（Child）：一个节点的直接下级节点。
- 父节点（Parent）：一个节点的直接上级节点。
- 叶子节点（Leaf）：没有子节点的节点。
- 内部节点（Internal Node）：至少有一个子节点的节点。
- 子树（Subtree）：一个节点及其所有后代节点构成的树。
- 边（Edge）：连接两个节点的线段。
- 路径（Path）：从某一节点到其子孙节点的连续边序列。
- 深度（Depth）：根节点到该节点的路径长度（根节点深度为0）。
- 高度（Height）：节点到最深叶子节点的路径长度（叶子节点高度为0）。
- 树的深度=树的高度
- 节点所在的层（level）：从顶至底递增，根节点所在层为 1 。
- 节点的度（degree）：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def plot_tree(root):
    """可视化二叉树"""
    import matplotlib.pyplot as plt
    from matplotlib.patches import Circle
    
    fig, ax = plt.subplots(figsize=(10, 8))
    ax.set_aspect('equal')
    ax.axis('off')
    
    def get_height(node):
        if not node:
            return 0
        return 1 + max(get_height(node.left), get_height(node.right))
    
    tree_height = get_height(root)
    
    def plot_node(node, x, y, dx):
        if not node:
            return
        
        # 绘制当前节点
        circle = Circle((x, y), 0.3, fill=True, color='lightblue')
        ax.add_patch(circle)
        ax.text(x, y, str(node.val), ha='center', va='center', fontsize=12)
        
        # 绘制左子树
        if node.left:
            new_x = x - dx
            new_y = y - 1
            ax.plot([x, new_x], [y-0.3, new_y+0.3], 'k-', lw=1.5)
            plot_node(node.left, new_x, new_y, dx/2)
        
        # 绘制右子树
        if node.right:
            new_x = x + dx
            new_y = y - 1
            ax.plot([x, new_x], [y-0.3, new_y+0.3], 'k-', lw=1.5)
            plot_node(node.right, new_x, new_y, dx/2)
    
    plot_node(root, 0, tree_height-1, 2**(tree_height-2))
    plt.xlim(-2**(tree_height-1), 2**(tree_height-1))
    plt.ylim(-1, tree_height)
    plt.show()

# 测试用例
if __name__ == "__main__":
    # 构建一个示例树
    #       1
    #      / \
    #     2   3
    #    / \
    #   4   5
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    
    plot_tree(root)

1.2树的递归定义

递归定义是一种通过自我引用来描述数据结构或算法的方式。对于树这种分层结构，递归定义尤其自然，因为每个子树本身也是一棵树。递归定义包含两个关键部分：

基线条件（Base Case）：定义最简单、不可再分的情况（通常是空树或叶子节点）。
递归条件（Recursive Case）：通过组合更小的树来定义更大的树。

通用树的递归定义

一个树可以是：

空树（基线条件），或者一个根节点，连接若干个子树（递归条件），每个子树本身也是树。

数学表达：

T=∅或T=(v,{T1,T2,...,Tn})

v：根节点的值
{T1,T2,...,Tn}：子树集合

动态演示建树过程：

import matplotlib.pyplot as plt
from matplotlib.patches import Circle
import time

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree_recursively(values, index=0):
    """
    递归构建二叉树
    :param values: 节点值列表
    :param index: 当前节点索引
    :return: 构建好的树节点
    """
    if index >= len(values) or values[index] is None:
        return None
    
    node = TreeNode(values[index])
    
    # 递归构建左子树
    node.left = build_tree_recursively(values, 2*index+1)
    
    # 递归构建右子树
    node.right = build_tree_recursively(values, 2*index+2)
    
    return node

def visualize_recursive_build(root, values):
    """
    可视化递归构建过程
    :param root: 树的根节点
    :param values: 节点值列表
    """
    fig, ax = plt.subplots(figsize=(12, 8))
    ax.set_aspect('equal')
    ax.axis('off')
    
    # 计算树的高度
    def get_height(node):
        if not node:
            return 0
        return 1 + max(get_height(node.left), get_height(node.right))
    
    tree_height = get_height(root)
    
    # 存储节点高度信息
    node_heights = {}
    
    def calc_heights(node):
        if not node:
            return 0
        h = 1 + max(calc_heights(node.left), calc_heights(node.right))
        node_heights[id(node)] = h - 1
        return h
    
    calc_heights(root)
    
    # 递归构建并可视化
    def recursive_build_visualize(node, x, y, dx, depth=0, is_new=False):
        if not node:
            return
        
        # 绘制当前节点
        color = 'red' if is_new else 'lightblue'
        circle = Circle((x, y), 0.35, fill=True, color=color, alpha=0.8)
        ax.add_patch(circle)
        
        # 显示节点信息
        node_info = f"值: {node.val}\n深度: {depth}\n高度: {node_heights.get(id(node), 0)}"
        ax.text(x, y, node_info, 
                ha='center', va='center', 
                fontsize=10, bbox=dict(facecolor='white', alpha=0.7))
        
        plt.pause(0.5)  # 暂停0.5秒展示当前步骤
        
        # 递归构建左子树
        if 2*values.index(node.val)+1 < len(values) and values[2*values.index(node.val)+1] is not None:
            new_x = x - dx
            new_y = y - 1.5
            ax.plot([x, new_x], [y-0.35, new_y+0.35], 'b-', lw=1.5, alpha=0.6)
            plt.pause(0.3)  # 展示连接线
            
            left_val = values[2*values.index(node.val)+1]
            left_node = TreeNode(left_val)
            node.left = left_node
            recursive_build_visualize(left_node, new_x, new_y, dx/2, depth+1, True)
        
        # 递归构建右子树
        if 2*values.index(node.val)+2 < len(values) and values[2*values.index(node.val)+2] is not None:
            new_x = x + dx
            new_y = y - 1.5
            ax.plot([x, new_x], [y-0.35, new_y+0.35], 'r-', lw=1.5, alpha=0.6)
            plt.pause(0.3)  # 展示连接线
            
            right_val = values[2*values.index(node.val)+2]
            right_node = TreeNode(right_val)
            node.right = right_node
            recursive_build_visualize(right_node, new_x, new_y, dx/2, depth+1, True)
    
    # 开始可视化构建过程
    plt.title("递归构建二叉树过程 (红色:新添加节点)", pad=20)
    recursive_build_visualize(root, 0, tree_height-1, 2**(tree_height-2))
    
    plt.xlim(-2**(tree_height-1), 2**(tree_height-1))
    plt.ylim(-tree_height, tree_height)
    
    # 设置中文字体
    plt.rcParams['font.sans-serif'] = ['SimHei']  # 使用黑体显示中文
    plt.rcParams['axes.unicode_minus'] = False  # 解决负号显示问题
    plt.show()

# 示例使用
if __name__ == "__main__":
    # 定义节点值列表 (None表示空节点)
    values = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    
    # 构建完整的树结构
    root = build_tree_recursively(values)
    
    # 可视化递归构建过程
    visualize_recursive_build(root, values)

演示视频可以在我的视频资源里看：20250330_101822-CSDN直播

2、二叉树（Binary Tree）

2.1. 定义

每个节点最多有两个子节点（左子节点和右子节点）。

结构示例：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

二叉树的递归定义

一个二叉树可以是：

空树（基线条件），或者一个根节点，连接一个左子树和一个右子树（递归条件），每个子树本身也是二叉树。

数学表达：

$T=\varnothing$ 或 $T=(V,T_{left},T_{right})$

2.2. 特殊二叉树类型

(1) 满二叉树（Full Binary Tree）

每个节点要么是叶子节点，要么恰好有两个子节点。

示例：

       1
    /     \
   2       3
  / \     / \
 4   5   6   7

(2) 完全二叉树（Complete Binary Tree）

除最后一层外，其他层节点全满，且最后一层节点尽量靠左排列。

示例：

(3) 二叉搜索树（BST, Binary Search Tree）

左子树所有节点值 < 根节点值 < 右子树所有节点值。
作用：支持高效查找、插入、删除（时间复杂度 O(log n)）。

示例：

      4
    /   \
   2     6
  / \   / \
 1   3 5   7

2.3树的遍历法

       1
    /     \
   2       3
  / \     / \
 4   5   6   7

2.3.1. 深度优先遍历（DFS）

前序遍历（Preorder）：根 → 左 → 右
示例：1 → 2 → 4 → 5 → 3 → 6 → 7

def preorder(root):
    if not root: return []
    return [root.val] + preorder(root.left) + preorder(root.right)

中序遍历（Inorder）：左 → 根 → 右
BST 中序遍历结果有序。
示例：4 → 2 → 5 → 1 → 6 → 3 → 7
```
def inorder(root):
    if not root: return []
    return inorder(root.left) + [root.val] + inorder(root.right)
```

后序遍历（Postorder）：左 → 右 → 根
示例：4 → 5 → 2 → 6 → 7 → 3 → 1

def postorder(root):
    if not root: return []
    return postorder(root.left) + postorder(root.right) + [root.val]

2.3.2. 广度优先遍历（BFS / 层序遍历）

按层次逐层访问节点。

示例：1 → 2 → 3 → 4 → 5 → 6 → 7

from collections import deque
def level_order(root):
    if not root: return []
    queue = deque([root])
    res = []
    while queue:
        node = queue.popleft()
        res.append(node.val)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    return res

完整代码示例：

class TreeNode:
    """
    二叉树节点类
    
    属性:
        val: 节点值
        left: 左子节点
        right: 右子节点
    """
    def __init__(self, val=0, left=None, right=None):
        """
        初始化二叉树节点
        
        参数:
            val: 节点值，默认为0
            left: 左子节点，默认为None
            right: 右子节点，默认为None
        """
        self.val = val
        self.left = left
        self.right = right

def preorder(root):
    """
    前序遍历二叉树
    
    参数:
        root: 二叉树根节点
        
    返回:
        包含前序遍历结果的列表
    """
    if not root: return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def inorder(root):
    """
    中序遍历二叉树
    
    参数:
        root: 二叉树根节点
        
    返回:
        包含中序遍历结果的列表
    """
    if not root: return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def postorder(root):
    """
    后序遍历二叉树
    
    参数:
        root: 二叉树根节点
        
    返回:
        包含后序遍历结果的列表
    """
    if not root: return []
    return postorder(root.left) + postorder(root.right) + [root.val]

from collections import deque
def level_order(root):
    """
    层序遍历二叉树
    
    参数:
        root: 二叉树根节点
        
    返回:
        包含层序遍历结果的列表
    """
    if not root: return []
    queue = deque([root])
    res = []
    while queue:
        node = queue.popleft()
        res.append(node.val)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    return res

# 示例用法
if __name__ == "__main__":
    # 构建示例树
    #       1
    #      / \
    #     2   3
    #    / \ / \
    #   4  5 6 7
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right.left = TreeNode(6)
    root.right.right = TreeNode(7)

    print("前序遍历:", preorder(root))
    print("中序遍历:", inorder(root))
    print("后序遍历:", postorder(root))
    print("层序遍历:", level_order(root))

C++简易版

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 二叉树节点结构体
struct TreeNode {
    int val;         // 节点存储的值
    TreeNode* left;  // 指向左子节点的指针
    TreeNode* right; // 指向右子节点的指针
    // 构造函数
    // 参数x: 节点存储的整数值
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 前序遍历二叉树（根-左-右）
// 参数root: 二叉树的根节点
// 返回值: 包含前序遍历结果的整数向量
vector<int> preorder(TreeNode* root) {
    if (!root) return {}; // 空树返回空向量
    vector<int> result;
    result.push_back(root->val); // 访问根节点
    vector<int> left = preorder(root->left); // 递归遍历左子树
    vector<int> right = preorder(root->right); // 递归遍历右子树
    result.insert(result.end(), left.begin(), left.end()); // 合并左子树结果
    result.insert(result.end(), right.begin(), right.end()); // 合并右子树结果
    return result;
}

// 中序遍历二叉树（左-根-右）
// 参数root: 二叉树的根节点
// 返回值: 包含中序遍历结果的整数向量
vector<int> inorder(TreeNode* root) {
    if (!root) return {}; // 空树返回空向量
    vector<int> left = inorder(root->left); // 递归遍历左子树
    vector<int> result;
    result.push_back(root->val); // 访问根节点
    vector<int> right = inorder(root->right); // 递归遍历右子树
    left.insert(left.end(), result.begin(), result.end()); // 合并根节点结果
    left.insert(left.end(), right.begin(), right.end()); // 合并右子树结果
    return left;
}

// 后序遍历二叉树（左-右-根）
// 参数root: 二叉树的根节点
// 返回值: 包含后序遍历结果的整数向量
vector<int> postorder(TreeNode* root) {
    if (!root) return {}; // 空树返回空向量
    vector<int> left = postorder(root->left); // 递归遍历左子树
    vector<int> right = postorder(root->right); // 递归遍历右子树
    right.push_back(root->val); // 访问根节点
    left.insert(left.end(), right.begin(), right.end()); // 合并右子树和根节点结果
    return left;
}

// 层序遍历二叉树（广度优先）
// 参数root: 二叉树的根节点
// 返回值: 包含层序遍历结果的整数向量
vector<int> levelOrder(TreeNode* root) {
    if (!root) return {}; // 空树返回空向量
    queue<TreeNode*> q; // 使用队列辅助遍历
    q.push(root); // 根节点入队
    vector<int> result;
    while (!q.empty()) {
        TreeNode* node = q.front(); // 取出队首节点
        q.pop();
        result.push_back(node->val); // 访问当前节点
        if (node->left) q.push(node->left); // 左子节点入队
        if (node->right) q.push(node->right); // 右子节点入队
    }
    return result;
}

int main() {
    // 构建示例树
    //       1
    //      / \
    //     2   3
    //    / \ / \
    //   4  5 6 7
    // 这是一个完全二叉树，用于测试各种遍历方法
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    cout << "前序遍历: ";
    for (int num : preorder(root)) {
        cout << num << " ";
    }
    cout << endl;

    cout << "中序遍历: ";
    for (int num : inorder(root)) {
        cout << num << " ";
    }
    cout << endl;

    cout << "后序遍历: ";
    for (int num : postorder(root)) {
        cout << num << " ";
    }
    cout << endl;

    cout << "层序遍历: ";
    for (int num : levelOrder(root)) {
        cout << num << " ";
    }
    cout << endl;

    // 释放内存
    delete root->right->right;
    delete root->right->left;
    delete root->left->right;
    delete root->left->left;
    delete root->right;
    delete root->left;
    delete root;

    return 0;
}

3.二叉树的数组表示

核心思想：用连续的内存空间（数组）存储二叉树节点，通过索引计算确定节点间的父子关系。

适用场景

完全二叉树：数组表示最紧凑，无空间浪费。
非完全二叉树：可能存在空间浪费，需用特殊值标记空节点。

3.1、数组存储规则

3.1.1. 索引分配规则（适用于完美二叉树）

假设数组从 索引0 开始存储：

根节点：索引为 0。
父节点索引 i：
- 左子节点索引：2*i + 1
- 右子节点索引：2*i + 2
子节点索引 j：
- 父节点索引：⌊(j-1)/2⌋（向下取整）

2. 空节点标记（非完美二叉树）

用特定值（如 None、null 或特殊符号）表示缺失的节点。

3.1.2、示例分析

示例1：完全二叉树的数组表示

树结构：

       1
    /     \
   2       3
  / \     / \
 4   5   6   7

数组表示：
```
[1, 2, 3, 4, 5, 6, 7]
```
- 索引关系：
  - 根节点 1 的索引为 0。
  - 左子节点 2 的索引为 1（2*0+1）。
  - 右子节点 3 的索引为 2（2*0+2）。
  - 节点 4（索引 3）的父节点为 1（⌊(3-1)/2⌋=1）。

示例2：非完全二叉树的数组表示

树结构：

数组表示（用 null 填充空缺）：
```
[1, 2, 3, null, 5, null, 7]
```
- 说明：
  - 索引 3（左子节点位置）为 null，表示节点 2 无左子节点。
  - 索引 5（右子节点位置）为 null，表示节点 3 无左子节点。

3.2、数组表示 vs. 链式表示

维度	数组表示	链式表示
空间效率	完全二叉树高效；非完全二叉树可能浪费空间	灵活，无空间浪费
访问速度	直接通过索引计算，速度快	需遍历指针，速度较慢
插入/删除	需要移动元素，效率低	修改指针即可，效率高
适用场景	完全二叉树、堆	任意二叉树（尤其是非完全树）

3.3、代码实现

3.3.1. 根据数组构建二叉树（链式结构）

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(arr, i=0):
    if i >= len(arr) or arr[i] is None:
        return None
    root = TreeNode(arr[i])
    root.left = build_tree(arr, 2*i + 1)
    root.right = build_tree(arr, 2*i + 2)
    return root

# 示例：构建示例2的非完全二叉树
arr = [1, 2, 3, None, 5, None, 7]
root = build_tree(arr)

C++版

#include <vector>
#include <queue>
#include <iostream>
using namespace std;

/**
 * @brief 二叉树节点结构
 * @param val 存储的数据元素
 * @param left 指向左子节点的指针
 * @param right 指向右子节点的指针
 *  */
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x = 0, TreeNode* l = nullptr, TreeNode* r = nullptr) : val(x), left(l), right(r) {}
};

/**
 * @brief 根据数组构建二叉树
 * @param arr 包含二叉树节点值的数组，-1表示空节点
 * @param i 当前处理的数组索引，默认为0(根节点)
 * @return TreeNode* 构建完成的二叉树根节点
 * @note 使用完毕后需要调用deleteTree释放内存
 */
TreeNode* buildTree(const vector<int>& arr, int i = 0) {
    // 参数校验
    if (arr.empty()) {
        return nullptr;
    }
    
    // 递归终止条件：索引越界或遇到空节点标记
    if (i < 0 || i >= arr.size() || arr[i] == -1) {
        return nullptr;
    }
    
    // 创建当前节点并递归构建左右子树
    TreeNode* root = new TreeNode(arr[i]);
    root->left = buildTree(arr, 2 * i + 1);
    root->right = buildTree(arr, 2 * i + 2);
    return root;
}

/**
 * @brief 释放二叉树内存
 * @param root 二叉树根节点
 */
void deleteTree(TreeNode* root) {
    if (!root) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

void printTree(TreeNode* root) {
    if (!root) {
        return;  // 空节点，直接返回  
    }
    queue<TreeNode*> q;  // 队列用于层次遍历    
    q.push(root);  // 根节点入队

    while (!q.empty()) {
        TreeNode* curr = q.front();
        q.pop();
        cout << curr->val << " ";  // 输出当前节点的值

        if (curr->left) {
            q.push(curr->left);  // 左子节点入队
      
        } else {}                 // 空节点，不做处理

        if (curr->right) {
            q.push(curr->right);  // 右子节点入队
        } else {}                 // 空节点，不做处理
    }   
}

/**
 * @brief 演示二叉树构建和删除
 */
int main() {
    // 示例数组表示二叉树
    vector<int> treeData = {1, 2, 3, -1, 4, 5, 6, -1, -1, 7, 8};
    
    // 构建二叉树
    TreeNode* root = buildTree(treeData);
    
    // 这里可以添加遍历或其他操作
    cout << "Tree in level order: ";
    printTree(root);
    cout << endl << "Tree deleted." << endl;
    // 释放内存
    deleteTree(root);
    
    return 0;

3.3.2. 将二叉树转为数组表示

def tree_to_array(root):
    if not root:
        return []
    queue = [root]
    res = []
    while queue:
        node = queue.pop(0)
        if node:
            res.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            res.append(None)
    # 去除末尾的 None（可选）
    while res and res[-1] is None:
        res.pop()
    return res

# 示例：将链式树转回数组
print(tree_to_array(root))  # 输出 [1, 2, 3, None, 5, None, 7]

c++版

#include <vector>
#include <queue>
#include <iostream>
#include <memory>
using namespace std;

/**
 * @brief 二叉树节点结构
 * 使用智能指针管理内存，防止内存泄漏
 */
struct TreeNode {
    int val;
    shared_ptr<TreeNode> left;
    shared_ptr<TreeNode> right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};


/**
 * @brief 将二叉树转换为数组表示（层次遍历）
 * @param root 二叉树根节点
 * @return 包含节点值的vector，空节点用-1表示
 * @note 使用智能指针避免内存泄漏
 */
vector<int> treeToArray(shared_ptr<TreeNode> root) {
    vector<int> result;
    if (!root) {
        return result;
    }
    
    queue<shared_ptr<TreeNode>> q;
    q.push(root);
    
    while (!q.empty()) {
        auto node = q.front();
        q.pop();
        
        if (node) {
            result.push_back(node->val);
            q.push(node->left);
            q.push(node->right);
        } else {
            result.push_back(-1); // 使用-1表示空节点
        }
    }
    
    // 去除末尾的-1（可选）
    while (!result.empty() && result.back() == -1) {
        result.pop_back();
    }
    
    return result;
}


int main() {
    try {
        // 构建示例二叉树
        auto root = make_shared<TreeNode>(1);
        root->left = make_shared<TreeNode>(2);
        root->right = make_shared<TreeNode>(3);
        root->left->right = make_shared<TreeNode>(5);
        root->right->right = make_shared<TreeNode>(7);
        
        // 转换为数组并打印
        vector<int> arr = treeToArray(root);
        
        cout << "层次遍历结果: ";
        for (int val : arr) {
            cout << val << " ";
        }
        cout << endl;
        
        // 输出: 1 2 3 -1 5 -1 7 
    } catch (const exception& e) {
        cerr << "错误: " << e.what() << endl;
        return 1;
    }
    
    return 0;
}

数据结构与算法分析：树与哈希表（一）

一、概述

1.预备知识

1.1. 树的定义与基本概念

1.2树的递归定义

数学表达：

2、二叉树（Binary Tree）

2.1. 定义

二叉树的递归定义

数学表达：

2.2. 特殊二叉树类型

(1) 满二叉树（Full Binary Tree）

(2) 完全二叉树（Complete Binary Tree）

(3) 二叉搜索树（BST, Binary Search Tree）

2.3树的遍历法

2.3.1. 深度优先遍历（DFS）

2.3.2. 广度优先遍历（BFS / 层序遍历）

3.二叉树的数组表示

适用场景

3.1、数组存储规则

3.1.1. 索引分配规则（适用于完美二叉树）

2. 空节点标记（非完美二叉树）

3.1.2、示例分析

示例1：完全二叉树的数组表示

示例2：非完全二叉树的数组表示

3.2、数组表示 vs. 链式表示

3.3、代码实现

3.3.1. 根据数组构建二叉树（链式结构）

3.3.2. 将二叉树转为数组表示

网站公告

今日签到

热门文章

最新发布

数据结构与算法分析：树与哈希表（一）

一、概述

1.预备知识

1.1. 树的定义与基本概念

1.2树的递归定义

​数学表达：

2、二叉树（Binary Tree）

2.1. 定义

二叉树的递归定义

​数学表达：

2.2. 特殊二叉树类型

(1) 满二叉树（Full Binary Tree）

(2) 完全二叉树（Complete Binary Tree）

(3) 二叉搜索树（BST, Binary Search Tree）

2.3树的遍历法

2.3.1. 深度优先遍历（DFS）

2.3.2. 广度优先遍历（BFS / 层序遍历）

3.二叉树的数组表示

适用场景

3.1、数组存储规则

3.1.1. 索引分配规则（适用于完美二叉树）

2. 空节点标记（非完美二叉树）

3.1.2、示例分析

示例1：完全二叉树的数组表示

示例2：非完全二叉树的数组表示

3.2、数组表示 vs. 链式表示

3.3、代码实现

3.3.1. 根据数组构建二叉树（链式结构）

3.3.2. 将二叉树转为数组表示

网站公告

今日签到

热门文章

最新发布

数学表达：

数学表达：