C++精灵库二叉树四种遍历算法可视化程序
本程序实现了二叉树的四种遍历实现：
前序遍历：根→左→右
中序遍历：左→根→右
后序遍历：左→右→根
层序遍历（BFS）：按层级从左到右访问
这个程序非常生动且具有教育意义。简单来说，这个程序就像是一个“二叉树遍历算法的动态模拟器”。它通过动画形式直观展示了二叉树的前序遍历、中序遍历、后序遍历和按层遍历（BFS）四种经典算法。所有代码如下所示：
#include "sprites.h" //包含C++精灵库 #include <vector> #include <queue> #include <map> #include <string> using namespace std; Sprite rocket; // 建立角色叫rocket，用于画树 Sprite visitor; // 建立角色用于演示遍历 int d = 18; //rocket角色单位旋转的度数 // 二叉树节点结构，每个节点有坐标，层级，左子树指针，右子树指针四个字段 struct TreeNode { pair<float, float> position; // 节点自包含坐标信息 int level; // 节点所在的层级 TreeNode* left; //左子树 TreeNode* right; //右子树 TreeNode(pair<float, float> pos, int lvl) { //构造函数 position = pos; level = lvl; left = nullptr; right = nullptr; } }; vector<pair<float, float>> posList; // 存储所有节点坐标的顺序表 vector<TreeNode*> nodes; // 存储所有节点指针的向量 TreeNode* root = nullptr; // 树的根节点 map<int, vector<pair<float, float>> > levelPositions; // 按层存储节点坐标 // 创建节点并记录坐标 TreeNode* createNode(pair<float, float> pos, int level) { TreeNode* node = new TreeNode(pos, level); posList.push_back(pos); nodes.push_back(node); levelPositions[level].push_back(pos); return node; } // 画二叉树并构建树结构 TreeNode* draw_tree(int level, int currentLevel = 0) { if (level < 1) { rocket.dot(20, "red"); return createNode(rocket.pos(), currentLevel); } rocket.dot(20, "red"); // 画当前节点（根节点） TreeNode* currentNode = createNode(rocket.pos(), currentLevel); // 画左子树 rocket.right(level * d); rocket.fd(50 * level); rocket.left(level * d); // 让角色朝下 currentNode->left = draw_tree(level - 1, currentLevel + 1); // 回到根节点 rocket.right(level * d); //恢复方向 rocket.bk(50 * level); //退回 // 画右子树 rocket.left(2 * level * d); rocket.fd(50 * level); rocket.right(level * d); // 让角色朝下 currentNode->right = draw_tree(level - 1, currentLevel + 1); // 回到根节点 rocket.left(level * d); rocket.bk(50 * level); rocket.right(level * d); return currentNode; } // 前序遍历演示 void preorderTraversal(TreeNode* node) { if (node == nullptr) return; // 访问当前节点 visitor.go(node->position); visitor.dot(15, "green"); visitor.wait(0.5); preorderTraversal(node->left); // 遍历左子树 preorderTraversal(node->right); // 遍历右子树 } // 中序遍历演示 void inorderTraversal(TreeNode* node) { if (node == nullptr) return; inorderTraversal(node->left); // 遍历左子树 // 访问当前节点 visitor.go(node->position); visitor.dot(15, "blue"); visitor.wait(0.5); inorderTraversal(node->right); // 遍历右子树 } // 后序遍历演示 void postorderTraversal(TreeNode* node) { if (node == nullptr) return; postorderTraversal(node->left); // 遍历左子树 postorderTraversal(node->right); // 遍历右子树 // 访问当前节点 visitor.go(node->position.first, node->position.second); visitor.dot(15, "purple"); visitor.wait(0.5); } // 按层遍历（BFS）演示 void levelOrderTraversal(TreeNode* root) { if (root == nullptr) return; queue<TreeNode*> q; //建立保存节点地址的队列 q.push(root); //根节点入队 while (!q.empty()) { TreeNode* current = q.front(); q.pop(); //出队 // 访问当前节点 visitor.go(current->position); visitor.dot(15, "orange"); visitor.wait(0.5); // 将子节点加入队列 if (current->left != nullptr) q.push(current->left); if (current->right != nullptr) q.push(current->right); } } // 演示所有遍历算法 void demonstrateAllTraversals(TreeNode* root) { visitor.speed(5).shape("circle").scale(0.5); // 1. 前序遍历演示 visitor.pu().go(-300, 300); //V1.0.2后可以写成 write("字符串",22); visitor.write("前序遍历: 根->左->右", "center",{"","22","normal"} ); visitor.go(posList[0]); preorderTraversal(root); visitor.wait(1); // 2. 中序遍历演示 visitor.pu().go(-300, 250); visitor.write("中序遍历: 左->根->右", "center",{"","22","normal"} ); visitor.go(posList[0]); inorderTraversal(root); visitor.wait(1); // 3. 后序遍历演示 visitor.pu().go(-300, 200); visitor.write("后序遍历: 左->右->根", "center",{"","22","normal"} ); visitor.go(posList[0]); postorderTraversal(root); visitor.wait(1); // 4. 按层遍历演示 visitor.pu().go(-300, 150); visitor.write("按层遍历: 本质是BFS", "center",{"","22","normal"} ); visitor.go(posList[0]); levelOrderTraversal(root); visitor.wait(1); } // 打印节点信息 void printNodeInfo() { cout << "=== 二叉树节点信息 ===" << endl; cout << "总节点数: " << posList.size() << endl << endl; cout << "所有节点坐标:" << endl; for (int i = 0; i < posList.size(); i++) cout << "节点 " << i << ": (" << posList[i].first << ", " << posList[i].second << ")" << endl; cout << endl; cout << "按层节点分布:" << endl; for (auto& level : levelPositions) { cout << "第 " << level.first << " 层: "; for (auto& pos : level.second) cout << "(" << pos.first << "," << pos.second << ") "; cout << endl; } } int main() { // 主功能块 rocket.speed(0).color("blue").right(90).pu().bk(200).pd(); root = draw_tree(3); // 画树并构建树结构 rocket.hide(); //隐藏画树的角色 printNodeInfo(); // 打印节点信息 visitor.speed(3).color("red").pu(); // 设置遍历演示角色 demonstrateAllTraversals(root); // 演示所有遍历算法 visitor.pu().go(0, 360); // 显示遍历说明 visitor.write("二叉树遍历演示", "center",{"","32","normal"} ); visitor.pu().go(200, 300); // 图例说明 visitor.dot(10, "green"); visitor.go(250, 300); visitor.write("前序", "center",{"","20","normal"}); visitor.pu().go(200, 250); visitor.dot(10, "blue"); visitor.go(250, 250); visitor.write("中序", "center",{"","20","normal"}); visitor.pu().go(200, 200); visitor.dot(10, "purple"); visitor.go(250, 200); visitor.write("后序", "center",{"","20","normal"}); visitor.pu().go(200, 150); visitor.dot(10, "orange"); visitor.go(250, 150); visitor.write("按层", "center",{"","20","normal"}); visitor.hide(); rocket.done(); // 完成了 return 0; // 返回0 }这个程序不仅是一个画一个二叉树这么简单，它是连接代码逻辑与物理空间的一座桥梁。
在信息学奥赛的算法教学中，它能把枯燥的树形结构“盘活”，帮助学生建立几何直觉，让算法学习变得像玩游戏一样直观有趣。
我们看到,只要掌握C++精灵库中的dot(), fd(), go()等基础命令，即可构建比较复杂的算法动画。
而本程序可完全自定义,胜在灵活性和实时性，可以自定义树或者图等结构并在本地环境运行，不受网络限制。更有趣的是,这些命令和Python turtle库中的命令用法基本一致,所以把这个C++程序稍微修改一下,就能在Python IDE中运行。你不要怕麻烦哦，这可是练习的好机会。
这就叫一箭双雕。这个程序不仅能帮助学生直观理解递归和遍历算法，还能激发学习兴趣、提升解题思维，是算法编程学习过程中较好的辅助工具。
