二叉树的先序，中序，后序遍历的实现_二叉树的先序,中序,后序遍历的实现

先序遍历
若二叉树为空，则空操作；否则
1.访问根节点
2.先序遍历左子树
3.先序遍历右子树

中序遍历
若二叉树为空，则空操作；否则
1.中序遍历左子树
2.访问根节点
3.中序遍历右子树

后序遍历
若二叉树为空，则空操作；否则
1.后序遍历左子树
2.后序遍历右子树
3.访问根节点

用递归的方式实现二叉树的遍历：

#include <bits/stdc++.h>
using namespace std;
typedef char TElemType;
typedef int Status;
//用二叉链表存储表示二叉树
typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild, *rchild;
}*BiTree, BiTNode;

//构造空二叉树
void InitBiTree(BiTree T)
{
	T=(BiTree)malloc(sizeof(BiTNode));
	if(!(T)) exit(OVERFLOW);
	T->lchild=NULL;
	T->rchild=NULL;
	return ;
}
//前序遍历二叉树
void CreateBiTreePreOrder(BiTree &T){
    TElemType ch;
	ch = getchar();
	getchar();
	if(ch =='#'){
        T = NULL;
	}
    else{
        T= (BiTree)malloc(sizeof(BiTNode));
        if(!T) exit(OVERFLOW);
		T->data = ch;
		CreateBiTreePreOrder(T->lchild);
		CreateBiTreePreOrder(T->rchild);
	}
}
//递归的先序遍历
void PreOrder(BiTree T){
	if(T){
		cout<<T->data<<" ";
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}
//递归的中序遍历
void InOrder(BiTree T){
	if(T){
        InOrder(T->lchild);
		cout<<T->data<<" ";
		InOrder(T->rchild);
	}
}
//递归的后序遍历 
void PostOrder(BiTree T){
	if(T){
        PostOrder(T->lchild);
		cout<<T->data<<" ";
		PostOrder(T->rchild);
	}
}
int main()
{
    BiTree T;
    InitBiTree(T);
    CreateBiTreePreOrder(T);
    cout<<"前序遍历为:"<<endl;
    PreOrder(T);
    cout<<endl;
    cout<<"中序遍历为:"<<endl;
    InOrder(T);
    cout<<endl;
    cout<<"后序遍历为:"<<endl;
    PostOrder(T);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75