【开发】 - 树

宋 游戏开发
  2025-07-31 00:19:07 2025-07-31 00:19:07 创建   2025-07-31 00:39:28 2025-07-31 00:39:28 更新      3k 字  13 分钟

作为一个联想能力较差的学渣，没有举例实际应用的学习总是很快就忘，树的应用就是如此，所以总结一下树的应用还是很有必要的。

1. 层序遍历（BFS）

特点：按层级从上到下、从左到右访问节点。
应用场景：

  • 场景加载与分层渲染
    在游戏场景中，地图或场景可能分为多层（如背景层、角色层、特效层）。通过层序遍历，可以逐层加载或渲染对象，确保层级逻辑正确。
    示例： 

    1
    2
    3
    4
    5
    6
    二叉树结构表示场景层级：
           场景根节点
          /          \
       背景层       角色层
      /   \       /     \
    背景1 背景2  角色A  角色B

    层序遍历顺序：场景根节点 → 背景层、角色层 → 背景1、背景2、角色A、角色B。
    用途：确保先加载场景根节点，再逐层加载背景和角色，避免渲染顺序混乱。

  • 敌人生成与波次控制
    在RPG或塔防游戏中，敌人可能分波次生成。层序遍历可用于逐层生成敌人，先生成第一波敌人（顶层节点），再生成后续波次（下一层节点）。
    示例： 

    1
    2
    3
    4
    5
    6
    二叉树结构表示敌人波次：
           波次1
          /     \
        波次2   波次3
       /   \     / \
    波次4 波次5 波次6 波次7

    层序遍历顺序：波次1 → 波次2、波次3 → 波次4、波次5、波次6、波次7。
    用途：按层级控制敌人生成节奏，确保游戏难度逐步提升。

  • 资源管理与依赖加载
    游戏资源（如纹理、模型）可能有依赖关系。层序遍历可按层级加载资源，先加载父资源，再加载子资源。
    示例： 

    1
    2
    3
    4
    5
    6
    二叉树结构表示资源依赖：
           场景资源
          /          \
       角色模型     背景纹理
      /   \       /     \
    动画1 动画2 纹理A  纹理B

    层序遍历顺序：场景资源 → 角色模型、背景纹理 → 动画1、动画2、纹理A、纹理B。
    用途：确保父资源加载完成后再加载子资源，避免资源缺失导致的错误。

2. 前序遍历（根-左-右）

特点：先访问根节点，再递归处理子节点。
应用场景：

  • 游戏数据保存与恢复
    在保存游戏进度时，需要递归保存每个节点的状态。前序遍历可以按“父节点先于子节点”的顺序保存数据，确保父子关系正确。
    示例： 

    1
    2
    3
    4
    5
    6
    二叉树结构表示玩家技能树：
           技能A
          /     \
        技能B   技能C
       /   \     / \
    技能D 技能E 技能F 技能G

    前序遍历顺序：技能A → 技能B → 技能D → 技能E → 技能C → 技能F → 技能G。
    用途：保存技能树时，先保存父技能，再保存子技能，避免技能依赖丢失。

  • 场景构建与初始化
    游戏场景初始化时，可能需要先创建父对象（如场景根节点），再依次创建子对象（如角色、道具）。
    示例： 

    1
    2
    3
    4
    5
    6
    二叉树结构表示场景对象：
           场景根
          /      \
       角色组    道具组
      /   \       / \
    角色1 角色2 道具A 道具B

    前序遍历顺序：场景根 → 角色组 → 角色1 → 角色2 → 道具组 → 道具A → 道具B。
    用途：按层级初始化场景对象，确保父对象存在后再创建子对象。

  • AI行为树的执行顺序
    在行为树中，父节点的条件可能需要先被评估，再执行子节点的行为。前序遍历可满足这种逻辑。
    示例： 

    1
    2
    3
    4
    5
    6
    二叉树结构表示AI行为：
           检查敌人
          /        \
       追逐敌人    攻击敌人
      /   \         / \
    移动  回避   普通攻击 特殊攻击

    前序遍历顺序：检查敌人 → 追逐敌人 → 移动 → 回避 → 攻击敌人 → 普通攻击 → 特殊攻击。
    用途：先评估是否检测到敌人，再决定后续行为。

3. 中序遍历（左-根-右）

特点：先遍历左子树，再访问根节点，最后遍历右子树。
应用场景：

  • 排序与查找
    如果二叉树是二叉搜索树（BST），中序遍历会得到有序序列。在游戏开发中，可用于排序玩家积分、物品价格等。
    示例： 

    1
    2
    3
    4
    5
    6
    二叉搜索树表示玩家积分：
           80
          /  \
        60   100
       / \    / \
     50  70 90 110

    中序遍历结果：50 → 60 → 70 → 80 → 90 → 100 → 110。
    用途：快速生成玩家积分排行榜，或查找特定分数段的玩家。

  • 物品栏管理
    玩家背包中的物品可能需要按名称或类别排序。中序遍历可生成有序列表，方便查找。
    示例： 

    1
    2
    3
    4
    5
    6
    二叉树结构表示物品栏：
           防具
          /   \
        武器   消耗品
       / \     / \
     剑  斧   药水 食物

    中序遍历顺序：剑 → 武器 → 斧 → 防具 → 药水 → 消耗品 → 食物。
    用途：生成按类别排序的物品列表，方便玩家浏览。

  • 动态路径规划
    在迷宫或地图中，中序遍历可用于生成特定顺序的路径，例如先探索左侧区域，再回到根节点，最后探索右侧区域。
    示例： 

    1
    2
    3
    4
    5
    6
    二叉树结构表示地图区域：
           中心区域
          /         \
       左侧区域    右侧区域
      /   \         / \
    A区  B区     C区  D区

    中序遍历顺序：A区 → 左侧区域 → B区 → 中心区域 → C区 → 右侧区域 → D区。
    用途：按特定顺序探索地图区域，确保覆盖所有区域。

4. 后序遍历（左-右-根）

特点：先遍历子节点，再访问根节点。
应用场景：

  • 资源释放与销毁
    在关闭游戏场景或销毁对象时，需先释放子节点资源，最后释放父节点。
    示例： 

    1
    2
    3
    4
    5
    6
    二叉树结构表示场景对象：
           场景根
          /      \
       角色组    道具组
      /   \       / \
    角色1 角色2 道具A 道具B

    后序遍历顺序：角色1 → 角色2 → 角色组 → 道具A → 道具B → 道具组 → 场景根。
    用途：先销毁角色和道具，再销毁父节点，避免引用失效导致的错误。

  • 计算子树属性
    在游戏中，可能需要计算某个节点的子树属性（如总攻击力、总生命值）。后序遍历可确保先计算子节点，再汇总到父节点。
    示例： 

    1
    2
    3
    4
    5
    6
     二叉树结构表示角色属性：
            总攻击力
           /       \
       近战伤害   法术伤害
      /   \         / \
    剑术  斧击    火球  冰霜

    后序遍历顺序：剑术 → 斧击 → 近战伤害 → 火球 → 冰霜 → 法术伤害 → 总攻击力。
    用途：先计算近战和法术伤害的子节点，再汇总总攻击力。

  • 场景清理与回收
    在游戏关卡结束时，需清理所有对象（如敌人、道具）。后序遍历可逐层清理，确保子对象先被处理。
    示例： 

    1
    2
    3
    4
    5
    6
    二叉树结构表示关卡对象：
           关卡1
          /     \
       敌人组   道具组
      /   \       / \
    敌人A 敌人B 道具C 道具D

    后序遍历顺序：敌人A → 敌人B → 敌人组 → 道具C → 道具D → 道具组 → 关卡1。
    用途：先清理敌人和道具，再清理关卡，避免残留对象影响后续逻辑。

总结

遍历方式 特点 游戏开发典型场景
层序遍历 按层级访问 场景分层渲染、敌人波次生成、资源加载
前序遍历 根节点优先 数据保存、场景初始化、AI行为树
中序遍历 左-根-右 排序与查找（积分、物品）、路径规划
后序遍历 子节点优先 资源释放、子树属性计算、场景清理

二叉树代码

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <queue>
#include <vector>

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

class BinaryTree {
public:
    BinaryTreeNode* root;

    BinaryTree() : root(nullptr) {}

    // 构造完全二叉树示例
    void createSampleTree() {
        root = new BinaryTreeNode(1);
        root->left = new BinaryTreeNode(2);
        root->right = new BinaryTreeNode(3);
        root->left->left = new BinaryTreeNode(4);
        root->left->right = new BinaryTreeNode(5);
        root->right->left = new BinaryTreeNode(6);
        root->right->right = new BinaryTreeNode(7);
    }

    // 层序遍历
    std::vector<int> levelOrder() {
        std::vector<int> result;
        if (!root) return result;
        
        std::queue<BinaryTreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            BinaryTreeNode* node = q.front();
            q.pop();
            result.push_back(node->val);
            
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        return result;
    }

    // 前序遍历
    std::vector<int> preorderTraversal() {
        std::vector<int> result;
        preorderRecursive(root, result);
        return result;
    }

    // 中序遍历
    std::vector<int> inorderTraversal() {
        std::vector<int> result;
        inorderRecursive(root, result);
        return result;
    }

    // 后序遍历
    std::vector<int> postorderTraversal() {
        std::vector<int> result;
        postorderRecursive(root, result);
        return result;
    }

private:
    void preorderRecursive(BinaryTreeNode* node, std::vector<int>& result) {
        if (!node) return;
        result.push_back(node->val);
        preorderRecursive(node->left, result);
        preorderRecursive(node->right, result);
    }

    void inorderRecursive(BinaryTreeNode* node, std::vector<int>& result) {
        if (!node) return;
        inorderRecursive(node->left, result);
        result.push_back(node->val);
        inorderRecursive(node->right, result);
    }

    void postorderRecursive(BinaryTreeNode* node, std::vector<int>& result) {
        if (!node) return;
        postorderRecursive(node->left, result);
        postorderRecursive(node->right, result);
        result.push_back(node->val);
    }
};
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
using System;
using System.Collections.Generic;

public class BinaryTreeNode
{
    public int Val;
    public BinaryTreeNode Left;
    public BinaryTreeNode Right;

    public BinaryTreeNode(int x) { Val = x; }
}

public class BinaryTree
{
    public BinaryTreeNode Root { get; private set; }

    public BinaryTree()
    {
        Root = null;
    }

    // 构造完全二叉树示例
    public void CreateSampleTree()
    {
        Root = new BinaryTreeNode(1)
        {
            Left = new BinaryTreeNode(2)
            {
                Left = new BinaryTreeNode(4),
                Right = new BinaryTreeNode(5)
            },
            Right = new BinaryTreeNode(3)
            {
                Left = new BinaryTreeNode(6),
                Right = new BinaryTreeNode(7)
            }
        };
    }

    // 层序遍历
    public List<int> LevelOrder()
    {
        var result = new List<int>();
        if (Root == null) return result;
        
        var queue = new Queue<BinaryTreeNode>();
        queue.Enqueue(Root);
        
        while (queue.Count > 0)
        {
            var node = queue.Dequeue();
            result.Add(node.Val);
            
            if (node.Left != null) queue.Enqueue(node.Left);
            if (node.Right != null) queue.Enqueue(node.Right);
        }
        return result;
    }

    // 前序遍历
    public List<int> PreorderTraversal()
    {
        var result = new List<int>();
        PreorderRecursive(Root, result);
        return result;
    }

    // 中序遍历
    public List<int> InorderTraversal()
    {
        var result = new List<int>();
        InorderRecursive(Root, result);
        return result;
    }

    // 后序遍历
    public List<int> PostorderTraversal()
    {
        var result = new List<int>();
        PostorderRecursive(Root, result);
        return result;
    }

    private void PreorderRecursive(BinaryTreeNode node, List<int> result)
    {
        if (node == null) return;
        result.Add(node.Val);
        PreorderRecursive(node.Left, result);
        PreorderRecursive(node.Right, result);
    }

    private void InorderRecursive(BinaryTreeNode node, List<int> result)
    {
        if (node == null) return;
        InorderRecursive(node.Left, result);
        result.Add(node.Val);
        InorderRecursive(node.Right, result);
    }

    private void PostorderRecursive(BinaryTreeNode node, List<int> result)
    {
        if (node == null) return;
        PostorderRecursive(node.Left, result);
        PostorderRecursive(node.Right, result);
        result.Add(node.Val);
    }
}
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class BinaryTreeNode {
    val: number;
    left: BinaryTreeNode | null;
    right: BinaryTreeNode | null;

    constructor(val: number) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class BinaryTree {
    root: BinaryTreeNode | null;

    constructor() {
        this.root = null;
    }

    // 构造完全二叉树示例
    createSampleTree(): void {
        this.root = new BinaryTreeNode(1);
        this.root.left = new BinaryTreeNode(2);
        this.root.right = new BinaryTreeNode(3);
        this.root.left.left = new BinaryTreeNode(4);
        this.root.left.right = new BinaryTreeNode(5);
        this.root.right.left = new BinaryTreeNode(6);
        this.root.right.right = new BinaryTreeNode(7);
    }

    // 层序遍历
    levelOrder(): number[] {
        const result: number[] = [];
        if (!this.root) return result;
        
        const queue: BinaryTreeNode[] = [this.root];
        
        while (queue.length > 0) {
            const node = queue.shift()!;
            result.push(node.val);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        return result;
    }

    // 前序遍历
    preorderTraversal(): number[] {
        const result: number[] = [];
        this.preorderRecursive(this.root, result);
        return result;
    }

    // 中序遍历
    inorderTraversal(): number[] {
        const result: number[] = [];
        this.inorderRecursive(this.root, result);
        return result;
    }

    // 后序遍历
    postorderTraversal(): number[] {
        const result: number[] = [];
        this.postorderRecursive(this.root, result);
        return result;
    }

    private preorderRecursive(node: BinaryTreeNode | null, result: number[]): void {
        if (!node) return;
        result.push(node.val);
        this.preorderRecursive(node.left, result);
        this.preorderRecursive(node.right, result);
    }

    private inorderRecursive(node: BinaryTreeNode | null, result: number[]): void {
        if (!node) return;
        this.inorderRecursive(node.left, result);
        result.push(node.val);
        this.inorderRecursive(node.right, result);
    }

    private postorderRecursive(node: BinaryTreeNode | null, result: number[]): void {
        if (!node) return;
        this.postorderRecursive(node.left, result);
        this.postorderRecursive(node.right, result);
        result.push(node.val);
    }
}
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
-- 二叉树节点
BinaryTreeNode = {}
BinaryTreeNode_mt = {
    __index = BinaryTreeNode
}

function BinaryTreeNode.create(val)
    local node = {
        val = val,
        left = nil,
        right = nil
    }
    return setmetatable(node, BinaryTreeNode_mt)
end

-- 二叉树类
BinaryTree = {}
BinaryTree_mt = {
    __index = BinaryTree
}

function BinaryTree.create()
    return setmetatable({root = nil}, BinaryTree_mt)
end

-- 构造完全二叉树示例
function BinaryTree:createSampleTree()
    self.root = BinaryTreeNode.create(1)
    self.root.left = BinaryTreeNode.create(2)
    self.root.right = BinaryTreeNode.create(3)
    self.root.left.left = BinaryTreeNode.create(4)
    self.root.left.right = BinaryTreeNode.create(5)
    self.root.right.left = BinaryTreeNode.create(6)
    self.root.right.right = BinaryTreeNode.create(7)
end

-- 层序遍历
function BinaryTree:levelOrder()
    local result = {}
    if not self.root then return result end
    
    local queue = {self.root}
    
    while #queue > 0 do
        local node = table.remove(queue, 1)
        table.insert(result, node.val)
        
        if node.left then table.insert(queue, node.left) end
        if node.right then table.insert(queue, node.right) end
    end
    return result
end

-- 前序遍历
function BinaryTree:preorderTraversal()
    local result = {}
    self:preorderRecursive(self.root, result)
    return result
end

-- 中序遍历
function BinaryTree:inorderTraversal()
    local result = {}
    self:inorderRecursive(self.root, result)
    return result
end

-- 后序遍历
function BinaryTree:postorderTraversal()
    local result = {}
    self:postorderRecursive(self.root, result)
    return result
end

-- 递归辅助函数
function BinaryTree:preorderRecursive(node, result)
    if not node then return end
    table.insert(result, node.val)
    self:preorderRecursive(node.left, result)
    self:preorderRecursive(node.right, result)
end

function BinaryTree:inorderRecursive(node, result)
    if not node then return end
    self:inorderRecursive(node.left, result)
    table.insert(result, node.val)
    self:inorderRecursive(node.right, result)
end

function BinaryTree:postorderRecursive(node, result)
    if not node then return end
    self:postorderRecursive(node.left, result)
    self:postorderRecursive(node.right, result)
    table.insert(result, node.val)
end
  • 标题: 【开发】 - 树
  • 作者: 宋
  • 创建于 : 2025-07-31 00:19:07
  • 更新于 : 2025-07-31 00:39:28
  • 链接: https://sxl-space.tk/2025/07/31/007_Tree/
  • 版权声明: 版权所有 © 宋，禁止转载。
目录
【开发】 - 树
  1. 1. 1. 层序遍历（BFS）
  2. 2. 2. 前序遍历（根-左-右）
  3. 3. 3. 中序遍历（左-根-右）
  4. 4. 4. 后序遍历（左-右-根）
  5. 5. 总结
  6. 6. 二叉树代码