树的遍历【东北大学oj数据结构7-3】C++

题面

二叉树是递归定义的。二叉树 T 是定义在有限节点集上的结构
不包含节点，或者由三个不相交的节点集组成：

一个根节点。
称为左子树的二叉树。
称为右子树的二叉树。
您的任务是编写一个程序，该程序基于以下算法执行树遍历（系统地遍历树中的所有节点）：

打印根、左子树和右子树（前序）。
打印左子树、根和右子树（中序）。
打印左子树、右子树和根（后序）。
这里，给定的二叉树由 n 个节点组成，每个节点都有一个从0到n-1的唯一ID。

输入

输入的第一行包括一个整数 n，即树的节点数。
在接下来的 n 行中，每个节点的信息以以下格式给出：
id left right
id 是节点的ID，left 是左孩子的ID，right 是右孩子的ID。如果节点没有左（右）子节点，左（右）用-1表示

输出

在第一行，打印“Preorder”，在第二行，打印通过前序遍历获得的节点 ID 列表。
在第 3 行打印“Inorder”，在第 4 行打印通过中序遍历获得的节点 ID 列表。
在第 5 行打印“Postorder”，在第 6 行打印通过后序遍历获得的节点 ID 列表。

在每个节点 ID 之前打印一个空格字符。

Constraints
1 ≤ n ≤ 25

输入样例

9
0 1 4
1 2 3
2 -1 -1
3 -1 -1
4 5 8
5 6 7
6 -1 -1
7 -1 -1
8 -1 -1

输出样例

Preorder
0 1 2 3 4 5 6 7 8
Inorder
2 1 3 0 6 5 7 4 8
Postorder
2 3 1 6 7 5 8 4 0

递归实现

#include <iostream>using namespace std;#define MAX 30// 定义树的节点结构
struct Node {int p, l, r;
};struct Node T[MAX];  // 树节点数组
int n;  // 节点的数量void preorder(int root)
{if(root==-1) return;cout<<root<<" ";preorder(T[root].l);preorder(T[root].r);
}
void inorder(int root)
{if(root==-1) return;inorder(T[root].l);cout<<root<<" ";inorder(T[root].r);
}
void posorder(int root)
{if(root==-1) return;posorder(T[root].l);posorder(T[root].r);cout<<root<<" ";
}int main() {int i, v, l, r;scanf("%d", &n);for (i = 0; i < n; i++) {T[i].p = T[i].l = T[i].r = -1;}for (i = 0; i < n; i++) {scanf("%d %d %d", &v, &l,&r);if(l!=-1){T[v].l=l;T[l].p=v;}if(r!=-1){T[v].r=r;T[r].p=v;}}for (int i = 0; i < n; i++) {if(T[i].p==-1){r=i;break;}}cout<<"Preorder"<<endl;preorder(r);cout<<endl;cout<<"Inorder"<<endl;inorder(r);cout<<endl;cout<<"Postorder"<<endl;posorder(r);cout<<endl;return 0;
}

非递归实现

#include <iostream>
#include <stack>
using namespace std;#define MAX 30// 定义树的节点结构
struct Node {int p, l, r;
};struct Node T[MAX];  // 树节点数组
int n;  // 节点的数量void preorder(int root)
{if(root==-1) return;stack<int> s;s.push(root);while(!s.empty()){int node=s.top();s.pop();cout<<node<<" ";if(T[node].r!=-1)s.push(T[node].r);if(T[node].l!=-1)s.push(T[node].l);}
}
void inorder(int root)
{if(root==-1) return;stack<int> s;int current=root;while(!s.empty()||current!=-1){while(current!=-1){s.push(current);current=T[current].l;}current=s.top();s.pop();cout<<current<<" ";current=T[current].r;}
}
void posorder(int root)
{if(root==-1) return;stack<int> s1,s2;s1.push(root);while(!s1.empty()){int node=s1.top();s1.pop();s2.push(node);if(T[node].l!=-1)s1.push(T[node].l);if(T[node].r!=-1)s1.push(T[node].r);}while(!s2.empty()){cout<<s2.top()<<" ";s2.pop();}
}int main() {int i, v, l, r;scanf("%d", &n);for (i = 0; i < n; i++) {T[i].p = T[i].l = T[i].r = -1;}for (i = 0; i < n; i++) {scanf("%d %d %d", &v, &l,&r);if(l!=-1){T[v].l=l;T[l].p=v;}if(r!=-1){T[v].r=r;T[r].p=v;}}for (int i = 0; i < n; i++) {if(T[i].p==-1){r=i;break;}}cout<<"Preorder"<<endl;preorder(r);cout<<endl;cout<<"Inorder"<<endl;inorder(r);cout<<endl;cout<<"Postorder"<<endl;posorder(r);cout<<endl;return 0;
}