C++U5-08-二叉树1

上节课作业分析讲解视频

链接：https://pan.baidu.com/s/1_jaM_TlZmLJX4JbLuJtKzA?pwd=2us4
提取码：2us4

学习目标

 树

在C++中，二叉树是一种常用的数据结构，由节点（Node）组成，每个节点可以有最多两个子节点。二叉树具有以下几个主要的作用：

1. 存储和组织数据：二叉树可用于存储和组织大量的数据。通过使用适当的插入和删除操作，可以轻松地在二叉树中添加、查找和删除数据项。二叉树的结构使得数据可以按照特定的排序方式进行存储和访问，提高了数据的查找效率。

2. 快速的插入和删除操作：相对于其他数据结构，如数组或链表，二叉树的插入和删除操作具有更高的效率。对于已经排好序的数据，二叉树可以在O(logn)的时间复杂度内执行插入和删除操作，这使得二叉树在需要频繁插入和删除数据的场景中非常有用。

3. 快速的搜索和查找操作：二叉树的结构允许高效地进行搜索和查找操作。通过比较节点值并按照特定的规则遍历树，可以快速地找到目标数据项。对于大型数据集，二叉树可以在O(logn)的时间复杂度内执行搜索和查找操作，极大地提高了查找效率。

4. 构建其他数据结构：二叉树是许多其他常见数据结构的基础。例如，平衡二叉搜索树（如AVL树和红黑树）、堆、哈夫曼树等都是基于二叉树的扩展或变种。这些数据结构在各种算法和应用中起着重要的作用，如排序、优先队列、编码压缩等。

5. 图的表示：二叉树可以看作是一种特殊的有向图。在某些情况下，二叉树可用于表示和处理图形结构，如最小生成树算法（如Prim和Kruskal算法）和图搜索算法（如深度优先搜索和广度优先搜索）。

总之，C++中的二叉树提供了一种灵活和高效的数据结构，用于存储和组织数据，并支持快速的插入、删除、搜索和查找操作。无论是作为独立的数据结构还是作为其他数据结构的基础，二叉树都具有广泛的应用场景，并在算法设计和程序开发中发挥着重要的作用。

 树的度

 前驱后继

 树的高度

 选择题

树的存储 

双亲表示法

 孩子表示法

[【二叉树】父亲表示法]

【算法分析】
用数组存储每个结点的父节点编号，从 id 结点不断向上移动即可。

【参考代码】
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 9;
int fa[maxn];
int main() {
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        cin >> fa[i];
    }
    int id;
    cin >> id;
    while (id) {
        cout << id << " ";
        id = fa[id];
    }
    return 0;
}

 二叉树

 性质1

 性质2

 性质3

 选择题

 完全二叉树与满二叉树

满二叉树

 完全二叉树

 性质4

 性质5

 练习1

 练习2

 练习3

 叶子结点

 练习5

 练习

【二叉树】数组存储]

【算法分析】
考察二叉树的数组存储，输出 −1 就是结点下标超出了数组的范围 1∼n。

【参考代码】
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 9;
int a[maxn];
int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    while (q--) {
        int id;
        cin >> id;
        if (id / 2 >= 1) cout << a[id / 2] << " ";
        else cout << -1 << " ";
        if (id * 2 <= n) cout << a[id * 2] << " ";
        else cout << -1 << ' ';
        if (id * 2 + 1 <= n) cout << a[id * 2 + 1] << "\n";
        else cout << -1 << "\n";
    }
    return 0;
}

本节课作业分析讲解

链接：https://pan.baidu.com/s/1EXsz0RL7SpsK-MQRSHPAaw?pwd=y2jt
提取码：y2jt