MyException - 我的异常网
当前位置:我的异常网» 编程 » 数据结构-二叉树非递归兑现

数据结构-二叉树非递归兑现

www.MyException.Cn  网友分享于:2013-08-28  浏览:8次
数据结构----二叉树非递归实现

/*********构造二叉树*********/

输入一串以二叉树先序序列遍历的字符,空格表示空指针。

比如这串字符:ABD123CE4F5G678(为方便阅读,以数字代替空格),以先序顺序逆推出的二叉树应是:


从中观察出构造二叉树的算法:

以字符串的遍历为循环条件,构造一个栈来存放左右孩子指针都未被赋值的节点,空指针不允许入栈。

(1)循环开始前,让头节点先入栈

(2)str[i]表示当前字符(i初始值为1),若str[i-1]不是空格,那么str[i]一定是str[i-1]的左孩子;

若是空格,那么str[i]一定不是它的左孩子,即:str[i]一定是str[i-1]的右孩子,当右孩子被连接之后,

表明双亲节点的左右孩子指针均已赋值,那么就可以将这个双亲节点弹出,简化版:

if(str[i-1] != ' ')
{
top->leftchild = creat_node(str[i]);
}
else
{
top->rightchild = creat_node(str[i]);
pop(top);
}

(3)如果str[i]不是空格,在一次循环完毕之前,还应将它入栈

Warning:

这里有个问题,我们是将节点从栈中弹出来修改其左右孩子指针的,仔细一想便会发现这些栈中的“节点”

并不是真正的二叉树节点,它们只是在内存中申请了一块连续的空间来寄存真正二叉树的节点,所以我们

是不能将节点直接连到栈中的元素的

Solution:

在每个节点里附设一个指向它本身的this指针,在连接的时候在this指针的内容里赋值,这样就可以保护

真正节点的内存地址了

/*********几种遍历二叉树*********/

一、前序遍历

以上图为例,前序遍历的顺序就是:ABDCEFG

前序遍历的算法依旧要借助栈来实现:

(1)栈中存放已被访问的节点

(2)先要往左走到最底端,也就是此时节点的左孩子为NULL

(3)然后向右走一步(通过出栈来获得其双亲节点数据,将当前指针指向它的右孩子即可)

(4)以这个右孩子为新的头节点,如果它为NULL,则继续出栈获得上一个双亲节点,在向右一步,重复

这个过程,直到栈为空或者有一个节点的右孩子不为NULL

(5)有了新的头节点后,重复(2)(3),直到栈为空,也就是遍历完毕

Waring:

这里的为什么不像构造二叉树那样利用this指针?因为这里的遍历不需要改变二叉树的结构、属性,如果

遇到线索化二叉树这种需要改变其本身的遍历就应该使用this指针了

二、中序遍历

中序遍历的顺序为:DBACEFG

算法:

(1)构造栈,头节点入栈,栈中元素为存放着未被访问的节点

(2)向左走到最底端,退栈,访问这个节点,然后向右走一步

(3)以右节点为新的头节点,继续(2),直到栈为空,表示遍历结束

Waring:

中序遍历和先序遍历都需要用到栈,但是栈中元素的性质却不一样,先序遍历中栈元素需要是已被访问的节点,

这是因为双亲节点应该被首先访问;而中序遍历中栈元素须是未被访问的节点,是因为双亲节点的访问应该后于

其左孩子。

(后序遍历在其后的销毁二叉树中总结)

三、层次遍历

层次遍历顺序:ABCDEFG

算法:

(1)我们需要的不是栈了,而是队列

(2)当访问一个节点的时候,我们要考虑其左右孩子,若有不为空的孩子就让它入队列,在其双亲节点后面排队

(3)采取从左到右、从上到下的层次,每让最前端的出队列被访问时,就应该让它的不为空的孩子指针入队列

(4)当队列为空的时候,就表示遍历完毕了

/********遍历的应用**********/

一、计算节点数目

通过层次遍历可以计算,每次出队列访问一个就++count,到层次遍历结束的时候,节点数目就自然出来了

二、求二叉树深度

如果用递归的方法很简单:先求其左子树深度,再求其右子树深度,深度大的为二叉树深度

(非递归的还没想出来,求大神指教)

三、销毁二叉树

二叉树的构造是通过内存申请完成的,销毁它是必须滴~~~

采用后序遍历来销毁二叉树要简单一些,因为销毁二叉树必须要从下到上销毁,不得破坏二叉树结构,否则将不能销毁;

而后序遍历正好是这种模型

算法:

(1)利用栈,向左走到最深处

(2)这时栈顶元素的左孩子肯定为NULL,so 考虑其右孩子是否也为NULL,如不为NULL,就向右走一步;如果是NULL,

说明找到的是叶子节点,pop一下,free它,当然应该free的是this指针,因为此时我们必须改变二叉树的结构。

(3)然后再次获取栈顶元素,我们需要改变栈顶元素的左右孩子指针,我们应该修改它的左孩子还是右孩子?我们不知道

刚才free的是哪一个孩子,但是有一个定律:后序遍历同样采用从左到右的顺序,如果它的左孩子不为NULL,就应该让它的

左孩子为NULL,如果已经是NULL了,就应该让它的右孩子为NULL

(4)循环中。。。。直到栈为空、头节点被释放,表明销毁成功

四、线索化二叉树

算法:

(1)一般采用中序线索化二叉树,一个节点的左孩子指针不为空时方可进行线索化

(2)中序遍历中,我们将访问节点的部分改为对节点进行线索化,若其左孩子指针不为NULL,就让它指向其前驱,若其

右孩子指针不为NULL,就让它指向其后继,这里同样要改变二叉树结构,所以也需用到this指针

(3)确定前驱后继:附设两个遍历指针,cur指针指向当前遍历的节点,pre指针指向刚刚访问过的节点,就是cur的前驱,在

中序遍历中,就有这种相互关系来找到一个节点的前驱后继,pre是cur的前驱,cur是pre的后继





文章评论

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