数据结构 --- c语言非递归法遍历二叉树

通过队列实现，从上往下一层一层去遍历，A ----> B、C ----> D、E、F ----> G、H

1.入队    2.打印数据

A入队，打印：A  队列中的元素：A                                                                                  打印结果：A   

A出队 

判断 A->LChild != NULL，B != NULL，B入队   打印：B   队列中的元素：B            打印结果：A、B

判断 A->RChild != NULL，C != NULL，C入队  打印：C  队列中的元素：B、C       打印结果：A、B、C

B出队

判断 B->LChild != NULL D != NULL，D入队   打印：D    队列中的元素：C、D       打印结果：A、B、C、D

判断 B->RChild != NULL E != NULL，E入队  打印：E     队列中的元素：C、D、E 打印结果：A、B、C、D、E

C出队 . . . 把C的左子树和右子树入队，打印C的左子树和右子树

D出队 . . . 把D的左子树和右子树入队，打印D的左子树和右子树

当队列为 NULL，整个二叉树就打印出来了

测试代码：数据结构 --- c语言递归法遍历二叉树_考拉爱睡觉鸭~的博客-CSDN博客

//要遍历的树
void layerOrder(LPTREE root) 
{
	LPTREE pmove = root;            //定义一个移动的节点==根节点
	//准备一个队列--->存的是一个节点<->指针 定义的是一个指针，用数组充当队列的容器
	LPTREE queue[1024];
	int front = 0;                  //队头标记
	int tail = 0;                   //队尾标记
	queue[tail++] = pmove;          //第一个节点入队 队尾做变化
	printf("%c", pmove->data);      //打印第一个节点的数据
	while (front != tail)           //队列不为空出队
	{
		pmove = queue[front++];		//出队 队头做变化 出队后把左、右子树入队
		if (pmove->LChild != NULL)  //左边!=NULL 左子树入队
		{
			queue[tail++] = pmove->LChild; //队尾做变化 1.入队 2.打印数据
			printf("%c", pmove->LChild->data);
		}
		if (pmove->RChild != NULL)  //右边!=NULL 右子树入队
		{
			queue[tail++] = pmove->RChild;
			printf("%c", pmove->RChild->data);
		}
	}
}

int main() 
{
	//创建二叉树--->无序的树--->创建节点
	LPTREE A = createNode('A');    //A节点
	LPTREE B = createNode('B');
	LPTREE C = createNode('C');
	LPTREE D = createNode('D');
	LPTREE E = createNode('E');
	LPTREE F = createNode('F');
	LPTREE G = createNode('G');
	LPTREE H = createNode('H');
    //一个个连接
	insertNode(A, B, C);           //A下面插入B、C
	insertNode(B, D, E);           //B下面插入D、E
	insertNode(E, G, NULL);        
	insertNode(C, NULL, F);
	insertNode(F, H, NULL);
    //打印结果
    layerOrder(A);                 //ABCDEFGH
	printf("n");
    return 0;
}

用栈实现回退效果

对于3种遍历方式的介绍：数据结构 --- c语言二叉树基础(无序二叉树)_考拉爱睡觉鸭~的博客-CSDN博客

定义一个移动的指针指向第一个位置

入栈顺序：ABD，出栈顺序：DBA

//非递归法先序
void preOrderByStack(LPTREE root) 
{ 
	if (root == NULL)                 //为空无法打印
		return;
	LPTREE pmove = root;              //定义移动的指针==根节点
	//栈
	LPTREE stack[1024];               //准备栈存储节点的位置<->指针
	int stackTop = -1;                //栈顶标记

	while (stackTop != -1 || pmove)   //pmove!=NULL
	{
		//先走左边,边打印边入栈
		while (pmove != NULL) 
		{
			printf("%c", pmove->data); //打印数据
			stack[++stackTop] = pmove; //入栈 栈顶标记从-1开始 ++栈顶标记
			pmove = pmove->LChild;     //入栈后一直往左边走,直到走到空的位置
		}
		//退出循环，到达空的位置，出栈找右边
		if (stackTop != -1)            //栈为空无法出栈
		{
			pmove = stack[stackTop--];
			pmove = pmove->RChild;     //找 出栈后节点的右边
		}
	}
}

刚开始只做入栈操作，不做数据打印，先走到树的最左边在出栈的位置打印，先走完再做打印

//非递归法中序
void midOrderByStack(LPTREE root) 
{
	if (root == NULL)
		return;

	LPTREE pmove = root;
	//栈
	LPTREE stack[1024];
	int stackTop = -1;

	while (pmove != NULL || stackTop != -1) 
	{
		while (pmove)                     //pmove!=NULL
		{
			stack[++stackTop] = pmove;    //入栈
			pmove = pmove->LChild;        //pmove一直往左边走 走到最左边
		}
        //退出循环，到达空的位置
		if (stackTop != -1)               //栈不为空出栈
		{
			pmove = stack[stackTop--];
			printf("%c", pmove->data);    //打印数据
			pmove = pmove->RChild;        //找 出栈后节点的右边
		}
	}
}

按左根右的方式存在重复打印的现象，打印节点的前提是出栈节点的右边没有节点或者已经被遍历完了，才能打印当前节点，如果有右边就要走到最右边

第1步不需要重复，重复做2、3步即可

//非递归法后序
void lastOrderByStack(LPTREE root) 
{
	if (root == NULL)
		return;

	LPTREE pmove = root;
	//栈
	LPTREE stack[1024];
	int stackTop = -1;
	//1.先走到最左边
	while (pmove) 
	{
		stack[++stackTop] = pmove;    //pmove!=NULL一直走到最左边 持续入栈
		pmove = pmove->LChild;
	}
	LPTREE lastvisited = NULL;       //记录被访问的节点<->访问标记
	while (stackTop != -1)           //栈不为空做出栈操作
	{
		pmove = stack[stackTop--];   //出栈
        //右边没有节点或者被访问了一次-->走过一次了在做回退
		if (pmove->RChild == NULL || pmove->RChild == lastvisited) 
		{
			printf("%c", pmove->data);
			lastvisited = pmove;    //改变上一次访问的标记==当前遍历的节点
		}
		else                        //有右边就要走右边
		{
			stack[++stackTop] = pmove; //当前节点入栈
			pmove = pmove->RChild;     //往当前节点右边走
			while (pmove) 
			{
				stack[++stackTop] = pmove;  //右子树的左边走到底
				pmove = pmove->LChild;      
			}
		}
	}
}

int main() 
{
	//创建二叉树--->无序的树--->创建节点
	LPTREE A = createNode('A');    //A节点
	LPTREE B = createNode('B');
	LPTREE C = createNode('C');
	LPTREE D = createNode('D');
	LPTREE E = createNode('E');
	LPTREE F = createNode('F');
	LPTREE G = createNode('G');
	LPTREE H = createNode('H');
    //一个个连接
	insertNode(A, B, C);           //A下面插入B、C
	insertNode(B, D, E);           //B下面插入D、E
	insertNode(E, G, NULL);        
	insertNode(C, NULL, F);
	insertNode(F, H, NULL);

    preOrderByStack(A);            //ABDEGCFH
    printf("n");
    midOrderByStack(A);            //DBGEACHF
    printf("n");
    lastOrderByStack(A);           //DGEBHFCA
    printf("n");                  
}