二叉树的创建和释放以及各种遍历方法(递归和非递归)
好久不看数据结构,感觉很多东西都有点生疏了,这两天趁着不是特别忙抽时间把有关二叉树的知识复习了一下,并用代码实现了一遍。主要功能有二叉树的创建和释放、前序遍历(递归和非递归两种方式)、中序遍历(递归和非递归两种方式)、后序遍历(递归和非递归两种方式)、层次遍历(递归和非递归两种方式)。
代码:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<stack>
#define MAX(X,Y) ((X) > (Y) ? (X) : (Y))
typedef char dataType;
typedef struct BiTNode
{
dataType data;
struct BiTNode *lchild;
struct BiTNode *rchild;
}BiTNode, *BiTree;
void printInfo(dataType data, int level=-1)
{
if(level >= 0)
printf("%c在第%d层 ",data,level);
else
printf("%c ",data);
}
//获取树的深度
int GetTreeDeep(BiTree T)
{
if(T == NULL)
return 0;
int lDeep = GetTreeDeep(T->lchild);
int rDeep = GetTreeDeep(T->rchild);
return MAX(lDeep,rDeep)+1;
}
//前序创建树
void CreateTree(BiTree *T)
{
dataType c;
scanf("%c",&c);
if(c == '\n')
return;
if(c == '#')
*T = NULL;
else
{
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = c;
//创建左子树
CreateTree(&(*T)->lchild);
//创建右子树
CreateTree(&(*T)->rchild);
}
}
//前序遍历(根左右) 递归
void PreOrderTraversal_re(BiTree T,int level=-1)
{
if(T == NULL)
return;
printInfo(T->data, level);
PreOrderTraversal_re(T->lchild, (level<0?level:level+1));
PreOrderTraversal_re(T->rchild, (level<0?level:level+1));
}
//中序遍历(左根右) 递归
void MiddOrderTraversal_re(BiTree T,int level=-1)
{
if(T == NULL)
return;
MiddOrderTraversal_re(T->lchild, (level<0?level:level+1));
printInfo(T->data, level);
MiddOrderTraversal_re(T->rchild, (level<0?level:level+1));
}
//后序遍历(左右根) 递归
void PostOrderTraversal_re(BiTree T,int level=-1)
{
if(T == NULL)
return;
PostOrderTraversal_re(T->lchild, (level<0?level:level+1));
PostOrderTraversal_re(T->rchild, (level<0?level:level+1));
printInfo(T->data, level);
}
//层序遍历 递归
//先找出树的深度再遍历
void PrintLevelOrderTraversal(BiTree T,int level)
{
if(T==NULL || level<1)
return;
if(level == 1)
printInfo(T->data);
PrintLevelOrderTraversal(T->lchild, level-1);
PrintLevelOrderTraversal(T->rchild, level-1);
}
void LevelOrderTraversal_re(BiTree T)
{
if(T == NULL)
return;
//找出树的深度
int deep = GetTreeDeep(T);
for(int i=1;i<=deep;i++)
PrintLevelOrderTraversal(T, i);
}
//前序遍历 非递归
void PreOrderTraversal_Nre(BiTree T)
{
if(T == NULL)
return;
std::stack<BiTree> sBT;
BiTree p = T;
while(p || !sBT.empty())
{
if(p != NULL)
{
sBT.push(p);
printInfo(p->data);
p = p->lchild;
}
else
{
p = sBT.top();
sBT.pop();
p = p->rchild;
}
}
}
//中序遍历 非递归
void MiddOrderTraversal_Nre(BiTree T)
{
if(T == NULL)
return;
std::stack<BiTree> sBT;
BiTree p = T;
while(p || !sBT.empty())
{
if(p != NULL)
{
sBT.push(p);
p = p->lchild;
}
else
{
p = sBT.top();
sBT.pop();
printInfo(p->data);
p = p->rchild;
}
}
}
//后序遍历 非递归
void PostOrderTraversal_Nre(BiTree T)
{
if(T == NULL)
return;
std::stack<BiTree> sBT;
BiTree p1 = T->lchild,p2 = NULL;
bool leftvisited = true; //左子树是否访问过标记
sBT.push(T);
while(!sBT.empty())
{
while(p1 != NULL) //将左子树压入栈中
{
sBT.push(p1);
p1 = p1->lchild;
}
leftvisited = true;
p2 = NULL;
while(!sBT.empty() && leftvisited) //如果左子树已经访问过,则遍历访问右子树
{
p1 = sBT.top(); //从栈里取出根节点
if(p1->rchild == p2) //如果右子树为空或已访问过,则输出根节点信息并将根节点从栈里删除
{
sBT.pop();
printInfo(p1->data);
p2 = p1;
}
else //否则进入右子树,并将右子树下的左子树标记为未访问
{
p1 = p1->rchild;
leftvisited = false;
}
}
}
}
//层次遍历 非递归
void LevelOrderTraversal_Nre(BiTree T)
{
if(T == NULL)
return;
std::queue<BiTree> qBT;
BiTree p = T;
qBT.push(p);
while(!qBT.empty())
{
p = qBT.front();
qBT.pop();
printInfo(p->data);
if(p->lchild != NULL)
qBT.push(p->lchild);
if(p->rchild != NULL)
qBT.push(p->rchild);
}
}
//释放二叉树
void FreeBiTree(BiTree T)
{
if(T == NULL)
return;
if(T->lchild != NULL)
{
FreeBiTree(T->lchild);
T->lchild = NULL;
}
if(T->rchild != NULL)
{
FreeBiTree(T->rchild);
T->rchild = NULL;
}
free(T);
T = NULL;
}
int main()
{
//测试样例
//ABDG##H###CE#I##F##
//1247##8###35#9##6##
BiTree T = NULL;
int level = 1;
printf("创建二叉树...\n");
CreateTree(&T);
printf("创建完成\n");
printf("前序递归遍历:\n");
PreOrderTraversal_re(T, level);
printf("\n");
printf("中序递归遍历:\n");
MiddOrderTraversal_re(T, level);
printf("\n");
printf("后序递归遍历:\n");
PostOrderTraversal_re(T, level);
printf("\n");
printf("层次递归遍历:\n");
LevelOrderTraversal_re(T);
printf("\n");
printf("前序非递归遍历:\n");
PreOrderTraversal_Nre(T);
printf("\n");
printf("中序非递归遍历:\n");
MiddOrderTraversal_Nre(T);
printf("\n");
printf("后序非递归遍历:\n");
PostOrderTraversal_Nre(T);
printf("\n");
printf("层次非递归遍历:\n");
LevelOrderTraversal_Nre(T);
printf("\n");
printf("释放二叉树...\n");
FreeBiTree(T);
printf("释放完成\n");
system("pause");
return 0;
}
结果截图: