第三题二叉树遍历 问题定义 输入一棵二叉树输出树的前、中、后序遍历结果。 输入一个整数NN< 10000)表示树中有N个结点编号0~N-1。 接下来N行依次为结点0~结点N-1的左右孩子情况。 每行3个整数F,L,R。L,R为F的左右孩子。L,R如果为-1表示该位置上没有孩子。 分三行分别输出树的前中后序遍历。 同一行中的数字用一个空格间隔。 输入样例 5 0 3 1 1 2 -1 2 -1 4 3 -1 -1 4 -1 -1 输出样例 0 3 1 2 4 3 0 2 4 1 3 4 2 1 0
#include #include #include #include #include #include #pragma warning(disable:4996);using namespace std;const int maxn 10010;struct node {int left;int right;int data;}Tree[maxn];int n;vector prior;vector post;vector layer;vector in;void priorTranverse(int rootNum){//根左右if (rootNum ! -1){prior.push_back(Tree[rootNum].data);priorTranverse(Tree[rootNum].left);priorTranverse(Tree[rootNum].right);}}void postTranverse(int rootNum){//左右根if (rootNum ! -1){postTranverse(Tree[rootNum].left);postTranverse(Tree[rootNum].right);post.push_back(Tree[rootNum].data);}}void levelTranverse(int rootNum){queue q;q.push(rootNum);while (!q.empty()){int top q.front();layer.push_back(top);q.pop();if (Tree[top].left ! -1) {q.push(Tree[top].left);}if (Tree[top].right ! -1) {q.push(Tree[top].right);}}}void inTranverse(int rootNum){//左根右if (rootNum ! -1){inTranverse(Tree[rootNum].left);in.push_back(Tree[rootNum].data);inTranverse(Tree[rootNum].right);}}void printAns(vector ans){for (int i 0; i < ans.size(); i){printf("%d ", ans[i]);}printf("\n");}int main(){scanf("%d", for (int i 0; i < n; i){scanf("%d %d %d", }priorTranverse(0);inTranverse(0);postTranverse(0);levelTranverse(0);printAns(prior);printAns(in);printAns(post);printAns(layer);}