[数据结构与算法]数据结构 --- 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");                  
}