没有parent属性的BInary搜索树迭代器c#
为了练习，我最近开始用C#做一个二进制搜索树。在完成这项任务后，我决定实现ICollection<T>，这样我的树就可以与foreach一起使用，并且通常只是为了让我练习。
我以这样一种方式构造类，即拥有一个Node<T>类和一个包含Node<T>、Count整数和IsReadOnly布尔值的BinarySearchTree<T>类。这是我的Node类：
internal class Node<T>: INode<T> where T: IComparable<T>
{
public Node<T> RightChildNode { get; set; }
public Node<T> LeftChildNode { get; set; }
public T Key { get; set; }
//some methods go here
}这是我的BST类：
public class BinarySearchTree<T>: ICollection<T> where T: IComparable<T>
{
internal Node<T> Root { get; set; }
public int Count { get; private set; }
public bool IsReadOnly => false;
//some methods go here
}现在，为了实现ICollection<T>，我显然需要一个枚举器，我已经(部分)这样实现了：
internal class BinarySearchTreeEnumerator<T> : IEnumerator<T> where T: IComparable<T>
{
private BinarySearchTree<T> _parentTree;
private BinarySearchTree<T> _currentTree;
private Node<T> _currentNode => _currentTree.Root;
private T _currentKey;
public T Current => _currentNode.Key;
/// <summary>
/// generic constructor
/// </summary>
/// <param name="tree"></param>
public BinarySearchTreeEnumerator(BinarySearchTree<T> tree)
{
this._parentTree = tree;
}
object IEnumerator.Current => Current;
void IDisposable.Dispose(){}
//pls
public bool MoveNext()
{
if (_currentTree is null)
{
_currentTree = _parentTree;
}
var leftSubtree = this._currentTree.GetLeftSubtree();
var rightSubtree = this._currentTree.GetRightSubtree();
if (!(leftSubtree is null))
{
this._currentTree = leftSubtree;
}
else if (!(rightSubtree is null))
{
this._currentTree = rightSubtree;
}
else
{
}
}
public void Reset()
{
_currentTree = _parentTree;
}
}现在，我的问题很明显与MoveNext()方法有关。它现在不起作用了，因为它只是沿着最左边的路径沿着树往下走，然后当它到达路径的尽头时就卡住了。我知道我可以通过向我的Node<T>类添加一个Parent属性来解决这个问题，然后每当我到达树中路径的末尾时，我可以只转到一个节点并检查是否有不同的路径……然而，这将意味着完全改变我的原始类，我不希望这样做。
这是不可避免的吗？有没有办法解决这个问题而不以这种方式修改我的Node<T>类？
编辑:我做了一个东西，但它不工作:/
public bool MoveNext()
{
if (_currentNode is null)
{
this._currentNode = _parentTree.Root;
this._nodeStack.Push(_currentNode);
return true;
}
var leftNode = this._currentNode.LeftChildNode;
var rightNode = this._currentNode.RightChildNode;
if (!(leftNode is null))
{
this._currentNode = leftNode;
this._nodeStack.Push(_currentNode);
return true;
}
else if (!(rightNode is null))
{
this._currentNode = rightNode;
this._nodeStack.Push(_currentNode);
return true;
}
else
{
//current node does not have children
var parent = this._nodeStack.Pop();
do
{
if (parent is null)
{
return false;
}
} while (!(parent.RightChildNode is null));
this._currentNode = parent.RightChildNode;
this._nodeStack.Push(_currentNode);
return true;
}
}回答 2
Stack Overflow用户
发布于 2018-06-04 03:21:33
如果向枚举数添加
private List<Node<T>> _currentParentNodes = new List<Node<T>>();就像一个堆栈一样使用它，每次你下一层你将当前节点推入currentParentNodes，每次你必须上一层你从currentParentNodes中弹出父节点，然后你所有的问题都会弹出:-)
Stack Overflow用户
发布于 2018-06-06 19:23:45
您是否需要深度优先搜索(DFS)方法？它具有递归性质，很难保存为状态(它使用调用堆栈)。
也许可以考虑广泛优先搜索(BFS)方法，它是迭代的。您只需要一个currentNode和一个队列。
规则应该是
current = Queue.poll();
For child in current
Queue.offer(child);在初始化时，你会这样做
Queue.offer(rootNode);我为我糟糕的格式和语法道歉，移动用户在这里。安德烈斯
https://stackoverflow.com/questions/50670023
复制相似问题