第一行一个正整数n(1<=n<=100),表示二叉树有n个结点。
接下来n行,第i行两个整数li,ri (0<=li,ri<=n) ,分别表示第i个结点的左儿子和右儿子,为0代表空。
保证根为1,保证输入为合法二叉树。
输出四行。
第一行为二叉树的前序遍历;
第二行为中序遍历;
第三行为后序遍历;
第四行为层次遍历。
每一行输出n个数,代表该方式遍历的结点的顺序,相邻两个数之间用一个空格相隔。
5 3 2 0 5 0 4 0 0 0 0
1 3 4 2 5 3 4 1 2 5 4 3 5 2 1 1 3 2 4 5
#include<cstring> #include<algorithm> #include<vector> #include<map> #include<queue> #include<cstdio> #include<stack> #include<cmath> #include<iostream> #define ll long long #define lowbit(x) x&(-x) using namespace std; struct TreeNode { int val; int left; int right; }t[1000]; int vis[1000]; int ans[1000]; void preOrder2(TreeNode root) { stack<TreeNode> stk; stk.push(root); int k=0; while(!stk.empty()) { TreeNode pNode = stk.top(); stk.pop(); ans[k++]=pNode.val; if(pNode.right != 0) stk.push(t[pNode.right]); if(pNode.left != 0) stk.push(t[pNode.left]); } } void inOrder2(TreeNode root) { stack<TreeNode> stk; TreeNode pNode = root; int k=0; while(pNode.val != 0 || !stk.empty()) { if(pNode.val != 0) { stk.push(pNode); pNode = t[pNode.left]; } else { pNode = stk.top(); stk.pop(); ans[k++]=pNode.val; pNode = t[pNode.right]; } } } void postOrder2(TreeNode root) { if(root.val == 0) return; int k=0; stack<TreeNode > stk, stk2; stk.push(root); while(!stk.empty()) { TreeNode pNode = stk.top(); stk.pop(); stk2.push(pNode); if(pNode.left != 0) stk.push(t[pNode.left]); if(pNode.right != 0) stk.push(t[pNode.right]); } while(!stk2.empty()) { ans[k++]=stk2.top().val; stk2.pop(); } } int main() { int n; while(~scanf("%d",&n)) { memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) { int a,b; scanf("%d%d",&a,&b); t[i].left=a; t[i].right=b; t[i].val=i; vis[a]=1; vis[b]=1; } int root; for(int i=1;i<=n;i++) { if(vis[i]==0) { root=i; break; } } preOrder2(t[root]); for(int i=0;i<n-1;i++) { printf("%d ",ans[i]); } printf("%d\n",ans[n-1]); inOrder2(t[root]); for(int i=0;i<n-1;i++) { printf("%d ",ans[i]); } printf("%d\n",ans[n-1]); postOrder2(t[root]); for(int i=0;i<n-1;i++) { printf("%d ",ans[i]); } printf("%d\n",ans[n-1]); queue<TreeNode> q; q.push(t[root]); int k=0; while(!q.empty()) { TreeNode now=q.front(); q.pop(); ans[k++]=now.val; if(now.left!=0) q.push(t[now.left]); if(now.right!=0) q.push(t[now.right]); } for(int i=0;i<n-1;i++) { printf("%d ",ans[i]); } printf("%d\n",ans[n-1]); } }
#include <iostream> #include <queue> #include <stack> #include <unordered_set> using namespace std; struct TreeNode { TreeNode(int val) :val(val), left(NULL), right(NULL) {} int val; TreeNode* left; TreeNode* right; }; int main() { int n; cin >> n; TreeNode* root = new TreeNode(1); queue<TreeNode*> q; q.push(root); int tnum = 0; for (int i = 0; i < n; ++i) { cin >> tnum; if (tnum) { q.front()->left = new TreeNode(tnum); q.push(q.front()->left); } cin >> tnum; if (tnum) { q.front()->right = new TreeNode(tnum); q.push(q.front()->right); } q.pop(); } //前序遍历:根->左->右 stack<TreeNode*> st; TreeNode* tmp = NULL; st.push(root); while (!st.empty()) { tmp = st.top(); st.pop(); cout << tmp->val << " "; if (tmp->right) st.push(tmp->right); if (tmp->left) st.push(tmp->left); } cout << endl; stack<TreeNode*>().swap(st); //中序遍历:左->根->右 tmp = root; while (tmp || !st.empty()) { if (tmp) { st.push(tmp); tmp = tmp->left; } else { cout << st.top()->val << " "; tmp = st.top()->right; st.pop(); } } cout << endl; stack<TreeNode*>().swap(st); stack<TreeNode*> st2; //后序遍历:左->右->根 st.push(root); while (!st.empty()) { tmp = st.top(); st.pop(); st2.push(tmp); if (tmp->left) st.push(tmp->left); if (tmp->right) st.push(tmp->right); } while (!st2.empty()) { cout << st2.top()->val << " "; st2.pop(); } //层序遍历 cout << endl; queue<TreeNode*>().swap(q); q.push(root); while (!q.empty()) { cout << q.front()->val << " "; if (q.front()->left) q.push(q.front()->left); if (q.front()->right) q.push(q.front()->right); q.pop(); } }
//没想出好方法,代码有点长 #include<iostream> #include<vector> #include<queue> #include<stack> using namespace std; int main() { int n; cin >> n; vector<int>val(n + 1); vector<int>le(n + 1, 0); vector<int>ri(n + 1, 0); for (int i = 0; i <= n; i++) val[i] = i; for (int i = 1; i <= n; i++) { cin >> le[i] >> ri[i]; } vector<int>lef(le); vector<int>rif(ri); stack<int>zhan; //前序遍历 lef.assign(le.begin(), le.end()); rif.assign(ri.begin(), ri.end()); zhan.push(1);//根节点为1 cout << 1 << " ";//前序遍历在节点加入进来时输出 while (!zhan.empty()) { int tmp = zhan.top(); if (lef[tmp]) { zhan.push(lef[tmp]); cout << lef[tmp] << " "; lef[tmp] = 0; } else if (rif[tmp]) { zhan.push(rif[tmp]); cout << rif[tmp] << " "; rif[tmp] = 0; } else zhan.pop(); } cout << endl; //中序遍历,入栈中左右,输出左中右,没有左右值的出栈 lef.assign(le.begin(), le.end()); rif.assign(ri.begin(), ri.end()); //stack<int>zhan2; zhan.push(1); while (!zhan.empty()) { int tmp = zhan.top(); if (lef[tmp]) { zhan.push(lef[tmp]); lef[tmp] = 0; } else if (rif[tmp]) {//将入栈顺序的中右改为右中 zhan.pop(); zhan.push(rif[tmp]); zhan.push(tmp); rif[tmp] = 0; } else { cout << tmp << " "; zhan.pop(); } } cout << endl; //后序遍历 lef.assign(le.begin(), le.end()); rif.assign(ri.begin(), ri.end()); zhan.push(1); while (!zhan.empty()) { int tmp = zhan.top(); if (lef[tmp]) { zhan.push(lef[tmp]); lef[tmp] = 0; } else if (rif[tmp]) { zhan.push(rif[tmp]); rif[tmp] = 0; } else { cout << tmp << " "; zhan.pop(); } } cout << endl; //层序遍历使用队列 lef.assign(le.begin(), le.end()); rif.assign(ri.begin(), ri.end()); queue<int>que; que.push(1);//第一层根节点1 while (!que.empty()) { int tmp = que.front(); que.pop(); if (lef[tmp]) { que.push(lef[tmp]); } if (rif[tmp]) { que.push(rif[tmp]); } cout << tmp << " "; } cout << endl; system("pause"); return 0; }