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 { pairfloat, float position; // 节点自包含坐标信息 int level; // 节点所在的层级 TreeNode* left; //左子树 TreeNode* right; //右子树 TreeNode(pairfloat, float pos, int lvl) { //构造函数 position pos; level lvl; left nullptr; right nullptr; } }; vectorpairfloat, float posList; // 存储所有节点坐标的顺序表 vectorTreeNode* nodes; // 存储所有节点指针的向量 TreeNode* root nullptr; // 树的根节点 mapint, vectorpairfloat, float levelPositions; // 按层存储节点坐标 // 创建节点并记录坐标 TreeNode* createNode(pairfloat, 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; queueTreeNode* 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中运行。你不要怕麻烦哦这可是练习的好机会。这就叫一箭双雕。这个程序不仅能帮助学生直观理解递归和遍历算法还能激发学习兴趣、提升解题思维是算法编程学习过程中较好的辅助工具。