＋设为首页 ＋添加到收藏夹
这几天偶来这里转了转,发现这里有不少的朋友问到这样一个问题:
已知二叉树的前序和中序,求后序.
然后偶也看了不少朋友的解答,基本上都是先还原出二叉树,然后再遍历求出后序,程序都挺麻烦的...
呵呵,在C++探路者,偶也曾经提出了这个问题,想看看大家的解法,可惜都是同样的做法..
呵呵,其实偶知道一个好方法的~~~~:D
偶现在就公布答案~~~~~~! 不过先声明,这并不是我的原创... (不要打我呀!)
这是一个比较少见的方法.在保证前序和中序的正确性和无二义性下,比标准解法要简单得多.有兴趣的朋友可以前去C++探路者看看: http://cpp.aosee.com/bbs/. 算法与数据结构版. 这个算法还可以推广到已经后序和中序 求前序的问题上.
同样希望有不同见解的朋友能继续就这个问题进行讨论.偶不是高手的说,如果有错误,还请指出~可以在这里跟帖,也可以到论坛去回复.当然,我建议去论坛回复,因为这样子我比较能顾及~
最后,希望大家以后也能多到C++探路者坐客,关心这个初学者的论坛:) 谢谢! 同时散分:)
我这就去看看，留个名，好拣分，谢谢先！
看看
up
哈哈
gz
gz
sd
谢谢你的贴子，又多长了点知识。
哥们你前面说的我看了看:我觉得这个问题提得很好,有助于我们对算法的进一步掌握,升华.
我觉得一棵二叉树,给出了前序和后序就能确定一棵二叉树,而一棵二叉树又能得到他的后序遍历.从中我们能不能走一条捷径,直接从前序和后序确定他的后序遍历.
你一想我们是怎样确定二叉树的,我们怎样确定二叉树的根接点的,只要我们能一一确定一个二叉树的每个接点的话我们不就可以不通过先确定这棵二叉树,而直接确定这棵二叉树的后序遍历了吗.
我是赶才想了一下,不知道有不有用
哥们你前面说的我看了看:我觉得这个问题提得很好,有助于我们对算法的进一步掌握,升华.
我觉得一棵二叉树,给出了前序和后序就能确定一棵二叉树,而一棵二叉树又能得到他的后序遍历.从中我们能不能走一条捷径,直接从前序和后序确定他的后序遍历.
你一想我们是怎样确定二叉树的,我们怎样确定二叉树的根接点的,只要我们能一一确定一个二叉树的每个接点的话我们不就可以不通过先确定这棵二叉树,而直接确定这棵二叉树的后序遍历了吗.
我是赶才想了一下,不知道我的观点对大家有不有用.希望大家多多指教.
谢谢!!!
呵呵，不过而而，没事大家还是常去数据结构盒算法版看看吧
"直接从前序和后序确定他的后序遍历",这有疑问吗?我说的不就是"跳过了建树的步骤,而直接得到二叉树的后序遍历"吗?
一个算法吗?
不一定就是只有一种模式,你的答案也只是其中一种,别人可能有更好的算法,不过你能想到就很不错了.
拉来大家讨论一下很好.
常关注:)!!!!
这个问题 我以前在数据算法版问过
http://www.csdn.net/expert/topic/692/692030.xml?temp=.7136042
