题意：反转一颗二叉树，然后输出层次遍历和中序遍历
思路：不用反转二叉树，遍历顺序只需由先前的先访问左子树变成先访问右子树即可。用一个结构体数组保存此二叉树之间的关系，进行中序遍历时，对每个节点的层次和index进行赋值，然后把节点加入中序数组中，中序直接打印即可，层次遍历用刚才的每个节点的层次和index进行排序输出即为层次遍历
代码：
#include<iostream> #include<vector> #include<string> #include<algorithm> using namespace std; struct node { int id, l, r, index, level;//index用于区分同一层次的节点的先后顺序 }nodes[15]; vector<node> p,q; bool v[15] = { false }; int n = 0, root = 0; void inorderTravel(int root,int index,int level) {//中序遍历 if (nodes[root].r != -1) inorderTravel(nodes[root].r, index * 2 + 2, level + 1); p.push_back({root,0,0,index,level});//把节点压入数组中 if (nodes[root].l != -1)inorderTravel(nodes[root].l, index * 2 + 1, level + 1); } bool cmp(node a,node b) { if (a.level != b.level)return a.level < b.level; return a.index > b.index; } int main() { cin >> n; for (int i = 0; i < n; i++) {//在每个节点得右边没有出现的即为根节点 string l, r; cin >> l >> r; if (l != "-") { nodes[i].l = stoi(l); v[stoi(l)] = true; } else { nodes[i].l = -1; } if (r != "-") { nodes[i].r = stoi(r); v[stoi(r)] = true; } else { nodes[i].r = -1; } } while (v[root] == true)root++;//寻找根节点 inorderTravel(root,0,0); q = p; sort(q.begin(),q.end(),cmp); for (int i = 0; i < q.size(); i++) { printf("%d%s",q[i].id,i!=q.size()-1?" ":"\n"); } for (int i = 0; i < p.size(); i++) { printf("%d%s",p[i].id,i!=q.size()-1?" ":"\n"); } system("pause"); return 0; }
