本文主要是介绍二叉树的三种递归遍历算法和中序遍历的非递归算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

二叉树本身是一种递归的数据类型，二叉树的许多操作离不开递归。非递归遍历包括结点入栈，先访问右子树，再访问根节点，访问左子树，先序和后序的非递归算法有待调试。

include <stdio.h>

#include<stdlib.h>
#include<stdbool.h>
typedef char TElemtype;

typedef struct BiTNode
{
	TElemtype Data;
	struct BiTNode* Lchild, * Rchild;

}BiTNode;
typedef BiTNode* BiTree;

typedef BiTNode ElemType;
typedef struct
{
	ElemType* base;
	int top;
	int SatckSize;
}Stack;
typedef Stack* PStack;
void PrintTree(BiTree Tree)
{
	printf("%c", Tree->Data);
}

void PreOrder(BiTree Tree, void(*Visit)(BiTree))
{
	if (Tree) {
		Visit(Tree);
		PreOrder(Tree->Lchild, Visit);
		PreOrder(Tree->Rchild, Visit);
	}

}

void InOrder(BiTree Tree, void(*Visit)(BiTree))
{
	if (Tree)
	{
		InOrder(Tree->Lchild, Visit);
		Visit(Tree);
		InOrder(Tree->Rchild, Visit);
	}
}

void PostOrder(BiTree Tree, void (*Visit)(BiTree))
{
	if (Tree)
	{
		PostOrder(Tree, Visit);
		PostOrder(Tree, Visit);
		Visit(Tree);
	}
}
void Array_InOrder(BiTree Tree, void(*Visit)(BiTree))
{
	PStack S;
	InitStack(S, 100);
	BiTree p = Tree;
	while (p || !IsEmpty(S))
	{
		if (p) {
			Push(S, *p);
			p = p->Lchild;
		}
		else {
			Pop(S, p);
			Visit(p);
			p->Rchild;
		}
	}
}


}

附上栈的一些操作

  void InitStack(PStack S, int size)
{
	if (!S) exit(1);
    	if (size > 0) S->base = (ElemType*)malloc(sizeof(ElemType) * size);
	if (!S->base)exit(1);
	S->SatckSize = size;
	S->top = 0;

 }

bool Pop(PStack S, ElemType* PopItem)
{
	if (S->top <= 0)
	{
		printf("Stack is empty\n"); return false;
	}
	S->top--;
	*PopItem = *(S->base + S->top);
	return true;
}

bool Push(PStack S, ElemType PushItem)
{
	if (S->top >= S->SatckSize)
	{
		printf("Stack is full\n"); return false;
	}
	*(S->base + S->top) = PushItem;
	S->top++;
	return true;
}

ElemType GetTop(PStack S, ElemType* TopItem)
{
	if (S->top <= 0)
	{
		printf("NO Item\n");

	}
	*TopItem = *(S->base + S->top - 1);
	return *TopItem;
}

bool IsEmpty(PStack S)
{
	if (S->top == 0) return true;
	else return false;
}

这篇关于二叉树的三种递归遍历算法和中序遍历的非递归算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！