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

二叉树的递归非递归遍历详解

程序员文章站 2024-01-15 12:57:16
...

1、二叉树的递归非递归遍历详解

树的节点
#typedef char elemtype
typedef struct BTNode
{
	elemtype data;
	BTNode * Leftchild;
	BTNode * Rightchild;
}BTNode,*BiTree;

//递归先序遍历
先序遍历顺序:根-》左子树-》右子树
void PreOrder(BTNode * root)
{
	if(NULL == root)
	{
		return ;
	}
	cout<<root->data<<" ";
	PreOrder(root->leftchild);
	PreOrder(root->Rightchild);
}
//递归中序遍历
先序遍历顺序:左子树-》根-》右子树
void InOrder(BTNode * root)
{
	if(NULL == root)
	{
		return ;
	}
	PreOrder(root->leftchild);
	cout<<root->data<<" ";
	PreOrder(root->Rightchild);
}

//递归后序遍历
先序遍历顺序:左子树-》右子树-》根
void PreOrder(BTNode * root)
{
	if(NULL == root)
	{
		return ;
	}
	PreOrder(root->leftchild);
	PreOrder(root->Rightchild);
	cout<<root->data<<" ";
}

这里以先序遍历为例,画图说明

 二叉树的递归非递归遍历详解

图片只画了先序遍历的一部分,按照上图一次类推,将得到完整的先序遍历结果;同理可得中序和后序遍历结果。

 

//非递归遍历

//非递归中序遍历
递归底层就是通过数据结构栈实现的,实现先进后出,所以非递归遍历将用到栈实现
实现思路:从根节点开始,只要当前节点存在,或者栈不为空,则重复下列操作
	1:如果当前节点存在,进栈并遍历左子树
	2:否则退栈并访问数据,然后遍历右子树
void NiceInOrder(BTNode * root)
{
	if(NULL == root)
	{
		return ;
	}
	BTNode* p=root;
	stack<BTNode*> st;
	while(!st.empty() || p!=NULL)
	{
		if(p!=NULL)
		{
			st.push(p);
			p=p->Leftchild;
		}
		else
		{
			p=st.top();
			st.pop();
			cout<<p->data<<" ";
			p=p->Rightchild;
		}
	}
}
//非递归先序遍历
实现思路:从根节点开始,只要当前节点存在,或者栈不为空,则重复下列操作
	1:如果当前节点存在,访问数据并进栈,再遍历左子树
	2:否则退栈,然后遍历右子树
void NicePreOrder(BTNode* root)
{
	if(NULL == root)
	{
		return ;
	}
	BTNode* p=root;
	stack<BTNode*> st;
	while(p!=NULL || !st.empty())
	{
		if(p!=NULL)
		{
			cout<<p->data<<" ";
			st.push(p);
			p=p->Leftchild;
		}
		else
		{
			p=st.top();
			st.pop();
			p=p->Rightchild
		}
	}
}
//非递归后序遍历
实现思路:从根节点开始,只要当前节点存在,或者栈不为空,则重复下列操作
	1:如果当前节点开始,进栈并遍历左子树,直到左子树为空
	2:如果栈顶元素的右子树为空,或者栈顶节点的右孩子为刚访问过得节点,则退栈并访问
	3:否则,遍历右子树
void NicePostOrder(BTNode* root)
{
	if(NULL == root)
	{
		return ;
	}
	BTNode* p=root;
	BTNode* q=NULL:
	stack<BTNode*> st;
	while(p!=NULL || !st.empty())
	{
		if(p!=NULL)
		{
			st.push(p);
			p=p->Leftchild;
		}
		else
		{
			p=st.top();
			if(p->Rightchild==NULL || p->Rightchild==q)
			{
				cout<<p->data<<" ";
				st.pop();
				q=p;
				p=NULL;
			}
			else
			{
				p=p->Rightchild;
			}
		}
	}
}

这里以非递归先序遍历为图解,解释程序执行过程

 二叉树的递归非递归遍历详解中序遍历只是在每次出栈的时候访问数据,过程相似

后序遍历需要主要的是需要用一个标志q来标记节点是否访问过,每次访问过p要置为NULL,否则就会陷入死循环。代码是下面这一段

			if(p->Rightchild==NULL || p->Rightchild==q)
			{
				cout<<p->data<<" ";
				st.pop();
				q=p;
				p=NULL;
			}

好了,到此处二叉树的三种遍历就全部说完了,之后会介绍二叉树的其他操作!

相关标签: BinaryTree_Order