二叉树的遍历方式
前序遍历(Preorder)
前序遍历就是先访问根节点，再访问左子节点，最后访问右子节点的遍历方式
中序遍历(Inorder)
中序遍历是先访问左子节点，再访问根节点，最后访问右子节点的遍历方式
后序遍历(Postorder)
后序遍历是先访问左子节点，再访问右子节点，最后访问根节点的遍历方式
二叉树的遍历
二叉树的遍历可以通过递归来实现。递归终止的条件是当前节点为空节点，然后返回。前中后序遍历的递归函数不同之处只是输出当前节点的那条语句不同。
题目
假设二叉树有n个节点，编号分别为0至n-1。
输入数据第一行给出节点数，然后接下来的n行按以下个数给出节点信息：
id left right
id为节点编号，left为左子结点编号，right为右子结点编号。当结点不存在时，编号为-1
题目在
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_C
样例输入
代码语言：javascript复制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样例输出
代码语言：javascript复制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代码实现
代码语言：javascript复制#include<iostream>
using namespace std;
#define MAX 25
#define NIL -1
struct Node
{
int parent;
int left;
int right;
};
Node T[MAX];
int n,root;
void preorder(int id)
{
cout<<" "<<id;
if(T[id].left!=NIL)
{
preorder(T[id].left);
}
if(T[id].right !=NIL)
{
preorder(T[id].right);
}
}
void inorder(int id)
{
if(T[id].left!=NIL)
{
inorder(T[id].left);
}
cout<<" "<<id;
if(T[id].right !=NIL)
{
inorder(T[id].right);
}
}
void Postorder(int id)
{
if(T[id].left!=NIL)
{
Postorder(T[id].left);
}
if(T[id].right !=NIL)
{
Postorder(T[id].right);
}
cout<<" "<<id;
}
int main()
{
for(int i=0;i<MAX;i )
{
T[i].parent = NIL;
T[i].left = NIL;
T[i].right = NIL;
}
cin>>n;
for(int i=0;i<n;i )
{
int id,left,right;
cin>>id>>left>>right;
T[id].left = left;
T[id].right = right;
T[left].parent = id;
T[right].parent = id;
}
for(int i=0;i<n;i )
{
if(T[i].parent == NIL)
{
root = i;
break;
}
}
cout<<"Preorder"<<endl;
preorder(root);
cout<<endl<<"Inorder"<<endl;
inorder(root);
cout<<endl<<"Postorder"<<endl;
Postorder(root);
cout<<endl;
}注意事项
二叉树的遍历会对每一个节点进行访问，因此时间复杂度为O(n)。使用递归实现遍历算法的时候要注意，一旦树的结点数量庞大且分布不均匀，那么就很可能导致递归深度过深，最终堆栈溢出，boom~
