树：二叉树的非递归遍历算法

约定不等于承诺〃 2022-05-31 10:25 180阅读 0赞

# 二叉树的递归遍历 #

二叉树的**递归遍历算法，写法很简单**，比如说前序遍历树，如下：

//前序遍历
    void PreOrderTraverse(BiTree tree)
    {
    	if (NULL != tree)
    	{
    		VisitNode(tree->data);
    		PreOrderTraverse(tree->lchild);
    		PreOrderTraverse(tree->rchild);
    	}
    }

递归算法 **就几行代码也很好理解**。

# 二叉树的非递归遍历 #

我们知道递归遍历算法也是有缺点的，就是当递归的深度很深的时候，会销毁大量的内存而且不被释放，只有在最里层的函数返回是才开始释放资源，这就存在许多的函数的压栈出栈开销，会影响效率。所有当**树的度非常深的时候，用递归遍历不是最好的选择**。下面我们**介绍一种非递归遍历树的方式。使用栈来实现非递归遍历**，这里我们使用企业级的链栈，就是企业级链表构成的栈，如果不知道企业级链表请看：[数据结构与算法：企业级链表实现（超详细）][Link 1]。主要是使用到一个**标志位**，**当标志位为false时将它的孩子结点入栈 ，然后将其标志位改为true ，当标志位true 时访问结点**。 二叉树的非递归遍历算法如下：

//非递归方式遍历树
    void nonrecursionPreTraverse(BiTree tree)
    {
    	LinkStack* stack = Create_LinkStack();
    	_BiTNode *bNode = (_BiTNode*)malloc(sizeof(_BiTNode));
    	bNode->flag = 0;
    	bNode->tree = tree;
    	Push_LinkStack(stack, (StackNode*)bNode);
    	while (stack->size!=0)
    	{
    		_BiTNode* node = (_BiTNode*)Pop_LinkStack(stack);
    		if (NULL == node->tree)
    		{
    			continue;
    		}
    		if (node->flag == 1)
    		{
    			//访问结点
    			printf("%c ", node->tree->data);
    		}
    		else
    		{
    			_BiTNode* lNode = (_BiTNode*)malloc(sizeof(_BiTNode)); 
    			_BiTNode* rNode = (_BiTNode*)malloc(sizeof(_BiTNode));
    			lNode->flag = 0;
    			lNode->tree = node->tree->lchild;
    			rNode->flag = 0;
    			rNode->tree = node->tree->rchild;
    			//非递归前序遍历---------
    			//前序遍历是 根 左 右 ，那么他们的压栈顺序是 右 左 根
    			Push_LinkStack(stack, (StackNode*)rNode);
    			Push_LinkStack(stack, (StackNode*)lNode);
    			node->flag = 1;
    			Push_LinkStack(stack, (StackNode*)node);
    
    			非递归中序遍历----------
    			中序遍历是  左 根 右 ，那么他们的压栈顺序是 右  根  左
    			//Push_LinkStack(stack, (StackNode*)rNode);
    			//node->flag = 1;
    			//Push_LinkStack(stack, (StackNode*)node);
    			//Push_LinkStack(stack, (StackNode*)lNode);
    
    			非递归后序遍历----------
    			后序遍历是  左 右 根，那么他们的压栈顺序是 根 右 左
    			//node->flag = 1;
    			//Push_LinkStack(stack, (StackNode*)node);
    			//Push_LinkStack(stack, (StackNode*)rNode);
    			//Push_LinkStack(stack, (StackNode*)lNode);
    		}
    	}
    	printf("\n");
    	return;
    }

# 完整代码 #

## CompanyLinkStack.h ##

#pragma once
    #ifndef __COMPANY_LINKSTACK_H__
    #define __COMPANY_LINKSTACK_H__
    typedef enum { ERROR, OK } STATUS;	//状态信息 ERROR 发生错误 OK 一切正常
    //栈结点 结构体
    typedef struct StackNode
    {
    	struct StackNode* next;
    }StackNode;
    //栈 结构体
    typedef struct LinkStack
    {
    	StackNode* top;//栈顶指针
    	int size;//栈结点元素个数
    }LinkStack;
    
    //创建链栈 并初始化
    LinkStack* Create_LinkStack();
    
    //压栈
    int Push_LinkStack(LinkStack* stack, StackNode* node);
    
    //弹栈
    StackNode* Pop_LinkStack(LinkStack* stack);
    
    //栈元素个数
    int Length_LinkStack(LinkStack* stack);
    
    #endif // !__COMPANY_LINKSTACK_H__

## CompanyLinkStack.c ##

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include "CompanyLinkStack.h"
    
    
    //创建链栈 并初始化
    LinkStack* Create_LinkStack()
    {
    	LinkStack* stack = (LinkStack*)malloc(sizeof(LinkStack));
    	stack->size = 0;
    	stack->top = NULL;
    	return stack;
    }
    
    //压栈
    int Push_LinkStack(LinkStack* stack,StackNode* node)
    {
    	if (NULL == stack || NULL == node)
    	{
    		return ERROR;
    	}
    	node->next = stack->top;
    	stack->top = node;
    	stack->size++;
    	return OK;
    }
    
    //弹栈
    StackNode* Pop_LinkStack(LinkStack* stack)
    {
    	if (NULL == stack || stack->size == 0)
    	{
    		return NULL;
    	}
    	StackNode* top = stack->top;
    	stack->top = stack->top->next;
    	stack->size--;
    	return top;
    }
    
    //栈元素个数
    int Length_LinkStack(LinkStack* stack)
    {
    	if (NULL == stack)
    	{
    		return ERROR;
    	}
    	return stack->size;
    }

## BiTree.c ##

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include "CompanyLinkStack.h"
    typedef char EleType;
    typedef struct BiTNode
    {
    	EleType data;//数据结点数据域
    	struct BiTNode	*lchild, *rchild;//左孩子，右孩子结点指针域
    }BiTNode,*BiTree;
    
    //栈结点 结构体，将树结点包起来使用企业级链栈
    typedef struct _BiTNode
    {
    	StackNode node;
    	BiTNode* tree;
    	int flag;
    }_BiTNode;
    
    
    
    //约定通过前序遍历创建结点
    //每个结点都有左右孩子，孩子不存在为NULL
    void CreatBiTree(BiTree* tree)
    {
    	char c;
    	scanf("%c",&c);
    	if (' '== c)
    	{
    		*tree = NULL;
    	}
    	else
    	{
    		*tree = (BiTNode*)malloc(sizeof(BiTNode));
    		(*tree)->data = c;
    		CreatBiTree(&(*tree)->lchild);//创建左子树
    		CreatBiTree(&(*tree)->rchild);//创建右子树
    	}
    }
    void VisitNode(EleType data)
    {
    	printf("%c ", data);
    	return;
    }
    //前序遍历
    void PreOrderTraverse(BiTree tree)
    {
    	if (NULL != tree)
    	{
    		VisitNode(tree->data);
    		PreOrderTraverse(tree->lchild);
    		PreOrderTraverse(tree->rchild);
    	}
    }
    //中序遍历
    void MidOrderTraverse(BiTree tree)
    {
    	if (NULL != tree)
    	{
    		MidOrderTraverse(tree->lchild);
    		VisitNode(tree->data);
    		MidOrderTraverse(tree->rchild);
    	}
    }
    //后序遍历
    void PostOrderTraverse(BiTree tree)
    {
    	if (NULL != tree)
    	{
    		PostOrderTraverse(tree->lchild);
    		PostOrderTraverse(tree->rchild);
    		VisitNode(tree->data);
    	}
    }
    //非递归方式遍历树
    void nonrecursionPreTraverse(BiTree tree)
    {
    	LinkStack* stack = Create_LinkStack();
    	_BiTNode *bNode = (_BiTNode*)malloc(sizeof(_BiTNode));
    	bNode->flag = 0;
    	bNode->tree = tree;
    	Push_LinkStack(stack, (StackNode*)bNode);
    	while (stack->size!=0)
    	{
    		_BiTNode* node = (_BiTNode*)Pop_LinkStack(stack);
    		if (NULL == node->tree)
    		{
    			continue;
    		}
    		if (node->flag == 1)
    		{
    			//访问结点
    			printf("%c ", node->tree->data);
    		}
    		else
    		{
    			_BiTNode* lNode = (_BiTNode*)malloc(sizeof(_BiTNode)); 
    			_BiTNode* rNode = (_BiTNode*)malloc(sizeof(_BiTNode));
    			lNode->flag = 0;
    			lNode->tree = node->tree->lchild;
    			rNode->flag = 0;
    			rNode->tree = node->tree->rchild;
    			//非递归前序遍历---------
    			//前序遍历是 根 左 右 ，那么他们的压栈顺序是 右 左 根
    			Push_LinkStack(stack, (StackNode*)rNode);
    			Push_LinkStack(stack, (StackNode*)lNode);
    			node->flag = 1;
    			Push_LinkStack(stack, (StackNode*)node);
    
    			非递归中序遍历----------
    			中序遍历是  左 根 右 ，那么他们的压栈顺序是 右  根  左
    			//Push_LinkStack(stack, (StackNode*)rNode);
    			//node->flag = 1;
    			//Push_LinkStack(stack, (StackNode*)node);
    			//Push_LinkStack(stack, (StackNode*)lNode);
    
    			非递归后序遍历----------
    			后序遍历是  左 右 根，那么他们的压栈顺序是 根 右 左
    			//node->flag = 1;
    			//Push_LinkStack(stack, (StackNode*)node);
    			//Push_LinkStack(stack, (StackNode*)rNode);
    			//Push_LinkStack(stack, (StackNode*)lNode);
    		}
    	}
    	return;
    }
    //非递归方式遍历树
    void nonrecursionMidTraverse(BiTree tree)
    {
    	LinkStack* stack = Create_LinkStack();
    	_BiTNode *bNode = (_BiTNode*)malloc(sizeof(_BiTNode));
    	bNode->flag = 0;
    	bNode->tree = tree;
    	Push_LinkStack(stack, (StackNode*)bNode);
    	while (stack->size != 0)
    	{
    		_BiTNode* node = (_BiTNode*)Pop_LinkStack(stack);
    		if (NULL == node->tree)
    		{
    			continue;
    		}
    		if (node->flag == 1)
    		{
    			//访问结点
    			printf("%c ", node->tree->data);
    		}
    		else
    		{
    			_BiTNode* lNode = (_BiTNode*)malloc(sizeof(_BiTNode));
    			_BiTNode* rNode = (_BiTNode*)malloc(sizeof(_BiTNode));
    			lNode->flag = 0;
    			lNode->tree = node->tree->lchild;
    			rNode->flag = 0;
    			rNode->tree = node->tree->rchild;
    			非递归前序遍历---------
    			前序遍历是 根 左 右 ，那么他们的压栈顺序是 右 左 根
    			//Push_LinkStack(stack, (StackNode*)rNode);
    			//Push_LinkStack(stack, (StackNode*)lNode);
    			//node->flag = 1;
    			//Push_LinkStack(stack, (StackNode*)node);
    
    			//非递归中序遍历----------
    			//中序遍历是  左 根 右 ，那么他们的压栈顺序是 右  根  左
    			Push_LinkStack(stack, (StackNode*)rNode);
    			node->flag = 1;
    			Push_LinkStack(stack, (StackNode*)node);
    			Push_LinkStack(stack, (StackNode*)lNode);
    
    			非递归后序遍历----------
    			后序遍历是  左 右 根，那么他们的压栈顺序是 根 右 左
    			//node->flag = 1;
    			//Push_LinkStack(stack, (StackNode*)node);
    			//Push_LinkStack(stack, (StackNode*)rNode);
    			//Push_LinkStack(stack, (StackNode*)lNode);
    		}
    	}
    	return;
    }
    //非递归方式遍历树
    void nonrecursionPostTraverse(BiTree tree)
    {
    	LinkStack* stack = Create_LinkStack();
    	_BiTNode *bNode = (_BiTNode*)malloc(sizeof(_BiTNode));
    	bNode->flag = 0;
    	bNode->tree = tree;
    	Push_LinkStack(stack, (StackNode*)bNode);
    	while (stack->size != 0)
    	{
    		_BiTNode* node = (_BiTNode*)Pop_LinkStack(stack);
    		if (NULL == node->tree)
    		{
    			continue;
    		}
    		if (node->flag == 1)
    		{
    			//访问结点
    			printf("%c ", node->tree->data);
    		}
    		else
    		{
    			_BiTNode* lNode = (_BiTNode*)malloc(sizeof(_BiTNode));
    			_BiTNode* rNode = (_BiTNode*)malloc(sizeof(_BiTNode));
    			lNode->flag = 0;
    			lNode->tree = node->tree->lchild;
    			rNode->flag = 0;
    			rNode->tree = node->tree->rchild;
    			非递归前序遍历---------
    			前序遍历是 根 左 右 ，那么他们的压栈顺序是 右 左 根
    			//Push_LinkStack(stack, (StackNode*)rNode);
    			//Push_LinkStack(stack, (StackNode*)lNode);
    			//node->flag = 1;
    			//Push_LinkStack(stack, (StackNode*)node);
    
    			非递归中序遍历----------
    			中序遍历是  左 根 右 ，那么他们的压栈顺序是 右  根  左
    			//Push_LinkStack(stack, (StackNode*)rNode);
    			//node->flag = 1;
    			//Push_LinkStack(stack, (StackNode*)node);
    			//Push_LinkStack(stack, (StackNode*)lNode);
    
    			//非递归后序遍历----------
    			//后序遍历是  左 右 根，那么他们的压栈顺序是 根 右 左
    			node->flag = 1;
    			Push_LinkStack(stack, (StackNode*)node);
    			Push_LinkStack(stack, (StackNode*)rNode);
    			Push_LinkStack(stack, (StackNode*)lNode);
    		}
    	}
    	return;
    }
    
    
    int main(int argc, char *argv[])
    {
    	BiTree tree = NULL;
    	printf("请按前序遍历的方式输入结点数据，没有结点不存在请使用空格代替：");
    	CreatBiTree(&tree);
    	printf("前序遍历：");
    	PreOrderTraverse(tree);
    	printf("\n中序遍历：");
    	MidOrderTraverse(tree);
    	printf("\n后序遍历：");
    	PostOrderTraverse(tree);
    	printf("\n非递归前序遍历：");
    	nonrecursionPreTraverse(tree);
    	printf("\n非递归中序遍历：");
    	nonrecursionMidTraverse(tree);
    	printf("\n非递归后序遍历：");
    	nonrecursionPostTraverse(tree);
    	printf("\n");
    	return 0;
    }

# 代码运行检测 #

我们来遍历如下图的二叉树：

![Center][]

注意：我们创建结点时的前序输入:ABC\_\_D\_\_EF\_\_G\_\_，一个\_表示一个空格哟。

下面是运行结果，和原来递归遍历结果是一样的。

![Center 1][]

[Link 1]: http://blog.csdn.net/qq_29542611/article/details/79342970
[Center]: /images/20220531/6f0da116c087401f93a748a0bf494d87.png
[Center 1]: /images/20220531/537c4887b9794c1f84fada52372aa870.png