[c语言]二叉树非递归算法（先中后遍历）come

洁洁

发布于 2023-10-10 13:30:33

3930

发布于 2023-10-10 13:30:33

文章被收录于专栏：小洁叫你mysql

今天本篇文章将会讲解c语言二叉树的非递归算法并加附代码。

非递归其实就是非递归遍历，非递归运用了栈的思想，包括了先中后3种方式遍历，费话不多说，开整。

1.定义头文件加结构体变量

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct TreeNode
{
	char data;
	struct TreeNode* lchild;
	struct TreeNode* rchild;
	int flag;
}TreeNode;
typedef struct StackNode 
{
	TreeNode* data;
	struct StackNode* next;
}StackNode;

注：这里定义的flag会在后序遍历中用到。（用来标记结点是否被访问过）

2.创建一棵树

void creatTree(TreeNode** T,int* index,char* data)
{
	char ch;
	ch = data[*index];
	(*index)++;
	if (ch == '#')
		*T = NULL;
	else
	{
		*T = (TreeNode*)malloc(sizeof(TreeNode));
		(*T)->data = ch;
		(*T)->flag = 0;
		creatTree(&((*T)->lchild), index, data);
		creatTree(&((*T)->rchild), index, data);
	}
}

注：此处不再详细解释，如果不懂可以参考本站另一篇文章http://t.csdn.cn/jX4cd

3.初始化栈

StackNode* initStack()
{
	StackNode* s = (StackNode*)malloc(sizeof(StackNode));
	s->data = NULL;
	s->next = NULL;
	return s;
}

注：把栈置为空（初始化）

4.头插法入栈

void headpush(TreeNode* data, StackNode* s)
{
	StackNode* node = (StackNode*)malloc(sizeof(StackNode));
	node->data = data;
	node->next = s->next;
	s->next = node;
}

注：入栈（头插法），即对指针进行操作。

5.判断栈是否为空

int is_empty(StackNode* s)
{
	if (s->next == NULL)
		return 1;
	else
		return 0;
}

6.出栈操作

StackNode* pop(StackNode* s)
{
	if (is_empty(s))
		return NULL;
	else
	{
		StackNode* node = s->next;
		s->next = node->next;
		return node;
	}
}

注：出栈之前要先判断一下是否为空栈，不为空再进行出栈，因为出的是栈顶元素直接指针断开即可。

下面重点来了：非递归先序、中序，后序遍历。

7.先序遍历

void preOrder(TreeNode* t)
{
	TreeNode* node = t;
	StackNode* s = initStack();
	while (node || !is_empty(s))  
	{
		if (node)        //判断node是否为空
		{
			printf("%c ", node->data);
			headpush(node, s);
			node = node->lchild;
		}
		else
		{
			node = pop(s)->data;
			node = node->rchild;
		}
	}
}

注：先序遍历：根左右，先打印根，然后入栈，找根的左孩子，然后判断左孩子是否为空，两种情况：1为空：那就会进入else语句，出栈，找它的右孩子，再进行判断。2不为空：就先打印，再入栈，再找它的左孩子，从而再进行判断。一直往复循环，直到不满足while条件时遍历结束。

8.中序遍历

void inOrder(TreeNode* t)
{
	TreeNode* node = t;
	StackNode* s = initStack();
	while (node || !is_empty(s))
	{
		if (node)
		{
			headpush(node, s);
			node = node->lchild;
		}
		else
		{
			node = pop(s)->data;
			printf("%c ", node->data);
			node = node->rchild;
		}
	}
}

注：与先序遍历一样，就是打印语句转移到了else语句，基本思路一致。

9.后序遍历

StackNode* getTop(StackNode* s)
{
	if (is_empty(s))
		return NULL;
	else
	{
		StackNode* node = s->next;
		return node;
	}
}
//先获取栈顶元素，因为不需要出栈，所以重新写了一个函数
void postOrder(TreeNode* t)
{
	TreeNode* node = t;
	StackNode* s = initStack();
	while (node || !is_empty(s))
	{
		if (node)
		{
			headpush(node, s);
			node = node->lchild;
	    }
		else
		{
			TreeNode* top = getTop(s)->data;
			if (top->rchild && top->rchild->flag == 0) 
			{
				top = top->rchild;
				headpush(top, s);
				node = top->lchild;
			}
			else
			{
				top = pop(s)->data;
				printf("%c ", top->data);
				top->flag = 1;
			}
		}
	}
}

注：所有遍历操作，基本上整体大的框架没有改变。

如果没有flag作为标记，会陷入死循环。

10.主函数调用

int main()
{
	int index = 0;
	TreeNode* t;
	char data[100];
	gets_s(data);
	creatTree(&t, &index, data);
	preOrder(t);
	printf("\n");
	inOrder(t);
	printf("\n");
	postOrder(t);
	return 0;
}

11.运行结果：

ab##c##
a b c  //先序
b a c  //中序
b c a  //后序
D:\VS\二叉树非递归\x64\Debug\二叉树非递归.exe (进程 12216)已退出，代码为 0。
按任意键关闭此窗口. . .

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-09-14，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度