本文共 1181 字，大约阅读时间需要 3 分钟。
#include#include #include #include #include using namespace std;struct node{ int id, index, level; post, in, pre;};void pre_order(int root, int startt, int endd, int index, int level){ if (startt > endd) return; int i = startt; while (i < endd && in[i].id != post[root].id) i++; pre.push_back({post[root].id, index, level}); pre_order(root + i - endd - 1, startt, i -1, index*2+1, level+1); pre_order(root -1, i+1, endd, index*2+2, level+1);}bool cmp(node x, node y){ if (x.level != y.level) return x.level < y.level; return x.index < y.index;}int main(){ int n; scanf("%d", &n); post.resize(n); in.resize(n); for (int i = 0; i < n; i++){ scanf("%d", &post[i].id); in[i].id =-1; // 初始化为-1，表示未读取 } // 初始化遍历方向，默认左优先 pre_order(n-1, 0, n-1, 0, 0); // 根据level和index排序结果 sort(pre.begin(), pre.end(), cmp); // 输出结果 for (int i=0; i
上述代码实现了二叉树的预序遍历（前序），其中使用了传统的非递归实现方式。代码的关键部分如下：
pre_order函数：实现了预序遍历，采用迭代的方式找到当前子树的根节点，然后递归地处理左子树和右子树。cmp函数：用于排序预序遍历结果，根据节点的层级和索引进行排序。main函数：读取输入数据，调用预序遍历函数并输出结果。整个过程通过模拟手工编写的风格，将代码结构清晰化，便于理解和维护。
转载地址：http://yiipz.baihongyu.com/