#include <bits/stdc++.h> #include <stdio.h> #include <stdlib.h> #include <queue> using namespace std; const int maxn = 110; struct node{ int lchild,rchild; }Node[maxn]; bool notRoot[maxn] = {false};//记录是否不是根节点,初始均是根节点 int n,num = 0;//n为节点个数,num为当前已经输出的节点个数 //print函数输出节点id的编号 void print(int id){ printf("%d",id); num++; if(num < n)printf(" "); else printf("\n"); } //中序遍历 void inOrder(int root){ if(root == -1){ return; } inOrder(Node[root].lchild); print(root); inOrder(Node[root].rchild); } //层序遍历 void BFS(int root){ queue<int> q; q.push(root); while(!q.empty()){ int now = q.front(); q.pop(); print(now); if(Node[now].lchild != -1) q.push(Node[now].lchild); if(Node[now].rchild != -1) q.push(Node[now].rchild); } } //后序遍历 void postOrder(int root){ if(root == -1){ return; } postOrder(Node[root].lchild); postOrder(Node[root].rchild); swap(Node[root].lchild,Node[root].rchild); } int strToNum(char c){ if(c == '-'){ return -1; } else{ notRoot[c-'0'] = true; return c- '0';//返回节点编号 } } int findRoot(){ for(int i =0;i<n;++i){ if(notRoot[i] == false){ return i; } } } int main(){ char lchild,rchild; scanf("%d",&n); for(int i=0;i<n;++i){ scanf("%*c%c %c",&lchild,&rchild); Node[i].lchild = strToNum(lchild); Node[i].rchild = strToNum(rchild); } int root = findRoot(); postOrder(root); BFS(root); num = 0; inOrder(root); system("pause"); return 0; }