数据结构-树(二叉树)-第三天

结合leetcode学习c++
学习资料来源

定义

二叉树（binary tree）是一种非线性数据结构，代表“祖先”与“后代”之间的派生关系，体现了“一分为二”的分治逻辑。
与链表类似，二叉树的基本单元是节点，每个节点包含值、左子节点引用和右子节点引用。
1
2

节点定义

/* 二叉树节点结构体 */
struct TreeNode {
    int val;          // 节点值
    TreeNode *left;   // 左子节点指针
    TreeNode *right;  // 右子节点指针
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
1
2
3
4
5
6
7

每个节点都有两个引用（指针），分别指向左子节点（left-child node）和右子节点（right-child node），该节点被称为这两个子节点的父节点（parent node）。当给定一个二叉树的节点时，我们将该节点的左子节点及其以下节点形成的树称为该节点的左子树（left subtree），同理可得右子树（right subtree）。

二叉树常见术语

根节点（root node）：位于二叉树顶层的节点，没有父节点。
叶节点（leaf node）：没有子节点的节点，其两个指针均指向 None 。
边（edge）：连接两个节点的线段，即节点引用（指针）。
节点所在的层（level）：从顶至底递增，根节点所在层为 1 。
节点的度（degree）：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。
二叉树的高度（height）：从根节点到最远叶节点所经过的边的数量。
节点的深度（depth）：从根节点到该节点所经过的边的数量。
节点的高度（height）：从距离该节点最远的叶节点到该节点所经过的边的数量。

初始化

/* 初始化二叉树 */
// 初始化节点
TreeNode* n1 = new TreeNode(1);
TreeNode* n2 = new TreeNode(2);
TreeNode* n3 = new TreeNode(3);
TreeNode* n4 = new TreeNode(4);
TreeNode* n5 = new TreeNode(5);
// 构建节点之间的引用（指针）
n1->left = n2;
n1->right = n3;
n2->left = n4;
n2->right = n5;
1
2
3
4
5
6
7
8
9
10
11
12

二叉树的类型

1. 普通二叉树 (General Binary Tree):

   • 最常见的二叉树形式，其中每个节点最多有两个子节点。
   • 没有特别的结构限制。

2. 满二叉树 (Full Binary Tree):

   • 每个节点要么没有子节点，要么恰好有两个子节点。
   • 没有度为 1 的节点。
   • 也被称为严格二叉树。

3. 完全二叉树 (Complete Binary Tree):

   • 除了最后一层之外，每一层都是完全填满的。
   • 最后一层的所有节点都尽可能地集中在左边。
   • 完全二叉树可以用数组高效地表示，通常用于堆数据结构中。

4. 平衡二叉树 (Balanced Binary Tree):

   • 任何两个叶节点的深度之差不超过 1。
   • 包括 AVL 树、红黑树等，这些树保证了在插入、删除等操作后的高度平衡，从而保持良好的性能。

5. 二叉搜索树 (Binary Search Tree, BST):

   • 对于任意节点，其左子树中的所有节点的值小于该节点的值，右子树中的所有节点的值大于该节点的值。
   • 提供了高效的查找、插入和删除操作。
   • 如果树不平衡，性能可能会退化到 O(n)。

6. AVL 树 (Adelson-Velsky and Landis Tree):

   • 一种自平衡的二叉搜索树，任何节点的两个子树的高度差至多为 1。
   • 在插入或删除节点后，树会通过旋转操作来保持平衡。
   • 保证了操作的时间复杂度为 O(log n)。

7. 红黑树 (Red-Black Tree):

   • 另一种自平衡的二叉搜索树，通过节点着色和旋转操作来维持平衡。
   • 每个节点都有一个颜色属性（红色或黑色），并且满足特定的规则来保证平衡。
   • 通常用于实现关联容器，如 C++ STL 中的 std::map 和 std::set。

8. 堆 (Heap):

   • 一种特殊的完全二叉树，通常用于实现优先队列。
   • 有两种类型：最大堆和最小堆。
   • 在最大堆中，父节点的值总是大于或等于其子节点的值；而在最小堆中，父节点的值总是小于或等于其子节点的值。

9. 线索二叉树 (Threaded Binary Tree):

   • 通过对空指针进行线索化处理，使得二叉树可以像链表一样进行遍历，而不需要使用递归或栈。
   • 通常用于节省内存和提高遍历效率。

10. 哈夫曼树 (Huffman Tree):

    • 一种特殊的二叉树，用于数据压缩。
    • 树的叶子节点表示字符，非叶子节点表示字符的频率。
    • 哈夫曼编码使用最短的编码表示最频繁的字符，从而实现高效的压缩。

示例代码

下面是一个简单的二叉树节点定义和一个创建二叉搜索树的示例：

#include <iostream>
using namespace std;

// 定义二叉树节点
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 插入节点到二叉搜索树
TreeNode* insert(TreeNode* root, int val) {
    if (!root) {
        return new TreeNode(val);
    }
    if (val < root->val) {
        root->left = insert(root->left, val);
    } else {
        root->right = insert(root->right, val);
    }
    return root;
}

// 中序遍历二叉搜索树
void inorderTraversal(TreeNode* root) {
    if (root) {
        inorderTraversal(root->left);
        cout << root->val << " ";
        inorderTraversal(root->right);
    }
}

int main() {
    TreeNode *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    cout << "Inorder traversal of the binary search tree: ";
    inorderTraversal(root);
    cout << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

输出

Inorder traversal of the binary search tree: 20 30 40 50 60 70 80 
1

总结

二叉树是一种多功能的数据结构，不同的二叉树类型适合不同的应用场景。了解每种类型的特性可以帮助你更好地选择合适的数据结构来解决问题。