MyException - 我的异常网
当前位置:我的异常网» 编程 » 算法学习札记一:二叉搜索树的非递归遍历实现

算法学习札记一:二叉搜索树的非递归遍历实现

www.MyException.Cn  网友分享于:2013-10-09  浏览:7次
算法学习笔记一:二叉搜索树的非递归遍历实现

一年一度的应届生招聘季又开始了,自己悲催的也加入到了应聘大军中。无奈非计算机本专业的LZ要进入IT行业可谓难上加难,现正在恶补各类算法笔试面试题中,今天整理记录“关于二叉搜索树非递归遍历”的学习过程于此,以供大家学习交流。


 简介:

关于二叉搜索树的概念,以及前序遍历、中序遍历和后序遍历的含义大家尽可百度、谷歌或维基,LZ不废话了,此处省略XXX字……

参考

http://baike.baidu.com/link?url=nZ-h8k3pNtF2usE_zitx4t9HxJjNk1yJd7Ed6UeBt8LkKRYnpCfoiku6iRjb79A8

http://blog.csdn.net/hackbuteer1/article/details/6583988

http://wenku.baidu.com/view/da83094a852458fb770b5659.html


非递归遍历思路:

想必递归遍历的方法大家都早已了解,不了解的可以参阅《算法导论》,书中给出了前序遍历、中序遍历和后序遍历的递归版本的伪代码,将其直接转换成自己擅长的语言即可。此处要记录的是非递归版本,既然采用非递归,那么就得分解各种遍历的过程,了解其中的机制。

  1. 遍历,就是要将二叉搜索树中的各个元素都搜索一次,自然可以采用循环来替换非递归;
  2. 前序、中序和后序遍历:三者的共同点是“左子节点”一定在“右子节点”之前输出,“中间根节点”则根据遍历的类型选择放在最前、中间还是最后。

根据以上两点,设计下面的非递归方法,主要分成三个步骤:

  1. 从根节点开始,逐次遍历当前节点的左子节点,并将遍历的左子节点压入栈中保存;
  2. 逐次弹出栈中的左子节点,判别是否含有右子节点,如果有,重复上一步骤,将以当前左子节点为根的右子树中的最外侧的所有左子节点压入栈中;如果没有,弹出该左子节点,完成相应的输出显示。
  3. 重复上述两个操作,知道栈中元素为空;

整体的示意图如下:


可以看出,整个非递归的遍历路径是按照如下原则进行的:假设有一辆车从二叉查找树根节点出发,首先沿着左节点一路到底,然后调转方向返回;返回过程中如果遇到右节点,则转入右节点,并沿着该节点的后续左节点一路到底,然后再返回;一直重复上述过程,直到再次回到出发点。


非递归遍历编程实现:

由于上述示意图中需要沿原路返回,因此需要记录车辆走过的所有左子节点,并且返回时首先遇到的是最后经过的左子节点,也就是说“先经过的,后返回”,由此想到可以利用“先进后出”的栈来保存途径的所有左子节点;

     stack<PZSTree>stk;

选定了编程实现的结构后,需要确定程序实现的流程。此时需要注意各种遍历之间的微妙的差别:前序遍历,要求根节点在其左/右子节点之前输出,所以根节点肯定是第一个输出的元素,但是保存左子节点的栈是FIFO流程,所以要想实现前序遍历,要求在节点压入栈中的时候,同时输出该节点。另外如果在返回途中遇到右节点时,此时已经是完成了该右节点父节点、及其父节点的左子节点的输出,因此遇到右节点时需要同时输出该节点。

中序遍历,要求根节点在其左/右子节点之间输出,所以第一个输出的一定是最外侧最底层的左子节点,这恰巧与栈的FIFO结构吻合,因此在返回途中,依次按照栈中左子节点的弹出顺序来输出左子节点恰恰能够实现中序遍历的要求。另外如果在返回途中遇到右节点,情况同前序遍历相同。

后续遍历,要求根节点在其左/右子节点之后输出,所以第一个输出的依然是最外侧最底层的左子节点,这一点与中序遍历相同。但是如果在返回途中遇到右节点,情况有点特殊,因为此时并要求将“以该右节点为根节点的右子树”全部输出完成后,才能输出该右节点的父节点。此时需要将含有右子节点的节点暂存到另一个标记的栈中,待从右子树遍历返回后,直接从两个栈中弹出该节点。如下图所示,所有含有左右子节点的节点都遍历了两次,其输出都需要等待期右子树遍历完成后才能将其从栈中弹出并输出,因此需要额外注意。


【注】:此处后序遍历采用了两个栈结构,分别用来保存左子节点和含有右节点的左子节点。

具体代码如下:

#include <iostream>
#include <iomanip>
#include <stack>
using namespace std;

typedef struct TreeNode
{
	int value;
	TreeNode* leftChild;
	TreeNode* rightChild;
} ZSTree, *PZSTree;

void CreateTree(PZSTree* TreeRoot )
{
	int v=0;
	cout<<"输入要插入的数据\n";
	cin>>v;
	if(v==-1)
		*TreeRoot=NULL;
	else
	{
		*TreeRoot=new ZSTree();
		(*TreeRoot)->value=v;
		cout<<"请输入"<<v<<"的左节点\n";
		CreateTree(&((*TreeRoot)->leftChild));
		cout<<"请输入"<<v<<"右节点\n";
		CreateTree(&((*TreeRoot)->rightChild));
		return;
	}
	return;
}



void PreOder_NORecur(PZSTree MyTree)
{
	stack<PZSTree> stk;
	if(MyTree==NULL)
		return;
	stk.push(MyTree);
	cout<<setw(5)<<(MyTree->value);
	PZSTree left=MyTree->leftChild;
	while(left)
	{
		stk.push(left);
		cout<<setw(5)<<((*left).value);
		left=left->leftChild;
	}

	while(!stk.empty())
	{
		PZSTree top=stk.top();
		stk.pop();
		if(top->rightChild)
		{
			
			left=top->rightChild;
			while(left)
			{
				cout<<setw(5)<<((*left).value);
				stk.push(left);
				left=left->leftChild;
			}

		}
	}
}
void MidOrder_NoRecur(PZSTree MyTree)
{
	stack<PZSTree> stk;
	if(MyTree==NULL)
		return;
	stk.push(MyTree);
	PZSTree left=MyTree->leftChild;
	while(left)
	{
		stk.push(left);
		left=left->leftChild;
	}
	while(!stk.empty())
	{
		PZSTree top=stk.top();
		cout<<setw(5)<<top->value;
		top=top->rightChild;
		stk.pop();
		while(top)
		{
			stk.push(top);
			top=top->leftChild;
		}
	}
}
void PostOrder_NoRecur(PZSTree MyTree)
{
	stack<PZSTree> stk,stk1;
	if(MyTree==NULL)
		return;
	stk.push(MyTree);

	PZSTree left=MyTree->leftChild;
	while(left)
	{
		stk.push(left);
		left=left->leftChild;
	}
	while(!stk.empty())
	{
		PZSTree top=stk.top();
		if(top->rightChild==NULL)
		{
			cout<<setw(5)<<top->value;
			stk.pop();
		}
		else
		{	
			if((!stk1.empty()) && top==stk1.top())
			{
				cout<<setw(5)<<stk1.top()->value;
				stk.pop();
				stk1.pop();
				continue;
			}
			stk1.push(top);
			top=top->rightChild;
			while(top)
			{
				stk.push(top);
				top=top->leftChild;
			}

		}


	}
}
int main()
{


	PZSTree MTree;
	CreateTree(&MTree);
	PreOder_NORecur(MTree);
	cout<<endl;
	MidOrder_NoRecur(MTree);
	cout<<endl;
	PostOrder_NoRecur(MTree);
	cout<<endl;

	return 0;
}


 

最后,用表格罗列一下前序、中序和后续遍历编程实现的区别,以便加强记忆。

 

不同点

相同点

前序遍历

1)在最外侧左子节点压入栈中的同时,输出该子节点的值;

2)发现节点存在“右节点”时,需要将当前节点弹出;

第一步,以根节点为起始,将左右最外侧左子节点压入栈中;

第二步,从栈顶元素进行判别,看是否存在右子节点;

第三步,重复第一、第二步,知道栈中元素为空

中序遍历

1)在最外侧左子节点压入栈中的时候,并不进行节点输出;

2)发现节点存在“右节点”时,需要将当前节点弹出;

后序遍历

1)在最外侧左子节点压入栈中的时候,并不进行节点输出;

2)发现节点存在“右节点”时,不需要弹出当前节点;

【注意】:第二次遍历到“既含有左节点又含有右节点”的根节点时,需要弹出该节点。因此需要利用两个堆栈来记录重复遍历的节点。


文章评论

Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
每天工作4小时的程序员
每天工作4小时的程序员
旅行,写作,编程
旅行,写作,编程
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
程序员都该阅读的书
程序员都该阅读的书
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
那些争议最大的编程观点
那些争议最大的编程观点
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
Java程序员必看电影
Java程序员必看电影
中美印日四国程序员比较
中美印日四国程序员比较
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
一个程序员的时间管理
一个程序员的时间管理
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
鲜为人知的编程真相
鲜为人知的编程真相
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
我是如何打败拖延症的
我是如何打败拖延症的
如何成为一名黑客
如何成为一名黑客
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
代码女神横空出世
代码女神横空出世
老程序员的下场
老程序员的下场
10个调试和排错的小建议
10个调试和排错的小建议
 程序员的样子
程序员的样子
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
编程语言是女人
编程语言是女人
我的丈夫是个程序员
我的丈夫是个程序员
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
漫画:程序员的工作
漫画:程序员的工作
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
程序员和编码员之间的区别
程序员和编码员之间的区别
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
总结2014中国互联网十大段子
总结2014中国互联网十大段子
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有