数据结构-树与二叉树

发布于：2025-04-21 ⋅ 阅读:(14) ⋅ 点赞:(0)

一、树的定义与基本术语

1.1 树的定义

树（Tree）是一种非线性的数据结构，它是由 n（n ≥ 0）个有限节点组成的集合。如果 n = 0，称为空树；如果 n > 0，则：

  1. 有一个特定的节点称为根（Root）。

  2. 除根节点外，其余节点被分成 m（m ≥ 0）个互不相交的集合 T₁, T₂, ..., Tₘ，其中每个集合本身又是一棵树，称为根的子树（Subtree）。

1.2 树的基本术语

  • 节点（Node）：树中的一个独立单元。

  • 度（Degree）：一个节点的子树个数称为该节点的度。

  • 叶子节点（Leaf Node）：度为0的节点。

  • 分支节点：度不为0的节点。

  • 树的度：树中所有节点的最大度数。

  • 层次（Level）：根节点在第1层，其子节点在第2层，依次类推。

  • 树的高度（Height）：树中节点的最大层次数。

  • 森林（Forest）：m棵互不相交的树的集合。

二、二叉树

2.1 二叉树的定义

二叉树（Binary Tree）是一种特殊的树，每个节点最多有两个子树，分别称为左子树和右子树。二叉树的子树有左右之分，且不能交换。

2.2 二叉树的基本操作

二叉树的基本操作包括：

  1. 创建二叉树

  2. 遍历二叉树（前序、中序、后序、层序）

  3. 查找节点

  4. 插入节点

  5. 删除节点

2.3 二叉树的性质

  1. 性质1：二叉树的第 i 层最多有 2^(i-1) 个节点（i ≥ 1）。

  2. 性质2：深度为 k 的二叉树最多有 2^k - 1 个节点（k ≥ 1）。

  3. 性质3：对于任何一棵二叉树，如果叶子节点数为 n₀，度为2的节点数为 n₂，则 n₀ = n₂ + 1。

  4. 性质4：具有 n 个节点的完全二叉树的深度为 ⌊log₂n⌋ + 1。

  5. 性质5：如果对完全二叉树的节点按层序编号（从1开始），则对于编号为 i 的节点：

    • 如果 i = 1，则该节点是根节点。

    • 如果 i > 1，则其父节点编号为 ⌊i/2⌋。

    • 如果 2i ≤ n，则其左子节点编号为 2i；否则无左子节点。

    • 如果 2i + 1 ≤ n，则其右子节点编号为 2i + 1；否则无右子节点。

2.4 二叉树的存储结构

二叉树的存储结构主要有两种：

  1. 顺序存储：用一组连续的存储单元存储二叉树的节点，通常用于完全二叉树。

  2. 链式存储：用链表存储二叉树的节点，每个节点包含数据域和左右子树指针。

2.5 二叉树的图解

以下是一个简单的二叉树结构图解：

        A
      /   \
     B     C
    / \   /
   D   E F

三、二叉树的遍历与线索化

3.1 二叉树的遍历

遍历是指按照某种顺序访问二叉树中的每个节点，且每个节点只访问一次。常见的遍历方法有：

  1. 前序遍历：根节点 → 左子树 → 右子树

  2. 中序遍历：左子树 → 根节点 → 右子树

  3. 后序遍历：左子树 → 右子树 → 根节点

  4. 层序遍历：按层次从上到下、从左到右访问节点

3.2 遍历算法应用

遍历算法可以应用于：

  1. 复制二叉树

  2. 计算二叉树的高度

  3. 统计叶子节点的数量

3.3 基于栈的递归消除

递归遍历可以转换为基于栈的非递归遍历，以避免递归带来的栈溢出问题。

3.4 线索二叉树

线索二叉树是在二叉树的链式存储中，利用空指针域存储节点的前驱和后继信息，以提高遍历效率。

3.5 由遍历序列确定二叉树

通过前序和中序遍历序列，或者后序和中序遍历序列，可以唯一确定一棵二叉树。

3.6 遍历的图解

以下是一个二叉树的前序遍历图解：

前序遍历：A → B → D → E → C → F

四、树、森林和二叉树的关系

4.1 树的存储结构

树的存储结构主要有：

  1. 双亲表示法：每个节点存储其父节点的指针。

  2. 孩子表示法：每个节点存储其子节点的指针列表。

  3. 孩子兄弟表示法：每个节点存储第一个孩子和右兄弟的指针。

4.2 树、森林和二叉树的相互转换

  1. 树转换为二叉树：将树的每个节点的子节点链表转换为二叉树的左子树，兄弟节点转换为右子树。

  2. 森林转换为二叉树：将森林中的每棵树依次转换为二叉树，并将它们链接起来。

  3. 二叉树转换为树或森林：将二叉树的右子树转换为兄弟节点，左子树转换为子节点。

4.3 树与森林的遍历

  1. 树的遍历：前序遍历和后序遍历。

  2. 森林的遍历：前序遍历和后序遍历。

五、哈夫曼树及其应用

5.1 哈夫曼树

哈夫曼树（Huffman Tree）是一种带权路径长度最小的二叉树，也称为最优二叉树。构造哈夫曼树的算法如下：

  1. 根据给定的 n 个权值 {w₁, w₂, ..., wₙ} 构成 n 棵二叉树的集合 F = {T₁, T₂, ..., Tₙ}，其中每棵二叉树只有一个带权值的根节点。

  2. 在 F 中选取两棵根节点权值最小的树作为左右子树，构造一棵新的二叉树，新树的根节点权值为左右子树根节点权值之和。

  3. 删除 F 中的这两棵树，并将新树加入 F。

  4. 重复步骤2和3，直到 F 中只剩下一棵树，这棵树就是哈夫曼树。

5.2 哈夫曼编码

哈夫曼编码是一种基于哈夫曼树的编码方法，左子树表示0，右子树表示1。每个叶子节点的编码是从根节点到该叶子节点路径上的0和1组成的字符串。

5.3 哈夫曼树的图解

以下是一个哈夫曼树的构造过程图解：

初始权值：1, 2, 3, 4

步骤1：选择1和2，构造新树，权值为3
步骤2：选择3和3，构造新树，权值为6
步骤3：选择4和6，构造新树，权值为10

最终哈夫曼树：
        10
      /   \
     4     6
        /   \
       3     3
      / \   / \
     1   2  ... ...

六、总结核心知识点

6.1 时间性能分析

数据结构 查找 插入 删除
二叉树 O(n) O(n) O(n)
平衡二叉树 O(log n) O(log n) O(log n)

6.2 空间性能分析

数据结构 空间复杂度
二叉树 O(n)

6.3 应用场景

数据结构 适用场景
二叉树 表达式求值、查找算法等
哈夫曼树 数据压缩、编码等

七、代码实现

7.1 二叉树的实现

7.1.1 C语言实现

​
#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点
typedef struct TreeNode {
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建新节点
TreeNode* createNode(char data) {
    TreeNode *newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 前序遍历
void preOrder(TreeNode *root) {
    if (root != NULL) {
        printf("%c ", root->data); // 访问根节点
        preOrder(root->left);      // 递归遍历左子树
        preOrder(root->right);     // 递归遍历右子树
    }
}

// 中序遍历
void inOrder(TreeNode *root) {
    if (root != NULL) {
        inOrder(root->left);       // 递归遍历左子树
        printf("%c ", root->data); // 访问根节点
        inOrder(root->right);      // 递归遍历右子树
    }
}

// 后序遍历
void postOrder(TreeNode *root) {
    if (root != NULL) {
        postOrder(root->left);     // 递归遍历左子树
        postOrder(root->right);    // 递归遍历右子树
        printf("%c ", root->data); // 访问根节点
    }
}

int main() {
    // 创建二叉树
    TreeNode *root = createNode('A');
    root->left = createNode('B');
    root->right = createNode('C');
    root->left->left = createNode('D');
    root->left->right = createNode('E');
    root->right->left = createNode('F');

    // 遍历二叉树
    printf("前序遍历: ");
    preOrder(root);
    printf("\n");

    printf("中序遍历: ");
    inOrder(root);
    printf("\n");

    printf("后序遍历: ");
    postOrder(root);
    printf("\n");

    return 0;
}

​

7.1.2 C++实现

​
#include <iostream>
using namespace std;

// 定义二叉树节点
struct TreeNode {
    char data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(char val) : data(val), left(nullptr), right(nullptr) {}
};

// 前序遍历
void preOrder(TreeNode *root) {
    if (root != nullptr) {
        cout << root->data << " "; // 访问根节点
        preOrder(root->left);      // 递归遍历左子树
        preOrder(root->right);     // 递归遍历右子树
    }
}

// 中序遍历
void inOrder(TreeNode *root) {
    if (root != nullptr) {
        inOrder(root->left);       // 递归遍历左子树
        cout << root->data << " "; // 访问根节点
        inOrder(root->right);      // 递归遍历右子树
    }
}

// 后序遍历
void postOrder(TreeNode *root) {
    if (root != nullptr) {
        postOrder(root->left);     // 递归遍历左子树
        postOrder(root->right);    // 递归遍历右子树
        cout << root->data << " "; // 访问根节点
    }
}

int main() {
    // 创建二叉树
    TreeNode *root = new TreeNode('A');
    root->left = new TreeNode('B');
    root->right = new TreeNode('C');
    root->left->left = new TreeNode('D');
    root->left->right = new TreeNode('E');
    root->right->left = new TreeNode('F');

    // 遍历二叉树
    cout << "前序遍历: ";
    preOrder(root);
    cout << endl;

    cout << "中序遍历: ";
    inOrder(root);
    cout << endl;

    cout << "后序遍历: ";
    postOrder(root);
    cout << endl;

    return 0;
}

​

7.1.3 Java实现

​
public class BinaryTree {
    // 定义二叉树节点
    static class TreeNode {
        char data;
        TreeNode left;
        TreeNode right;
        TreeNode(char data) {
            this.data = data;
            left = null;
            right = null;
        }
    }

    // 前序遍历
    void preOrder(TreeNode root) {
        if (root != null) {
            System.out.print(root.data + " "); // 访问根节点
            preOrder(root.left);              // 递归遍历左子树
            preOrder(root.right);             // 递归遍历右子树
        }
    }

    // 中序遍历
    void inOrder(TreeNode root) {
        if (root != null) {
            inOrder(root.left);               // 递归遍历左子树
            System.out.print(root.data + " "); // 访问根节点
            inOrder(root.right);              // 递归遍历右子树
        }
    }

    // 后序遍历
    void postOrder(TreeNode root) {
        if (root != null) {
            postOrder(root.left);             // 递归遍历左子树
            postOrder(root.right);            // 递归遍历右子树
            System.out.print(root.data + " "); // 访问根节点
        }
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        TreeNode root = new TreeNode('A');
        root.left = new TreeNode('B');
        root.right = new TreeNode('C');
        root.left.left = new TreeNode('D');
        root.left.right = new TreeNode('E');
        root.right.left = new TreeNode('F');

        System.out.print("前序遍历: ");
        tree.preOrder(root);
        System.out.println();

        System.out.print("中序遍历: ");
        tree.inOrder(root);
        System.out.println();

        System.out.print("后序遍历: ");
        tree.postOrder(root);
        System.out.println();
    }
}

​

7.1.4 Python实现

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

# 前序遍历
def pre_order(root):
    if root is not None:
        print(root.data, end=" ")  # 访问根节点
        pre_order(root.left)       # 递归遍历左子树
        pre_order(root.right)      # 递归遍历右子树

# 中序遍历
def in_order(root):
    if root is not None:
        in_order(root.left)        # 递归遍历左子树
        print(root.data, end=" ")  # 访问根节点
        in_order(root.right)       # 递归遍历右子树

# 后序遍历
def post_order(root):
    if root is not None:
        post_order(root.left)      # 递归遍历左子树
        post_order(root.right)     # 递归遍历右子树
        print(root.data, end=" ")  # 访问根节点

if __name__ == "__main__":
    # 创建二叉树
    root = TreeNode('A')
    root.left = TreeNode('B')
    root.right = TreeNode('C')
    root.left.left = TreeNode('D')
    root.left.right = TreeNode('E')
    root.right.left = TreeNode('F')

    # 遍历二叉树
    print("前序遍历:", end=" ")
    pre_order(root)
    print()

    print("中序遍历:", end=" ")
    in_order(root)
    print()

    print("后序遍历:", end=" ")
    post_order(root)
    print()

​

八、总结

通过以上内容，我们详细讲解了树和二叉树的定义、性质、存储结构、遍历方法以及哈夫曼树的应用。希望这些内容能够帮助你更好地理解和使用树和二叉树这种数据结构。每种数据结构的代码实现都附有详细的注释，便于读者理解和动手操作。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布