⼆叉树的前序遍历、中序遍历、后序遍历、层序遍历的时间复杂度和空间复杂度
⾮递归版：
由于不管是先序遍历还是中序遍历以及后序遍历，我们都需要利⽤⼀个辅助栈来进⾏每个节点的存储打印，所以每个节点都要进栈和出栈，不过是根据那种遍历⽅式改变的是每个节点的进栈顺序，所以时间复杂度为O(n)，同样空间复杂度也为O(n)，n为结点数。
层序遍历是通过队列来进⾏每个节点的存储打印的，所以时间复杂度和空间复杂度也与前三种遍历⽅式⼀样。
递归版：
空间复杂度与系统堆栈有关，系统栈需要记住每个节点的值，所以空间复杂度为O(n)。时间复杂度应该为O(n)，根据公
式T(n)=2T(n/2)+1=2(2T(n/4)+1)+1=2^logn+2^(logn-1)+...+2+1 ~= n，所以时间复杂度为O(n)。
相关代码如下（包括递归版和⾮递归版）
BiTree.h:
#pragma once
typedef char TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode* Ichild,* rchild;
}BiTNode,*BiTree;
int CreateBiTree(BiTree& T);//先序构造⼆叉树
int PreOrderTraverse(BiTree T);//先序遍历⼆叉树
int InOrderTraverse(BiTree T);//中序遍历⼆叉树
int PostOrderTraverse(BiTree T);//后序遍历⼆叉树
int LevelOrderTraverse(BiTree T);//层序遍历⼆叉树
int PreOrderTraverse1(BiTree T);//先序遍历⼆叉树，⾮递归版
int InOrderTraverse1(BiTree T);//中序遍历⼆叉树，⾮递归版
int PostOederTraverse1(BiTree T);//后序遍历⼆叉树，⾮递归版
BiTree.cpp:
#include"BitTree.h"
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
int CreateBiTree(BiTree& T)
{
TElemType e;
cin >> e;
if(e =='#')//#表⽰空树
T =NULL;
else
{
T =(BiTNode*)malloc(sizeof(BiTNode));
if(!T)
exit(0);
else
{
T->data = e;//⽣成根节点
CreateBiTree(T->Ichild);//构造左⼦树
CreateBiTree(T->rchild);//构造右⼦树
}
}
return1;
}
int PreOrderTraverse(BiTree T)//前序遍历
{
if(T){//判T是否为空树
cout << T->data;//输出T节点的数据
if(PreOrderTraverse(T->Ichild));//递归遍历左⼦树
if(PreOrderTraverse(T->rchild));//递归遍历右⼦树
if(PreOrderTraverse(T->rchild));//递归遍历右⼦树
return0;
}
else
return1;
}
int InOrderTraverse(BiTree T)//中序遍历
{
if(T){//判T是否为空树，递归边界
if(InOrderTraverse(T->Ichild));//递归遍历左⼦树
cout << T->data;//输出T节点的数据
if(InOrderTraverse(T->rchild));//递归遍历右⼦树
return0;
}
else
return1;
}
int PostOrderTraverse(BiTree T)//后序遍历
{
if(T){//判T是否为空树
if(PostOrderTraverse(T->Ichild));//递归遍历左⼦树
if(PostOrderTraverse(T->rchild));//递归遍历右⼦树
cout << T->data;//输出T节点的数据
return0;
}
else
return1;
}
int LevelOrderTraverse(BiTree T)//层序遍历
{
if(T ==NULL)
return0;
queue<BiTree> Q;
Q.push(T);//把根结点推⼊
while(!Q.empty())//循环结束之后再次判断，直到队列为空
{
cout << Q.front()->data;
if(Q.front()->Ichild!=NULL)//左节点进队列
Q.push(Q.front()->Ichild);
if(Q.front()->rchild !=NULL)//右节点进队列
Q.push(Q.front()->rchild);
Q.pop();//队头出列
}
cout << endl;
return1;
}
int PreOrderTraverse1(BiTree T)//前序遍历
{
/*
对于任⼀结点P：
1)访问结点P，并将结点P⼊栈;
2)判断结点P的左孩⼦是否为空，若为空，则取栈顶结点并进⾏出栈操作，并将栈顶结点的右孩⼦置为当前的结点P，循环⾄1)；若不为空，则将P的左孩⼦置为当前的结点P;
3)直到P为NULL并且栈为空，则遍历结束。
*/
stack<BiTree> s;
BiTree p = T;//根节点
while(p !=NULL||!s.empty())
{
while(p !=NULL)//根左右
{
cout << p->data;
s.push(p);
s.push(p);
p = p->Ichild;
}
if(!s.empty())
{
p = s.top();//得到根节点
s.pop();//根节点出栈
p = p->rchild;//
}
}
return0;
}
int InOrderTraverse1(BiTree T)//中序遍历
{
/*
对于任⼀结点P：
1)若其左孩⼦不为空，则将P⼊栈并将P的左孩⼦置为当前的P，然后对当前结点P再进⾏相同的处理；
2)若其左孩⼦为空，则取栈顶元素并进⾏出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩⼦；
3)直到P为NULL并且栈为空则遍历结束
*/
stack<BiTree> s;
BiTree p = T;
while(p !=NULL||!s.empty())
{
while(p !=NULL)
{
s.push(p);
p = p->Ichild;
}
if(!s.empty())
{
p = s.top();//得到最底端的左节点
cout << p->data;//输出节点值
s.pop();
p = p->rchild;
}
}
return0;
}
先序中序后序遍历二叉树int PostOederTraverse1(BiTree T)//后序遍历
{
/*
要保证根结点在左孩⼦和右孩⼦访问之后才能访问，因此对于任⼀结点P，先将其⼊栈。如果P不存在左孩⼦和右孩⼦，则可以直接访问它；
或者P存在左孩⼦或者右孩⼦，但是其左孩⼦和右孩⼦都已被访问过了，则同样可以直接访问该结点。
若⾮上述两种情况，则将P的右孩⼦和左孩⼦依次⼊栈，这样就保证了每次取栈顶元素的时候，左孩⼦在右孩⼦前⾯被访问，左孩⼦和右孩⼦都在根结点前⾯被访问。
*/
stack<BiTree> s;
BiTree cur;//当前结点
BiTree pre =NULL;//前⼀次访问的结点
s.push(T);//根节点出栈
while(!s.empty())
{
cur = s.top();
if((cur->Ichild ==NULL&& cur->rchild ==NULL)||
(pre !=NULL&&(pre == cur->Ichild || pre == cur->rchild)))
{
cout << cur->data;//当前结点没有孩⼦节点或孩⼦节点都已经被访问了
s.pop();
pre = cur;
}
else
{
if(cur->rchild !=NULL)
s.push(cur->rchild);//右孩⼦先进栈
if(cur->Ichild !=NULL)
if(cur->Ichild !=NULL)
s.push(cur->Ichild);//左孩⼦后进栈，保证在取栈顶元素时，左孩⼦在右孩⼦之前被访问}
}
return0;
}
test.cpp:
#include"BitTree.h"
#include<iostream>
using namespace std;
int main()
{
cout <<"输⼊⼆叉树：";
BiTree T;
CreateBiTree(T);
cout <<"先序遍历（递归）：\t";
PreOrderTraverse(T);
cout <<"\n先序遍历（⾮递归）：\t";
PreOrderTraverse1(T);
cout <<"\n中序遍历（递归）：\t";
InOrderTraverse(T);
cout <<"\n中序遍历（⾮递归）：\t";
InOrderTraverse1(T);
cout <<"\n后序遍历（递归）：\t";
PostOrderTraverse(T);
cout <<"\n后序遍历（⾮递归）：\t";
PostOederTraverse1(T);
cout <<"\n层序遍历（⾮递归）：\t";
LevelOrderTraverse(T);
//ABC##DE#G##F###
system("pause");
}
运⾏结果如下：