（C语言版）二叉树遍历算法——包含递归前、中、后序和层次，非递归前、中、后序和层次遍历共八种

时间：2021-11-20 22:02:19

        首先，要感谢网上的参考资料。

  1. http://mengliao.blog.51cto.com/876134/1178079（作者：BlackAlpha）
  2. http://blog.csdn.net/fzh1900/article/details/14056735（作者：_云淡风轻）
  3. http://blog.csdn.net/stpeace/article/details/8138458（作者：stpeace）

       二叉树是使用的比较广泛的一种数据结构，这里我写了二叉树的相关操作，包括初始化、新建、以及遍历。这里主要是为了学习二叉树的遍历算法，我总结后，写了八种二叉树的遍历算法，分别是：

      1.递归先序遍历
      2.递归中序遍历
      3.递归后序遍历
      4.非递归先序遍历（单栈辅助）
      5.非递归中序遍历（单栈辅助）
      6.非递归后序遍历（单栈辅助）
      7.递归层次遍历
      8.非递归层次遍历（队列辅助）
       当然，这里还要用到栈和队列，博客中以前有提到过（链式的栈和链式队列），其实还可以用顺序栈和顺序队列的（博客中后面将补上这块）。下面直接上代码：
LinkStack.h 链式栈头文件 
#ifndef _LINK_STACK_H_H
#define _LINK_STACK_H_H

#include "BiTree.h"

typedef pBiTree LStackEle; 

typedef struct LSNODE
{
LStackEle ele;
struct LSNODE *pnext;
}LSNode, *pLSNode;

typedef struct LSTACK
{
pLSNode top;
}LStack, *pLStack;

//栈初始化
void InitLinkStack(LStack &s);

//入栈
void PushLinkStack(LStack &s, LStackEle ele);

//出栈
void PopLinkStack(LStack &s, LStackEle &ele);

//判断栈是否为空
bool IsemptyLinkStack(LStack s);

//获得栈顶值
LStackEle GetTopLinkStack(LStack s);

#endif
LinkQueue.h 链式队列头文件 
#ifndef _LINK_QUEUE_H_H
#define _LINK_QUEUE_H_H

#include "BiTree.h"

typedef pBiTree LQueueEle;

typedef struct LQNODE
{
LQueueEle ele;
struct LQNODE *pnext;
}LQNode, *pLQNode;

typedef struct LQUEUE
{
pLQNode rear;
pLQNode front;
}LQueue, *pLQueue;

//初始化队列
void InitLinkQueue(LQueue &q);

//入队
void EnLinkQueue(LQueue &q, LQueueEle ele);

//出队
void DeLinkQueue(LQueue &q, LQueueEle &ele);

//判断队列是否为空
bool IsemptyLinkQueue(LQueue q);

//获得队头元素值
LQueueEle GetFrontLinkQueue(LQueue q);

#endif

BiTree.h 二叉树头文件 
#ifndef _BITREE_H_H
#define _BITREE_H_H

typedef struct BINODE
{
int ele;
struct BINODE *plchild;
struct BINODE *prchild;
}BiNode, *pBiTree;

//初始化二叉树（含根节点）
void InitBiTree(pBiTree &bt, int ele);

//创建二叉树节点
BiNode *CreateBiTreeNode(pBiTree lchild, pBiTree rchild, int ele);

//插入左子二叉树
void InsertLChild(pBiTree parent, pBiTree lchild);

//插入右子二叉树
void InsertRChild(pBiTree parent, pBiTree rchild);

//计算二叉树的深度
int DeepBiTree(pBiTree bt);

//递归先序遍历
void RePreOrderTraverse(pBiTree bt); 

//递归中序遍历
void ReInOrderTraverse(pBiTree bt);

//递归后序遍历
void RePostOrderTraverse(pBiTree bt);

//非递归先序遍历二
void NonRePreOrderTraverse(pBiTree bt);

//非递归中序遍历
void NonReInOrderTraverse(pBiTree bt);

//非递归后序遍历
void NonRePostOrderTraverse(pBiTree bt);

//非递归层次遍历
void NonReLevelOrderTraverse(pBiTree bt);

//递归层次遍历
void ReLevelOrderTraverse(pBiTree bt);

void PrintLevelNode(pBiTree bt, int level);

#endif

LinkStack.cpp 链式栈源文件 
#include "LinkStack.h"
#include <stdlib.h>
#include <stdio.h>

//栈初始化
void InitLinkStack(LStack &s)
{
s.top= NULL;
}

//入栈
void PushLinkStack(LStack &s, LStackEle ele)
{
pLSNode pnew = (pLSNode)malloc(sizeof(LSNode));
if (pnew == NULL)
{
printf("内存分配失败！\n");
exit(EXIT_FAILURE);
}

pnew->ele = ele;
pnew->pnext = s.top;
s.top = pnew;
}

//出栈
void PopLinkStack(LStack &s, LStackEle &ele)
{
pLSNode pt = NULL;
if (IsemptyLinkStack(s))
{
printf("栈为空，不能出栈操作！\n");
exit(EXIT_FAILURE);
}
else
{
ele = s.top->ele;
pt = s.top;
s.top = pt->pnext;
free(pt);
pt = NULL;
}

}

//判断栈是否为空
bool IsemptyLinkStack(LStack s)
{
if (s.top == NULL)
return true;
else
return false;
}

//获得栈顶元素
LStackEle GetTop(LStack s)
{
if (IsemptyLinkStack(s))
{
printf("栈为空，不能获得栈顶元素值！\n");
exit(EXIT_FAILURE);
}
else
return s.top->ele;
}
LinkQueue.cpp 链式队列源文件 
#include <stdlib.h>
#include <stdio.h>
#include "LinkQueue.h"

//初始化队列
void InitLinkQueue(LQueue &q)
{
q.front = (pLQNode)malloc(sizeof(LQNode));
if (q.front == NULL)
{
printf("内存分配失败！\n");
exit(EXIT_FAILURE);
}

q.rear = q.front;
}

//入队
void EnLinkQueue(LQueue &q, LQueueEle ele)
{
pLQNode pnew = (pLQNode)malloc(sizeof(LQNODE));
if (pnew == NULL)
{
printf("内存分配失败！\n");
exit(EXIT_FAILURE);
}

pnew->ele = ele;
pnew->pnext = NULL;
q.rear->pnext = pnew;
q.rear = pnew;
}

//出队
void DeLinkQueue(LQueue &q, LQueueEle &ele)
{
pLQNode pt = NULL;

if (IsemptyLinkQueue(q))
{
printf("队列为空，不能出队操作！\n");
exit(EXIT_FAILURE);
}

ele = q.front->pnext->ele;
pt = q.front->pnext;
q.front->pnext = pt->pnext;
free(pt);
/*
pt是最后一个节点时，释放完了以后，尾指针指向的
是随机内存，所以让它和头指针指向同一个地址。
*/
if (q.front->pnext == NULL)
q.rear = q.front;
}

//判断队列是否为空
bool IsemptyLinkQueue(LQueue q)
{
if (q.front == q.rear)
return true;
else
return false;
}

//获得队头元素
LQueueEle GetFrontLinkQueue(LQueue q)
{
if (IsemptyLinkQueue(q))
{
printf("队列为空，不能获得队头元素！\n");
exit(EXIT_FAILURE);
}

return q.front->pnext->ele;
}

BiTree.cpp 二叉树源文件 
#include <stdlib.h>
#include <stdio.h>
#include "BiTree.h"
#include "LinkStack.h"
#include "LinkQueue.h"


//初始化二叉树（含根节点）
void InitBiTree(pBiTree &bt, int ele)
{
bt = (BiNode *)malloc(sizeof(BiNode));
if (bt == NULL)
{
printf("内存分配失败！\n");
exit(EXIT_FAILURE);
}

bt->ele = ele;
bt->plchild = NULL;
bt->prchild = NULL;
}

//创建二叉树节点
BiNode *CreateBiTreeNode(pBiTree lchild, pBiTree rchild, int ele)
{
BiNode *pnew = (BiNode *)malloc(sizeof(BiNode));
if (pnew == NULL)
{
printf("内存分配失败！\n");
exit(EXIT_FAILURE);
}

pnew->ele = ele;
pnew->plchild = lchild;
pnew->prchild = rchild;

return pnew;
}

//插入左子二叉树
void InsertLChild(pBiTree parent, pBiTree lchild)
{
parent->plchild = lchild;
}

//插入右子二叉树
void InsertRChild(pBiTree parent, pBiTree rchild)
{
parent->prchild = rchild;
}

//用递归的方法计算二叉树的深度
int DeepBiTree(pBiTree bt)
{
int ldeep = 0, rdeep = 0;

if (bt)
{
ldeep = DeepBiTree(bt->plchild);
rdeep = DeepBiTree(bt->prchild);
return (ldeep > rdeep ? ldeep : rdeep) + 1;
}
else
return 0;
}

//（一）递归先序遍历
void RePreOrderTraverse(pBiTree bt)
{
if(bt != NULL)
{
printf("%d ", bt->ele);
RePreOrderTraverse(bt->plchild);
RePreOrderTraverse(bt->prchild);
}
}

//（二）递归中序遍历
void ReInOrderTraverse(pBiTree bt)
{
if(bt != NULL)
{
ReInOrderTraverse(bt->plchild);
printf("%d ", bt->ele);
ReInOrderTraverse(bt->prchild);
}
}

//（三）递归后序遍历
void RePostOrderTraverse(pBiTree bt)
{
if(bt != NULL)
{
RePostOrderTraverse(bt->plchild);
RePostOrderTraverse(bt->prchild);
printf("%d ", bt->ele);
}
}

//（四）非递归先序遍历
void NonRePreOrderTraverse(pBiTree bt)
{
LStack s;
InitLinkStack(s);

while (bt != NULL || !IsemptyLinkStack(s))
{
while ( bt != NULL)
{
printf("%d ", bt->ele);
PushLinkStack(s, bt);
bt = bt->plchild;
}

if (!IsemptyLinkStack(s))
{
PopLinkStack(s, bt);
bt = bt->prchild;
}
}
}

//（五）非递归中序遍历
void NonReInOrderTraverse(pBiTree bt)
{
LStack s;
InitLinkStack(s);

while (bt != NULL || !IsemptyLinkStack(s))
{
while (bt != NULL)
{
PushLinkStack(s, bt);
bt = bt->plchild;
}

if (!IsemptyLinkStack(s))
{
PopLinkStack(s, bt);
printf("%d ", bt->ele);
bt = bt->prchild;
}
}
}

//（六）非递归后序遍历
void NonRePostOrderTraverse(pBiTree bt)
{
LStack s;
InitLinkStack(s);
BiNode * pt = NULL;

while (bt != NULL || !IsemptyLinkStack(s))
{
while (bt != NULL)
{
PushLinkStack(s, bt);
bt = bt->plchild;
}

if (!IsemptyLinkStack(s))
{
PopLinkStack(s, bt);

if (bt->prchild == NULL || bt->prchild == pt)
{
printf("%d ", bt->ele);
pt = bt;
bt = NULL;
}
else
{
PushLinkStack(s, bt);
bt = bt->prchild;
}
}
}
}

//（七）非递归层次遍历
void NonReLevelOrderTraverse(pBiTree bt)
{
LQueue q;
InitLinkQueue(q);
BiNode *pt = NULL;

if (bt != NULL)
{
EnLinkQueue(q, bt);

while (!IsemptyLinkQueue(q))
{
DeLinkQueue(q, pt);
printf("%d ", pt->ele);
if (pt->plchild != NULL)
EnLinkQueue(q, pt->plchild);
if (pt->prchild != NULL)
EnLinkQueue(q, pt->prchild);
}
}
}

//（八）递归层级遍历
void ReLevelOrderTraverse(pBiTree bt)
{
int i, deep;

if (bt != NULL)
{
deep = DeepBiTree(bt);
for(i=1; i<deep+1; i++)
PrintLevelNode(bt, i);
}
}

void PrintLevelNode(pBiTree bt, int level)
{
if (bt != NULL && level > 0)
{
if (level == 1)
printf("%d ", bt->ele);
PrintLevelNode(bt->plchild, level - 1);
PrintLevelNode(bt->prchild, level - 1);
}
}

main.cpp 测试程序源文件 
#include <stdio.h>
#include "BiTree.h"
#include "LinkStack.h"
#include "LinkQueue.h"

int main(void)
{
//二叉树测试代码
pBiTree bt;
InitBiTree(bt, 10);

pBiTree lchild = CreateBiTreeNode(CreateBiTreeNode(NULL, 
CreateBiTreeNode(CreateBiTreeNode(NULL, NULL, 80), 
NULL, 55), 40), NULL, 20);
InsertLChild(bt, lchild);

pBiTree rchild = CreateBiTreeNode(NULL, CreateBiTreeNode(
CreateBiTreeNode(NULL, NULL, 60), 
CreateBiTreeNode(NULL, NULL, 70), 50), 30);
InsertRChild(bt, rchild);

printf("********二叉树图形********\n");
printf("          10\n");
printf("         /  \\\n");
printf("        20   30\n");
printf("       / \\  / \\\n");
printf("     40   N N  50\n");
printf("    / \\       /  \\\n");
printf("   N  55     60   70\n");
printf("     / \\    / \\  / \\\n");
printf("   80   N  N  N  N  N\n");
printf("  / \\\n");
printf(" N   N\n");

printf("二叉树的深度：%d", DeepBiTree(bt));

printf("\n**********************************");

printf("\n递归前序遍历：");
RePreOrderTraverse(bt);
printf("\n递归中序遍历：");
ReInOrderTraverse(bt);
printf("\n递归后序遍历：");
RePostOrderTraverse(bt);

printf("\n**********************************");

printf("\n非递归前序遍历：");
NonRePreOrderTraverse(bt);
printf("\n非递归中序遍历：");
NonReInOrderTraverse(bt);
printf("\n非递归后序遍历：");
NonRePostOrderTraverse(bt);

printf("\n**********************************");

printf("\n非递归层次遍历：");
NonReLevelOrderTraverse(bt);
printf("\n递归层次遍历：");
ReLevelOrderTraverse(bt);
putchar('\n');
return 0;}
下面是结果图：

（C语言版）二叉树遍历算法——包含递归前、中、后序和层次，非递归前、中、后序和层次遍历共八种
PS：希望大家能共同学习、共同进步。

标签：

相关文章