加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 综合聚焦 > 服务器 > 安全 > 正文

【数据结构】 二叉树 非递归遍历

发布时间:2020-12-15 06:09:06 所属栏目:安全 来源:网络整理
导读:以下是我自己的一些写法,由于本人修行尚浅,因此代码难免有不当之处,如有发现,敬请指出,如有雷同纯属巧合。 /* 先序遍历 * 思路: 先输出根 并一直寻找左子树,同时,若存在右子树,则右子树入栈。 * 找完所有的左子树之后,栈顶出栈,重复上述工作,一

以下是我自己的一些写法,由于本人修行尚浅,因此代码难免有不当之处,如有发现,敬请指出,如有雷同纯属巧合。

/* 先序遍历
 * 思路: 先输出根 并一直寻找左子树,同时,若存在右子树,则右子树入栈。
 * 找完所有的左子树之后,栈顶出栈,重复上述工作,一直到栈空为止。
 * */
void PreOrderTraverse(PBiTree T)
{
	if (T == NULL)
	{
		return;
	}

	Stack nStack = {0,};

	while (NULL != T)
	{
		if (T->RChild != NULL)
		{
			nStack.BElem[nStack.top++] = T->RChild;
		}

		printf("%c ",T->elem);

		T = T->LChild;

		if (NULL == T && nStack.top != 0)
		{
			T = nStack.BElem[-- nStack.top];
		}
	}
}
/** 中序遍历
 *  根 先入栈,
 * */
void InOrderTraverse(PBiTree T)
{
	if (T == NULL)
	{
		return;
	}

	Stack nStack = {0,};

	while (NULL != T)
	{
		while (NULL != T->LChild)
		{
			nStack.BElem[nStack.top++] = T;
			T = T->LChild;
		}

		printf("%c ",T->elem);
		T = T->RChild;

		while (NULL == T)
		{
			if (0 != nStack.top)
			{
				T = nStack.BElem[--nStack.top];
				printf("%c ",T->elem);
			}
			else
			{
				break;
			}

			T = T->RChild;
		}
	}
}


整个的代码:

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

#define MAX_SIZE 100

typedef struct BiTree
{
	char elem;
	struct BiTree * LChild;
	struct BiTree * RChild;
} BiTree,*PBiTree;

typedef struct Stack
{
	int top;
	PBiTree BElem[MAX_SIZE];
} Stack;

PBiTree CreateBiTree();
void PreOrderTraverse(PBiTree T);
void InOrderTraverse(PBiTree T);

int main()
{
	PBiTree Tree = CreateBiTree();

	printf("n先序遍历:n");
	PreOrderTraverse(Tree);

	printf("n中序遍历:n");
	InOrderTraverse(Tree);

	return 0;
}


PBiTree CreateBiTree()
{
	char data;
	PBiTree T;
	scanf("%c",&data);

	if (data == '#')
	{
		T = NULL;
	}
	else
	{
		T = (PBiTree)malloc(sizeof(BiTree));
		T->elem = data;
		T->LChild = CreateBiTree();
		T->RChild = CreateBiTree();
	}

	return T;
}


/* 先序遍历
 * 思路: 先输出根 并一直寻找左子树,同时,若存在右子树,则右子树入栈。
 * 找完所有的左子树之后,栈顶出栈,重复上述工作,一直到栈空为止。
 * */
void PreOrderTraverse(PBiTree T)
{
	if (T == NULL)
	{
		return;
	}

	Stack nStack = {0,T->elem);

		T = T->LChild;

		if (NULL == T && nStack.top != 0)
		{
			T = nStack.BElem[-- nStack.top];
		}
	}
}


/** 中序遍历
 *  根 先入栈,
 * */
void InOrderTraverse(PBiTree T)
{
	if (T == NULL)
	{
		return;
	}

	Stack nStack = {0,T->elem);
			}
			else
			{
				break;
			}

			T = T->RChild;
		}
	}
}

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读