二叉树的前、中、后、层序遍历算法实现

实现代码

二叉树图

#include
using namespace std;

typedef char ElemType;
//二叉树的定义 
typedef struct BTreeNode{
	ElemType data;
	struct	BTreeNode *left;//左孩子
	struct	BTreeNode *right;//右孩子
}BTreeNode;

//队列中结点的定义 
typedef struct qnode {
	BTreeNode *data;
	struct qnode *next;
}LQNode;
//队列的定义 
typedef struct {
	LQNode *front;//队头指针
	LQNode *rear;//队尾指针
}LQueue;

//二叉树初始化
void BTreeInit(BTreeNode *root){
	root=(BTreeNode *)malloc(sizeof(BTreeNode));
	root->left=NULL;
	root->right=NULL;
}
 
//添加左孩子 
int addLeftKid(BTreeNode *btNode,ElemType ldata) {
	//分配新结点
	BTreeNode * lNode=(BTreeNode *)malloc(sizeof(BTreeNode));
	//初始化结点数据
	lNode->data=ldata;
	//cout<data<<" ";
	lNode->left=NULL;
	lNode->right=NULL;
	//将当前初始化的结点添加到父节点之下
	btNode->left=lNode;
	return 1;	
}	

//添加右孩子 
int addRightKid(BTreeNode *btNode,ElemType rdata) {
	//分配新结点
	BTreeNode * rNode=(BTreeNode *)malloc(sizeof(BTreeNode));
	//初始化结点数据
	rNode->data=rdata;
	//cout<data<<" ";
	rNode->left=NULL;
	rNode->right=NULL;
	//将当前初始化的结点添加到父节点之下
	btNode->right=rNode;
	return 1;	
}

//访问结点数据 
void visit(BTreeNode *btNode){
	cout<<btNode->data<<" ";
}

//前序遍历 根左右 
void preOrder(BTreeNode *btNode){
	if(btNode==NULL){
		return;
	}
	visit(btNode);
	preOrder(btNode->left);
	preOrder(btNode->right);
}

//中序遍历  左根右
void midOrder(BTreeNode *btNode){
	if(btNode==NULL){
		return;
	}
	midOrder(btNode->left);
	visit(btNode);
	midOrder(btNode->right);
}

//后序遍历  左右根
void afterOrder(BTreeNode *btNode){
	if(btNode==NULL){
		return;
	}
	afterOrder(btNode->left);
	afterOrder(btNode->right);
	visit(btNode);
}

//队列初始化
void QueueInit(LQueue *Q) {
	Q->front=NULL;
	Q->rear=NULL;	
}

//入队
void EnQueue(LQueue *Q,BTreeNode *btNode) {
	//cout<data<<" ";
	//申请一个新的队列结点 
	LQNode* p=(LQNode *)malloc(sizeof(LQNode));
	//将当前的二叉树结点入队
	p->data= btNode;
	//cout<data->data<<" ";
	p->next=NULL;
	if(Q->rear!=NULL)//队尾不空，也就是当前队列不为空
		Q->rear->next=p;//将当前新申请的结点入队
	Q->rear=p;//将p更改为队尾指针	
	if(Q->front==NULL)//如果队列为空，将p修改为队头指针 脑子一热在if里面少写了个等号，改bug改了一下午，艹 
		Q->front=p; 
	//cout<rear->data->data<<" ";
}

//出队
int  OutQueue(LQueue *Q,BTreeNode * &btNode) {
	LQNode *p;
	if(Q->front==NULL){
		cout<<"当前队头为空，队列已无数据!"<<endl;
		return 0;
	}
	btNode=Q->front->data;
	//cout<<*(btNode->data)<<" ";

	p=Q->front;
	//当前队头为队头下一个元素，将当前队头出队 
	Q->front=Q->front->next;
	/*如果当前队头为空，也就是
	说队头之后下一个元素为空，
	删除最后一个结点，将尾指针置空。 
	*/ 
	if(Q->front==NULL){
		//cout<<"当前队头为空！";
		Q->rear=NULL;
	}
		
	//free(p);
	return 1;
}

//判断队列是否为空
int isEmpty(LQueue Q) {
	return (Q.front==NULL)?1:0;
}

//二叉树的层次遍历 
void LevelOrder(LQueue *Q,BTreeNode *btNode){
	BTreeNode *p;
	EnQueue(Q,btNode);
	//out<<"2"<
	//cout<front->data->data<<" ";
	while(!isEmpty(*Q)){
		//cout<<"1"<
		OutQueue(Q,p);
		//cout<data<<" ";
		visit(p);
		//cout<left->data<<" "		;
		if(p->left!=NULL)
		{
			EnQueue(Q,p->left);
			//EnQueue(Q,p->right);
		}			
		if(p->right!=NULL){
			//EnQueue(Q,p->left);
			EnQueue(Q,p->right);
		}	
	}
}

int main() {
	char a[]={'A','B','C','D','E','F','G'};
	BTreeNode root;//根节点
	BTreeInit(&root);
	root.data='A' ;
	addLeftKid(&root,'B');
	addRightKid(&root,'C');
	//给'B'添加左右孩子 
	addLeftKid(root.left,'D');
	addRightKid(root.left,'E');
	//给'C'添加左右孩子 
	addLeftKid(root.right,'F');
	addRightKid(root.right,'G');

	cout<<"前序遍历结果为:";
	preOrder(&root);
	cout<<"\n中序遍历结果为:";
	midOrder(&root);
	cout<<"\n后序遍历结果为:";
	afterOrder(&root);
	cout<<endl;
	cout<<"层序遍历结果为:";
	
	LQueue Q;
	QueueInit(&Q);
	LevelOrder(&Q,&root);
	//cout<left->data;
	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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200

运行结果