gpt4 book ai didi

c# - 二叉搜索树 IEnumerator.MoveNext() 非递归中序遍历实现。如何?

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:06:12 28 4
gpt4 key购买 nike

构建二叉搜索树后BST<Tkey,TValue>其中包括 BSTNode<Tkey,TValue>我正在尝试为其实现 IEnumerable 接口(interface)。

这就是我构建 BSTNodeEnumrator<Tkey,TValue> 的方式:

public class BSTNodeEnumerator<TKey, TValue> : IEnumerator<BSTNode<TKey, TValue>> where TKey : IComparable<TKey>
{
private Stack<BSTNode<TKey, TValue>> _stack;

public BSTNodeEnumerator(BSTNode<TKey, TValue> root)
{
_stack = new Stack<BSTNode<TKey, TValue>>();
_current = null;
_root = root;
}

// ... rest of the implementation
}

我传入 root节点和 _current是枚举的结果。我也尝试为此使用堆栈,因为我不像在 AVL BST 中那样跟踪父节点。

现在我希望枚举器以非递归的方式按顺序遍历树。由于 bst 的属性,这也应该导致排序的枚举,这很好,因为这正是我想要实现的。

在伪代码中顺序遍历的非递归算法,如wikipedia article

    iterativeInorder(node)
s ← empty stack
while (not s.isEmpty() or node ≠ null)
if (node ≠ null)
s.push(node)
node ← node.left
else
node ← s.pop()
visit(node)
node ← node.right

我们可以将算法转换成这个c#代码:

public BSTNode<Tkey,TValue> Next() 
{
while (_stack.Count > 0 || _current != null)
{
if (_current != null)
{
_stack.Push(_current);
_current = _current.left;
}
else
{
_current = _stack.Pop();
BSTNode<Tkey,TValue> result = _current;
_current = _current.Right;
}
}
return result;
}

但这不是必需的bool MoveNext()实现,因为我必须返回一个 bool 值。如果我设置了 _current 则为真到适当的节点,如果我在最后则为 false。

我应该如何实现 public bool MoveNext() ?我无法解决的主要问题是如果我想转换 BSTNode<Tkey,TValue> Next()进入bool MoveNext()我必须 return true而不是简单地访问节点 BSTNode<Tkey,TValue> result = _current;只有在那之后设置 _current = _current.Right;我显然做不到。

最佳答案

老实说,对于像这样的复杂枚举器,最好只使用 .NET 中内置的工具。它可以通过返回 IEnumerator<BSTNode<Tkey,TValue>> 自动将您写入的代码转换为枚举器,只需进行非常小的调整。并使用 yield return关键字。

class BSTNode<TKey, TValue> : IEnumerable<BSTNode<TKey, TValue>>
where TKey : IComparable<TKey>
{
public IEnumerator<BSTNode<TKey, TValue>> GetEnumerator()
{
var stack = new Stack<BSTNode<TKey, TValue>>();
var current = this;
while (stack.Count > 0 || current != null)
{
if (current != null)
{
stack.Push(current);
current = current.Left;
}
else
{
current = stack.Pop();
yield return current;
current = current.Right;
}
}
}

IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}

public BSTNode<TKey, TValue> Left { get; set; }

public BSTNode<TKey, TValue> Right { get; set; }

public TKey Key { get; set; }

public TValue Value { get; set; }
}

如果你很好奇,这里是编译器为它在幕后制作的 IEnumerator 类生成的代码

[CompilerGenerated]
private sealed class <GetEnumerator>d__0 : IEnumerator<BSTNode<TKey, TValue>>, IDisposable, IEnumerator
{
private int <>1__state;
private BSTNode<TKey, TValue> <>2__current;
public BSTNode<TKey, TValue> <>4__this;
private Stack<BSTNode<TKey, TValue>> <stack>5__1;
private BSTNode<TKey, TValue> <current>5__2;

BSTNode<TKey, TValue> IEnumerator<BSTNode<TKey, TValue>>.Current
{
[DebuggerHidden] get
{
return this.<>2__current;
}
}

object IEnumerator.Current
{
[DebuggerHidden] get
{
return (object) this.<>2__current;
}
}

[DebuggerHidden]
public <GetEnumerator>d__0(int <>1__state)
{
base.\u002Ector();
this.<>1__state = param0;
}

[DebuggerHidden]
void IDisposable.Dispose()
{
}

bool IEnumerator.MoveNext()
{
switch (this.<>1__state)
{
case 0:
this.<>1__state = -1;
this.<stack>5__1 = new Stack<BSTNode<TKey, TValue>>();
this.<current>5__2 = (BSTNode<TKey, TValue>) null;
goto label_8;
case 1:
this.<>1__state = -1;
this.<current>5__2 = this.<current>5__2.Right;
break;
default:
return false;
}
label_7:
label_8:
if (this.<stack>5__1.Count <= 0 && this.<current>5__2 == null)
return false;
if (this.<current>5__2 != null)
{
this.<stack>5__1.Push(this.<current>5__2);
this.<current>5__2 = this.<current>5__2.Left;
goto label_7;
}
else
{
this.<current>5__2 = this.<stack>5__1.Pop();
this.<>2__current = this.<current>5__2;
this.<>1__state = 1;
return true;
}
}

[DebuggerHidden]
void IEnumerator.Reset()
{
throw new NotSupportedException();
}
}

关于c# - 二叉搜索树 IEnumerator.MoveNext() 非递归中序遍历实现。如何?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38105729/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com