[二叉树] 遍历方法总结--递归与非递归--纯C实现

非递归方法：
思路一：根据访问次序来入栈并输出
思路二：模拟访问过程
思路三：使用标识符mark来记录已经第几次访问该结点
/*
@Desc:二叉链表 无头结点
@Vesrion:0.0.1
@Time:20180922创建
*/

#include<stdio.h>
#include<stdlib.h>

#ifndef BASE
#define BASE
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int bool;
#endif

#define TElemType char //固定为char，若修改需要修改方法
typedef struct BiTNode { // 结点结构
    TElemType      data;
    struct BiTNode  *lchild, *rchild; // 左右孩子指针
}BiTNode, *BiTree;
void visit(TElemType e) {
	printf("%c ", e);
}

#define maxSize 50 //本文件中 队列、栈 最大的内容


Status PreCreate(BiTree *pT); // 先序遍历创建二叉树
int BiTreeDepth(BiTree T); // 求二叉树深
void LevelOrder(BiTree T);// 层次遍历DFS

// ----------------------------- 遍历 递归实现
void PreOrder(BiTree T); // 先序遍历二叉树
void InOrder(BiTree T); // 中序遍历二叉树
void PostOrder(BiTree T); // 后序遍历二叉树

// ----------------------------- 遍历 非递归实现
// - 思路一：根据访问次序来入栈并输出
// -- 缺点：没有模拟遍历的实质--对一个结点的三次的访问
void PreOrderNonrecursive1(BiTree T); //先序遍历
void PostOrderNonrecursive1(BiTree T); //后序遍历

// - 思路二：模拟访问过程
// -- 步骤：走到最左下角，直到走不通-->退回去，往右走一步-->往复
// -- 缺点：只模拟出前两次访问，没有模拟出最后一次访问-->所以该方法不能实现后序遍历
void PreOrderNonrecursive2(BiTree T); //先序遍历
Status InOrderNonrecursive2_1(BiTree T); //中序遍历-第一种
Status InOrderNonrecursive2_2(BiTree T); //中序遍历-第二种

// - 思路三：使用标识符mark来记录已经第几次访问该结点
// -- 优点：该方法可以模拟出遍历的实质--同一个结点将会三次访问 --> 可以完成三种遍历的任何一种
// -- 缺点：构造了一个结构体，开销大
typedef struct{
	BiTNode *ptr;
	enum {ZERO, ONE, TWO} mark; // 标识第几次访问
}PMType; //有mark域的结点指针类型
void PreOrderNonrecursive3(BiTree T); //先序遍历
void InOrderNonrecursive3(BiTree T); //中序遍历
void PostOrderNonrecursive3(BiTree T); //后序遍历

int main() {
	BiTree T;

	PreCreate(&T); //测试数据：ABC##DE#G##F###
	printf("遍历测试：\n");
	printf("---递归算法---\n");
	printf("PreOrder()：");PreOrder(T);printf("\n");
	printf("InOrder()：");InOrder(T);printf("\n");
	printf("PostOrder()：");PostOrder(T);

	printf("\n---非递归算法-----\n");
	printf("PreOrderNonrecursive1()：");PreOrderNonrecursive1(T);printf("\n");
	printf("PostOrderNonrecursive1()：");PostOrderNonrecursive1(T);printf("\n");

	printf("PreOrderNonrecursive2()：");PreOrderNonrecursive2(T);printf("\n");
	printf("InOrderNonrecursive2_1()：");InOrderNonrecursive2_1(T);printf("\n");
	printf("InOrderNonrecursive2_2()：");InOrderNonrecursive2_2(T);printf("\n");

	printf("PreOrderNonrecursive3()：");PreOrderNonrecursive3(T);printf("\n");
	printf("InOrderNonrecursive3()：");InOrderNonrecursive3(T);printf("\n");
	printf("PostOrderNonrecursive3()：");PostOrderNonrecursive3(T);printf("\n");

	printf("---层次遍历---\n");
	LevelOrder(T);printf("\n");



	return 0;
}

// 先序遍历创建二叉树
Status PreCreate(BiTree *pT) {
	char ch;
	scanf("%c", &ch);
	if ('#' == ch ) *pT=NULL;
	else {
		*pT = (BiTNode *)malloc(sizeof(BiTNode));
		if (!*pT) exit(OVERFLOW);
		(*pT)->data = ch;
		PreCreate( &(*pT)->lchild );
		PreCreate( &(*pT)->rchild );
	}
	return OK;
}
// 先序遍历二叉树
void PreOrder(BiTree T) { // - 递归
	if (!T) return ;
	visit(T->data);
	PreOrder(T->lchild);
	PreOrder(T->rchild);
}
// 中序遍历二叉树
void InOrder(BiTree T) { // - 递归
	if (!T) return ;
	InOrder(T->lchild);
	visit(T->data);
	InOrder(T->rchild);
}
// 后序遍历二叉树
void PostOrder(BiTree T) { // - 递归
	if (!T) return ;
	PostOrder(T->lchild);
	PostOrder(T->rchild);
	visit(T->data);
}
// 层次遍历DFS
void LevelOrder(BiTree T) {
	BiTNode *queue[maxSize]; int front,rear;
	BiTNode *p;

	if (!T) return;
	front=rear=0;
	queue[rear] = T;rear = (rear+1)%maxSize;
	while (front!=rear) {
		p = queue[front];front=(front+1)%maxSize;
		visit(p->data);
		if (p->lchild) {
			queue[rear] = p->lchild;
			rear = (rear+1)%maxSize;
		}
		if (p->rchild) {
			queue[rear] = p->rchild;
			rear = (rear+1)%maxSize;
		}
	}
}

// 求二叉树深
int BiTreeDepth(BiTree T) {
	int l,r,tmp;
	
	if (!T) return 0;
	else if (!T->lchild && !T->rchild) return 1;
	else {
		l = BiTreeDepth(T->lchild);
		r = BiTreeDepth(T->rchild);
		tmp = l>=r?l:r;
		return 1+tmp;
	}
}

// 遍历 - 非递归 
// - 思路一：根据访问次序来入栈并输出
// -- 缺点：没有模拟遍历的实质--对一个结点的三次的访问
void PreOrderNonrecursive1(BiTree T) { //先序遍历
	/*方法原理：
		1. 先序：根左右
		2. 访问根，然后把右、左入栈（先入栈后输出，所以将右子树先入栈）
	*/
	BiTNode *p;
	BiTNode *Stack[maxSize]; //自己实现栈，适合做题
	int top=-1; //top指向当前元素
	
	if (!T) return ;
	Stack[++top] = T; //根结点入栈
	while (top!=-1) {
		p = Stack[top--];
		visit(p->data);
		// 右孩子先入栈，先入栈后输出
		if (p->rchild) Stack[++top]=p->rchild; //把右孩子入栈
		if (p->lchild) Stack[++top]=p->lchild; //把左孩子入栈
	}
}
void PostOrderNonrecursive1(BiTree T) {
	/* 方法原理：
	思路：
		1. 先序：根左右
		2. 后序：左右根 --> 逆后序：根右左
		3. 比较【先序】和【逆后序】：发现根是一样的，知识左右换了一下
	结论：
		1. 与PreOrderNonrecursive1方法类似，只是先将左孩子先入栈（先入栈后输出），得到逆后序序列
		2. 将逆后序数列倒过来输出
	*/
	BiTNode *p;
	BiTNode *Stack[maxSize]; int top1=-1;
	BiTNode *InPostOrderStack[maxSize]; int top2=-1;
	Stack[++top1] = T;
	while (top1!=-1) {
		p = Stack[top1--];
		InPostOrderStack[++top2]=p;
		if (p->lchild) Stack[++top1]=p->lchild;
		if (p->rchild) Stack[++top1]=p->rchild;
	}
	while (top2!=-1) {
		p = InPostOrderStack[top2--];
		visit(p->data);
	}
}

// - 思路二：模拟访问过程
// -- 步骤：走到最左下角，直到走不通-->退回去，往右走一步-->往复
// -- 缺点：只模拟出前两次访问，没有模拟出最后一次访问-->所以该方法不能实现后序遍历
void PreOrderNonrecursive2(BiTree T) { //先序遍历
	BiTNode *Stack[maxSize];int top=-1; //SqStack S;
	BiTNode *p;
	
	Stack[++top]=T;//Push(&S, T);
	while (top!=-1) { //栈不为空
		//向左走到尽头
		while (p=Stack[top]) {
			visit(p->data);
			Stack[++top]=p->lchild;
		}
		--top; //上一步多将一个NULL放入栈了，删除它
		if (top!=-1) { //退一步，并向右走一步
			p=Stack[top--];
			Stack[++top]=p->rchild;
		}
	}
}
Status InOrderNonrecursive2_1(BiTree T) { //中序遍历
	BiTNode *p;
	BiTNode *Stack[maxSize];int top=-1; //创建栈
	
	Stack[++top]=T; //根指针进栈
	while (top!=-1) {
		while (p=Stack[top]) Stack[++top] = p->lchild;//向左走到尽头
		--top;//空指针出栈
		if (top!=-1) {//访问结点，向右一步
			p=Stack[top--];
			visit(p->data);
			Stack[++top]=p->rchild;
		}
	}
	return OK;
}
Status InOrderNonrecursive2_2(BiTree T) { //中序遍历
	BiTNode *p;
	BiTNode *Stack[maxSize];int top=-1; //创建栈
	
	p=T;
	while (p || top!=-1 ) {
		if (p) { //根指针进栈，遍历左子树
			Stack[++top]=p;
			p=p->lchild;
		} else { //根指针退栈，访问根结点，遍历右子树
			p=Stack[top--];
			visit(p->data);
			p=p->rchild;
		}
	}
	return OK;
}
// - 思路三：使用标识符mark来记录已经第几次访问该结点
// -- 优点：该方法可以模拟出遍历的实质--同一个结点将会三次访问 --> 可以完成三种遍历的任何一种
// -- 缺点：构造了一个结构体，开销大
void PreOrderNonrecursive3(BiTree T) { //先序遍历
	PMType pm;
	PMType stack[maxSize];int top=-1; //栈

	pm.mark=ZERO;pm.ptr=T;stack[++top]=pm; //根结点入栈
	while (top!=-1) { //栈不空
		pm = stack[top--]; //取出栈顶
		switch (pm.mark) {
		case ZERO: //第一次访问该结点
			visit(pm.ptr->data);
			pm.mark=ONE;stack[++top]=pm; //修改mark域，再放入栈
			if (pm.ptr->lchild) {//往左走
				pm.mark = ZERO;pm.ptr=pm.ptr->lchild;
				stack[++top] = pm;
			}
			break;
		case ONE: //左子树处理返回，第二次访问
			pm.mark=TWO;stack[++top]=pm; //修改mark域，再放入栈
			if (pm.ptr->rchild) { //往右走
				pm.mark=ZERO;pm.ptr=pm.ptr->rchild;
				stack[++top]=pm;
			}
			break;
		case TWO: //右子树处理访问，第三次访问
			break; //空操作
		}
	}
}
void InOrderNonrecursive3(BiTree T) { //中序遍历
	PMType pm;
	PMType stack[maxSize];int top=-1; //栈

	pm.mark=ZERO;pm.ptr=T;stack[++top]=pm; //根结点入栈
	while (top!=-1) { //栈不空
		pm = stack[top--]; //取出栈顶
		switch (pm.mark) {
		case ZERO: //第一次访问该结点
			pm.mark=ONE;stack[++top]=pm; //修改mark域，再放入栈
			if (pm.ptr->lchild) {//往左走
				pm.mark = ZERO;pm.ptr=pm.ptr->lchild;
				stack[++top] = pm;
			}
			break;
		case ONE: //左子树处理返回，第二次访问
			visit(pm.ptr->data);
			pm.mark=TWO;stack[++top]=pm; //修改mark域，再放入栈
			if (pm.ptr->rchild) { //往右走
				pm.mark=ZERO;pm.ptr=pm.ptr->rchild;
				stack[++top]=pm;
			}
			break;
		case TWO: //右子树处理访问，第三次访问
			break; //空操作
		}
	}
}
void PostOrderNonrecursive3(BiTree T) { //后序遍历
	PMType pm;
	PMType stack[maxSize];int top=-1; //栈
	
	pm.mark=ZERO;pm.ptr=T;stack[++top]=pm; //根结点入栈
	while (top!=-1) {
		pm = stack[top--];
		switch (pm.mark) {
		case ZERO: //刚刚访问此结点
			pm.mark=ONE;stack[++top]=pm; //修改mark域
			if (pm.ptr->lchild) {
				pm.mark = ZERO;pm.ptr = pm.ptr->lchild;
				stack[++top] = pm; //访问左子树
			}
			break;
		case ONE: //左子树处理返回
			pm.mark=TWO;stack[++top]=pm; //修改mark域
			if (pm.ptr->rchild) {
				pm.mark = ZERO;pm.ptr=pm.ptr->rchild;
				stack[++top] = pm; //访问右子树
			}
			break;
		case TWO: //右子树处理返回
			visit(pm.ptr->data);
		}
	}
}
[二叉树] 遍历方法总结--递归与非递归--纯C实现

相关推荐
