二叉树，是数据结构这门课的重要知识点，也是考研必考的知识点。关于二叉树的遍历算法， 主要有前序遍历，中序遍历，后序遍历，层序遍历。本文着重介绍前序遍历，中序遍历，后序遍历这三种算法。树的遍历，一般都是递归遍历，本文也采用递归遍历实现。为了更好的掌握算法，建议大家上机调试，这样掌握的更牢固。

#include <stdio.h>

#include <stdlib.h>

#include <malloc.h>

#define OK 1

#define ERROR 0

#define NULL 0

#define OVERFLOW -2

typedef int Status;

typedef char TElemType;

/*二叉树的二叉链表存储表示*/

typedef struct BiTNode{

TElemType data;

struct BiTNode *lchild, *rchild; //左右孩子指针

}BiTNode, *BiTree;

/*建立二叉链表*/

Status CreateBiTree(BiTree &T){

//按先序次序输入二叉树中结点值，空格表示空树

//构造二叉链表表示的二叉树

char ch;

scanf("%c",&ch);

//ch=getchar();

if(ch==' ')

T=NULL;

else

{

if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);

T->data=ch;

CreateBiTree(T->lchild);

CreateBiTree(T->rchild);

}

return OK;

}

/*打印二叉树的内容*/

Status PrintElement(char ch)

{

printf("%c",ch);

return OK;

}

/*先序遍历二叉树，递归算法*/

Status PreOrderTraverse(BiTree T,Status(*PrintElement)(TElemType e))

{

if(T)

{

if(PrintElement(T->data))

if(PreOrderTraverse(T->lchild,PrintElement))

if(PreOrderTraverse(T->rchild,PrintElement))

return OK;

return ERROR;

}

else return OK;

}

/*中序遍历二叉树，递归算法*/

Status InOrderTraverse(BiTree T,Status(*PrintElement)(TElemType e))

{

if(T)

{

if(InOrderTraverse(T->lchild,PrintElement))

if(PrintElement(T->data))

if(InOrderTraverse(T->rchild,PrintElement))

return OK;

return ERROR;

}

else return OK;

}

/*后序遍历二叉树，递归算法*/

Status PostOrderTraverse(BiTree T,Status(*PrintElement)(TElemType e))

{

if(T)

{

if(PostOrderTraverse(T->lchild,PrintElement))

if(PostOrderTraverse(T->rchild,PrintElement))

if(PrintElement(T->data))

return OK;

return ERROR;

}

else return OK;

}

int main()

{ BiTree T;

printf("请输入二叉树:");

printf("\n");

CreateBiTree(T);

printf("先序遍历:");

printf("\n");

PreOrderTraverse(T,PrintElement);

printf("\n");

printf("中序遍历:");

printf("\n");

InOrderTraverse(T,PrintElement);

printf("\n");

printf("后序遍历:");

printf("\n");

PostOrderTraverse(T,PrintElement);

printf("\n");

return 0;

}

想了解最新考研资讯和院校指导，点击上方头像关注我，或给我发私信，也可关注上方图片右下角的账号，为你提供最新考研干货。