1.树

1.树的基本概念

1.1.讲解

（0基础先大概浏览加粗部分）。

1.树：由若干个节点以及若干条边组成的具有层级关系且非线性的数据结构。
2.根节点：（Root）树的最顶层节点。
3.父节点：（Parent Node）节点沿着边往上一层的结点称为该节点的父节点。
4.子节点：（Child Node） 节点沿着边往下一层的结点称为该节点的子节点。
5.兄弟节点：（Sibling）同一个父亲节点的子节点互为兄弟节点。
6.叶子结点：（Leaf）没有子节点的节点称为叶子结点。
7.子树：（Subtree）以某个子节点为根节点的树分支。
8.节点的深度：（Depth）是指从根节点到该节点的距离。
9.节点的高度：（Height）该节点到叶子结点的最长距离。
10.树的高度：（Height of tree）根节点到叶子结点的最长距离。
11.节点的层级：（Level）该节点的父节点数量+1。
12.节点的度：（Degree）该节点的子节点数量。

你可能不懂，不妨看下面例子：

在上图中，是一棵树（见上1.树）。

其中根节点是1（根节点就是树冠，见上2.根节点）。

我们称1是2和3的父节点（见上3.父节点），反之，2和3是1的子节点（见上4.子节点）。

看到12和13，我们称它们互为兄弟节点（见上5.兄弟节点）。

再看到最后一层（这只是一个例子，不一定所有叶子结点都在最后一层哟！），我们称8至15都是这棵树的叶子结点（见上6.叶子结点）。

子树：仍然以上图为例，下图是上图中的一个子树（见上7.子树）。

相信上面的知识你懂了，但是下面的认真看，有点点难哟！

在图中，根节点 1 的深度为 0；节点 2 和 3 的深度为 1，因为从根节点 1 到节点 2 或 3 只经过 1 条边；节点 4、5、6、7 的深度为 2。（见上8.节点的深度）

接下来这个东西千万千万千万不要跟下面的搞混了！！！

叶子节点 8、9、10、11、12、13、14、15 的高度为 0，因为它们本身就是叶子节点；节点 4 的高度为 1，因为从节点 4 到叶子节点 8 或 9 最长距离是 1 条边。（见上9.节点的高度）

如果说8.9.是一组，那么10.11也是一组。

根节点到叶子节点的最长距离就是树的高度。图中从根节点 1 到最底层的叶子节点 8、9、10、11、12、13、14、15，最长距离是 3 条边，所以这棵树的高度为 3。（见上10.树的高度）

节点的父节点数量加 1 就是该节点的层级。根节点 1 没有父节点，它的父节点数量是 0，所以层级是 1；节点 2 和 3 有 1 个父节点（即根节点 1），它们的层级是 2（见上11.节点的层级）

节点的子节点数量就是节点的度。根节点 1 的度为 2，因为它有节点 2 和 3 两个子节点；节点 2 的度为 2，有节点 4 和 5 两个子节点；节点 3 的度为 2 ，有节点 6 和 7 两个子节点（节点的度）

1.2.题目练习

节点深度相关

已知一棵二叉树，根节点 A 下有子节点 B 和 C，B 节点下有子节点 D 和 E，节点 E 的深度是（  ）。

节点高度相关

在一棵树中，节点 F 有两个子节点 G 和 H，G 节点没有子节点，H 节点下有子节点 I 和 J，节点 F 的高度是（   ）。

树的高度相关

一棵树包含根节点 K，其下有三个子节点 L、M、N。L 节点下有四层子节点，M 节点下有两层子节点，N 节点下有三层子节点，这棵树的高度是（    ）

节点层级相关

有一棵树，根节点为 O，根节点下有两个子节点 P 和 Q，P 节点下又有三个子节点 R、S、T，节点 S 的层级是（   ）。

节点的度相关

在一棵树中，节点 U 有三个子节点 V、W、X，节点 V 有一个子节点 Y，节点 W 没有子节点，节点 X 有四个子节点，节点 U 的度是（   ），节点 V 的度是（   ）。

答案：

1.  2

2.  2

3.  5

4.  3

5.  3，1

2.二叉树的基本概念

二叉树的概念很简单，二叉树，就是除了叶子结点的所有节点度都为2，叶子结点度为0（没有儿子节点）。

3.树和二叉树的基本性质

性质：

证明：

树：

二叉树：

4.特殊树：

完全二叉树（complete binary tree）：除了最后一层，其他所有层次都被填满的二叉树。
满二叉树（full binary tree）：除了叶子节点以外，其他结点的度均为2的二叉树(特殊完全二叉树)。
完美二叉树（perfect binary tree）：所有叶子结点均在同一层，其他节点的度均为2的二叉树。

二叉搜索树（binary search tree）：
1.若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。
2.若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。
3.它的左右子树也分别为二叉搜索树。
4.中序遍历有序。
5.如果为空，无视1234性质。

平衡二叉树：
1.左右子树的高度之差的绝对值不能超过1。
2.任何一个节点的左右子树都是平衡二叉树。

二叉排序树：
1.左子树节点值<根节点值<右子树根节点值。
2.左子树和右子树又各是一棵二叉排序树。
3.如果为空，无视12性质。

路径：某节点到另一节点所经过的所有节点。
路径长度：从某节点到另一节点所经过边的数量。
节点的带权路径长度：这个值=树的根节点到该节点的路径长度*该节点的权重。
树的带权路径长度：这个值=所有叶子结点的带权路径长度之和，简称WPL。
哈夫曼树：在叶子节点和权重确定的情况下，带权路径长度最小的二叉也被称为最优二叉树。

构建哈夫曼树的方法：
1：把每一个节点都当成一颗独立的树。这样就形成了一个森林。
2：选择当前权重最小的两个节点，生成新的父节点。
3：从队列中移除上一步选择的两个最小节点，把新的父节点加入队列。
4：重复第23步。一直到队列为空，也就是没有节点的时候结束。

5.遍历方式：

深搜：
前序遍历：根左右。
中序遍历：左根右。
后序遍历：左右根。

广搜：
层次遍历：按层次遍历即可。
例如，求下边二叉树的各种遍历。

答案：
前序遍历：1 2 4 5 3 6 7
中序遍历：4 2 5 1 6 3 7
后序遍历：4 5 2 6 7 3 1
层次遍历：1 2 3 4 5 6 7

代码：

#include <bits/stdc++.h>
#include <vector>
#include <queue>
using namespace std;

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

// 构建二叉树
TreeNode* buildTree() {
    string val;
    cin >> val;
    if (val == "#") {
        return NULL;
    }
    TreeNode* root = new TreeNode(stoi(val));
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cin >> val;
        if (val != "#") {
            node->left = new TreeNode(stoi(val));
            q.push(node->left);
        }
        cin >> val;
        if (val != "#") {
            node->right = new TreeNode(stoi(val));
            q.push(node->right);
        }
    }
    return root;
}

// 前序遍历（深搜）
void preorderTraversal(TreeNode* root, vector<int>& result) {
    if (root == NULL) {
        return;
    }
    result.push_back(root->val);
    preorderTraversal(root->left, result);
    preorderTraversal(root->right, result);
}

// 中序遍历（深搜）
void inorderTraversal(TreeNode* root, vector<int>& result) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left, result);
    result.push_back(root->val);
    inorderTraversal(root->right, result);
}

// 后序遍历（深搜）
void postorderTraversal(TreeNode* root, vector<int>& result) {
    if (root == NULL) {
        return;
    }
    postorderTraversal(root->left, result);
    postorderTraversal(root->right, result);
    result.push_back(root->val);
}

// 层次遍历（广搜）
void levelOrderTraversal(TreeNode* root, vector<int>& result) {
    if (root == NULL) {
        return;
    }
    queue<TreeNode*> q;
    q.push(root);
    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);
        }
    }
}

// 辅助函数，用于打印结果
void printVector(const vector<int>& vec) {
    for (int num : vec) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    cout << "请按层输入二叉树节点值，空节点用 # 表示：" << endl;
    TreeNode* root = buildTree();

    vector<int> preorderResult;
    preorderTraversal(root, preorderResult);
    cout << "前序遍历结果: ";
    printVector(preorderResult);

    vector<int> inorderResult;
    inorderTraversal(root, inorderResult);
    cout << "中序遍历结果: ";
    printVector(inorderResult);

    vector<int> postorderResult;
    postorderTraversal(root, postorderResult);
    cout << "后序遍历结果: ";
    printVector(postorderResult);

    vector<int> levelOrderResult;
    levelOrderTraversal(root, levelOrderResult);
    cout << "层次遍历结果: ";
    printVector(levelOrderResult);

    return 0;
}