欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树的前序,中序,后序非递归遍历(C&C++)

程序员文章站 2024-01-15 19:47:46
...

前序遍历示意:

二叉树的前序,中序,后序非递归遍历(C&C++)

中序遍历示意:

二叉树的前序,中序,后序非递归遍历(C&C++)

后序遍历示意:

二叉树的前序,中序,后序非递归遍历(C&C++)

实现:

void Visit(int n)
{
	cout << n;
}

void NRPreOrder(BiTree bt)
{
	BiTree S[MAXSIZE], p = bt;
	int top = -1;
	if (bt == NULL) return;
	while (!(!p && top == -1))//p与栈均不空时继续循环
	{
		while (p)
		{
			Visit(p->data);    //入栈时访问
			S[++top] = p;
			p = p->lchird;
		}                      //循环访问左子树并入栈
		if (top == -1) return; //栈空时返回
		else
		{
			p = S[top--];      //出栈,该节点使用完毕,不会再经过该节点
			p = p->rchird;     //p指向右子树
		}
	}
	cout << endl;
}
void NRInOrder(BiTree bt)
{
	BiTree S[MAXSIZE], p = bt;
	int top = -1;
	if (bt == NULL) return;
	while (!(!p && top == -1)) //p与栈均不空时继续循环
	{
		while (p)
		{

			S[++top] = p;
			p = p->lchird;     //循环访问左子树并入栈
		}
		if (top == -1) return; //栈空时返回
		else
		{
			p = S[top--];
			Visit(p->data);    //出栈并访问,该节点使用完毕,不会再经过该节点
			p = p->rchird;     //p指向右子树
		}
	}
	cout << endl;
}

void NRPostOrder1(BiTree bt)
{
	BiTree S[MAXSIZE], antiPre[MAXSIZE], p = bt;
	int top = -1, cnt = -1;
	if (bt == NULL) return;
	while (!(!p && top == -1))
	{
		while (p)
		{
			antiPre[++cnt] = p;  //不访问,入栈时同时入逆前置栈
			S[++top] = p;
			p = p->rchird;       //注意,这里首先遍历右子树
		}
		if (top == -1) return;
		else
		{
			p = S[top--];
			p = p->lchird;       //p指向左子树
		}
	}
	for (int i = cnt; i >= 0; i--)
		Visit(antiPre[i]->data); //出逆前置栈,同时访问节点;
	cout << endl;
}

void NRPostOrder2(BiTree bt)
{
	BiTree S[MAXSIZE], p = bt;
	int flag[MAXSIZE] = { 0 };  //构建标志量
	int top = -1;
	if (bt == NULL) return;
	while (!(!p && top == -1))
	{
		while (p)
		{

			S[++top] = p;
			flag[top] = 1;    //第一次经过该节点,标志量置1
			p = p->lchird;
		}                     //循环访问左子树并入栈
		if (top == -1) return;
		p = S[top];
		if (flag[top] == 1)
		{
			flag[top] = 2;    //第二次经过该节点,标志量置2
			p = p->rchird;
		}
		else
		{   // 节点已被经过两次,第三次经过该节点时,出栈并访问
			p = S[top--];
			Visit(p->data);
			p = NULL;        //重置p指针
		}
	}
	cout << endl;
}

void NRPostOrder3(BiTree bt)
{
	BiTree S[MAXSIZE], p = bt, Pre = NULL;    //构建记忆树
	int top = -1;
	if (bt == NULL) return;
	while (!(!p && top == -1))
	{
		while (p)
		{

			S[++top] = p;
			p = p->lchird;
		}
		if (top == -1) return;
		//栈顶节点右孩子为空或右子树已被遍历过,则栈顶节点出栈并访问
		if (S[top]->rchird == NULL || S[top]->rchird == Pre)
		{
			p = S[top--];
			Visit(p->data);
			Pre = p;        //Pre指向刚刚被遍历过的节点
			p = NULL;
		}
		else
		{
			p = S[top]->rchird;
		}
	}
	cout << endl;
}

测试结果:

二叉树的前序,中序,后序非递归遍历(C&C++)