我正在阅读 Cormen 算法书(二叉搜索树章节),它说有两种无需递归即可遍历树的方法:
使用堆栈和
更复杂但更优雅
不使用堆栈的解决方案,但
假设两个指针可以
测试平等
我已经实现了第一个选项(使用堆栈),但不知道如何实现后者。
这不是作业,只是为了教育自己而读书。
关于如何在 C# 中实现第二个的任何线索?
当然可以。您没有说您想要什么样的遍历,但这是中序遍历的伪代码。
t = tree.Root;
while (true) {
while (t.Left != t.Right) {
while (t.Left != null) { // Block one.
t = t.Left;
Visit(t);
}
if (t.Right != null) { // Block two.
t = t.Right;
Visit(t);
}
}
while (t != tree.Root && (t.Parent.Right == t || t.Parent.Right == null)) {
t = t.Parent;
}
if (t != tree.Root) { // Block three.
t = t.Parent.Right;
Visit(t);
} else {
break;
}
}
要获得前序或后序,您需要重新排列块的顺序。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)