二叉树的三种递归遍历算法和中序遍历的非递归算法

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

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;
}
上一篇:行为型设计模式:访问者模式


下一篇:2020第十一届蓝桥杯javaA组省赛题解(1~4)