树的基本概念

概念讲解

什么是树？

树是一种非线性数据结构，由节点和边组成，具有以下特点：

  • 有且仅有一个根节点
  • 除根节点外，每个节点有且仅有一个父节点
  • 没有环

基本术语

术语 说明
节点 树中的元素
根节点 没有父节点的节点
叶节点 没有子节点的节点
度 节点的子节点个数
深度 从根节点到该节点的边数
高度 从该节点到最远叶节点的边数
层 深度 + 1

二叉树

定义

二叉树是每个节点最多有两个子节点的树，分别称为左子节点和右子节点。

存储方式

链式存储

1234567struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

数组存储（完全二叉树）

1234int tree[100];

// 节点 i 的子节点：2*i, 2*i+1
// 节点 i 的父节点：i/2

二叉树遍历

前序遍历（根-左-右）

1234567void preorder(TreeNode* root) {
    if (root == nullptr) return;
    
    cout << root->val << " ";  // 访问根节点
    preorder(root->left);       // 遍历左子树
    preorder(root->right);      // 遍历右子树
}

中序遍历（左-根-右）

1234567void inorder(TreeNode* root) {
    if (root == nullptr) return;
    
    inorder(root->left);        // 遍历左子树
    cout << root->val << " ";   // 访问根节点
    inorder(root->right);       // 遍历右子树
}

后序遍历（左-右-根）

1234567void postorder(TreeNode* root) {
    if (root == nullptr) return;
    
    postorder(root->left);      // 遍历左子树
    postorder(root->right);     // 遍历右子树
    cout << root->val << " ";   // 访问根节点
}

层序遍历（BFS）

12345678910111213141516void levelorder(TreeNode* root) {
    if (root == nullptr) return;
    
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        
        cout << node->val << " ";
        
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

特殊二叉树

满二叉树

每个节点都有 0 或 2 个子节点。

完全二叉树

除最后一层外，其他层都是满的，且最后一层的节点都靠左。

性质

  1. 第 i 层最多有 2^(i-1) 个节点
  2. 深度为 k 的树最多有 2^k - 1 个节点
  3. 叶节点数 = 度为 2 的节点数 + 1

考点分析

初赛考查方式

  1. 选择题： 树的基本概念
  2. 程序阅读： 理解遍历过程
  3. 填空题： 根据遍历序列还原树

常见题型

  • 遍历序列还原
  • 树的性质
  • 层序遍历

例题精讲

例题 1：遍历序列

题目： 已知前序遍历 [1,2,4,5,3]，中序遍历 [4,2,5,1,3]，求后序遍历。

解答：

前序：1 2 4 5 3
中序：4 2 5 1 3

根节点：1（前序第一个）
左子树：前序 [2,4,5]，中序 [4,2,5]
右子树：前序 [3]，中序 [3]

后序：4 5 2 3 1

例题 2：层序遍历

题目： 二叉树的层序遍历。

解答：

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

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void levelorder(TreeNode* root) {
    if (root == nullptr) return;
    
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int size = q.size();
        
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();
            
            cout << node->val << " ";
            
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        
        cout << endl;
    }
}

练习题

  1. 洛谷 P1305 新二叉树
查看答案

思路：用数组存储树，然后前序遍历。

12345678910111213141516171819202122232425262728293031#include <iostream>
using namespace std;

char leftChild[256], rightChild[256];

void preorder(char root) {
    if (root == '*') return;
    cout << root;
    preorder(leftChild[root]);
    preorder(rightChild[root]);
}

int main() {
    int n;
    cin >> n;
    
    char root;
    cin >> root;
    
    for (int i = 1; i < n; i++) {
        char node, l, r;
        cin >> node >> l >> r;
        leftChild[node] = l;
        rightChild[node] = r;
    }
    
    preorder(root);
    cout << endl;
    
    return 0;
}
  1. 洛谷 P1827 美国血统
查看答案

思路：已知中序和前序，求后序。

123456789101112131415161718192021222324252627#include <iostream>
#include <string>
using namespace std;

string inorder, preorder;

void postorder(int inStart, int inEnd, int preStart, int preEnd) {
    if (inStart > inEnd) return;
    
    char root = preorder[preStart];
    int rootIdx = inorder.find(root, inStart);
    int leftSize = rootIdx - inStart;
    
    postorder(inStart, rootIdx - 1, preStart + 1, preStart + leftSize);
    postorder(rootIdx + 1, inEnd, preStart + leftSize + 1, preEnd);
    cout << root;
}

int main() {
    cin >> inorder >> preorder;
    
    int n = inorder.size();
    postorder(0, n - 1, 0, n - 1);
    cout << endl;
    
    return 0;
}
  1. 洛谷 P1229 遍历问题
查看答案

思路：已知前序和后序，求中序遍历的可能数量。

公式：2(只有一个子节点的节点数)2^{(\text{只有一个子节点的节点数})}

12345678910111213141516171819202122232425#include <iostream>
#include <string>
using namespace std;

int main() {
    string pre, post;
    cin >> pre >> post;
    
    int count = 0;
    for (int i = 0; i < pre.size() - 1; i++) {
        for (int j = 1; j < post.size(); j++) {
            if (pre[i] == post[j] && pre[i + 1] == post[j - 1]) {
                count++;
            }
        }
    }
    
    int ans = 1;
    for (int i = 0; i < count; i++) {
        ans *= 2;
    }
    
    cout << ans << endl;
    return 0;
}

易错点

⚠️ 注意：

  1. 前序+中序可以唯一确定一棵二叉树
  2. 后序+中序可以唯一确定一棵二叉树
  3. 前序+后序不能唯一确定一棵二叉树
  4. 完全二叉树可以用数组存储