非递归遍历二叉树---c++写法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了非递归遍历二叉树---c++写法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3147字，纯文字阅读大概需要5分钟。

内容图文

前序遍历的非递归算法

#include<iostream>
using namespace std;
#include<stack>
struct node
{
	char data;
	node* lchild;
	node* rchild;
};
//树的建立---前序建立
void creatTree(char ch[10],node*& root)
{
	static int i = 0;
	if (ch[i] == '#')
	{
		i++;
		root = NULL;
		return;
	}
	else 
	{
		root = new node;
		root->data = ch[i];
		i++;
		creatTree(ch, root->lchild);
		creatTree(ch, root->rchild);
	}
}
//非递归遍历
void display(node* root)
{
	stack<node*> s;
	node* p = root;
	//当p为空,栈也为空的时候退出循环
	while (p != NULL || !s.empty())
	{
		while (p!=NULL)
		{
			cout << p->data << endl;
			s.push(p);
			p = p->lchild;
		}
		//当发现一个根的左子树为空，那么弹出栈顶元素，走其右子树
		if (!s.empty())
		{
			p = s.top();
			s.pop();
			p = p->rchild;
		}
	}
}
//测试---------------------
void test()
{
	node* root=NULL;
	char ch[10] = "AB#D##C##";
	creatTree(ch,root);
	display(root);
}
int main()
{
	test();
	system("pause");
	return 0;
}

中序遍历的非递归算法

#include<iostream>
using namespace std;
#include<stack>
struct node
{
	char data;
	node* lchild;
	node* rchild;
};
//树的建立---前序建立
void creatTree(char ch[10],node*& root)
{
	static int i = 0;
	if (ch[i] == '#')
	{
		i++;
		root = NULL;
		return;
	}
	else 
	{
		root = new node;
		root->data = ch[i];
		i++;
		creatTree(ch, root->lchild);
		creatTree(ch, root->rchild);
	}
}
//非递归遍历
void display(node* root)
{
	stack<node*> s;
	node* p = root;
	//当p为空,栈也为空的时候退出循环
	while (p != NULL || !s.empty())
	{
		while (p != NULL)
		{
			s.push(p);
			//先找到左子树最左下的节点，为中序的第一个节点
			p = p->lchild;
		}
		//当发现一个根的左子树为空，那么弹出栈顶元素，走其右子树
		if (!s.empty())
		{
		   //当找到最下面的左子树时，会先弹出最下面左子树的节点然后进行输出
		   //因为当前左子树为叶子节点，没有左右孩子，所以上面的while循环会直接跳过，当再次来到if语句里面时，会弹出最后左子树的根节点，然后进行输出，再进行一次上面的循环输出右孩子
			p = s.top();
			cout << p->data << endl;
			s.pop();
			p = p->rchild;
		}
	}
}
//测试---------------------
void test()
{
	node* root=NULL;
	char ch[10] = "AB#D##C##";
	creatTree(ch,root);
	display(root);
}
int main()
{
	test();
	system("pause");
	return 0;
}

后序遍历的非递归算法

#include<iostream>
using namespace std;
#include<stack>
struct node
{
	char data;
	node* lchild;
	node* rchild;
};
struct element 
{
	node* ptr;
	int flag; //1:第一次出栈 2：第二次出栈
};
//树的建立---前序建立
void creatTree(char ch[10],node*& root)
{             
	static int i = 0;
	if (ch[i] == '#')
	{
		i++;
		root = NULL;
		return;
	}
	else 
	{
		root = new node;
		root->data = ch[i];
		i++;
		creatTree(ch, root->lchild);
		creatTree(ch, root->rchild);
	}
}
//非递归遍历
void display(node* root)
{
	stack<element> s;
	node* p = root;
	element ele;
	while (p||!s.empty())
	{
		if (p != NULL)//第一次入栈，访问左子树
		{
			ele.ptr = p; //用来保存节点，然后压入栈中
			ele.flag = 1; //表明要访问左子树
			s.push(ele);//将当前保存节点数据压入到栈中
			p = p->lchild; //访问左孩子
		}
		else 
		{
			ele = s.top();//获得即将出栈元素的节点数据
			s.pop();//出栈
			p = ele.ptr; //p指向当前要处理的节点
			if (ele.flag == 1) //只访问过左子树还需要继续访问右子树
			{
				ele.flag = 2;//表示即将访问右孩子
				s.push(ele);//第二次入栈
				p = p->rchild;
			}
			else 
			{
				//表明左右子树都访问过了
				cout << p->data << endl;
				p = NULL;//确保下次循环继续出栈
			}
		}
	}
}
//测试---------------------
void test()
{
	node* root=NULL;
	char ch[10] = "AB#D##C##";
	creatTree(ch,root);
	display(root);
}
int main()
{
	test();
	system("pause");
	return 0;
}

内容总结

以上是互联网集市为您收集整理的非递归遍历二叉树---c++写法全部内容，希望文章能够帮你解决非递归遍历二叉树---c++写法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---