二进制搜索树遍历-预编序

本文关键字：搜索树 遍历 二进制 | 更新日期: 2023-09-27 17:58:19

我正在尝试使用返回IEnumerable 的yield return来实现Tree Traversal PreOrder

private IEnumerable<T> Preorder(Node<T> node)
{
    while(node != null)
    {
        yield return node.Data;
        yield return node.LeftChild.Data;
        yield return node.RightChild.Data;
    }
}

在这种情况下，它进入无限循环，是的，我知道我需要继续遍历。如何做到这一点？

如果LeftChild或RightChild为null，则引发null异常。我认为在这一点上，我需要让步；

我想，有序和后有序也会相似，有什么想法吗？

我有复活版，效果很好。

public void PreOrderTraversal(Node<T> node)
{
    if(node!=null)
    {
        Console.Write(node.Data);
    }
    if (node.LeftChild != null)
    {
        PreOrderTraversal(node.LeftChild);
    }
    if (node.RightChild != null)
    {
        PreOrderTraversal(node.RightChild);
    }
}

谢谢。

二进制搜索树遍历-预编序

选项#1递归

public class Node<T> : IEnumerable<T>
{
    public Node<T> LeftChild { get; set; }
    public Node<T> RightChild { get; set; }
    public T Data { get; set; }
    public IEnumerator<T> GetEnumerator()
    {
        yield return Data;
        if (LeftChild != null)
        {
            foreach (var child in LeftChild)
                yield return child;
        }
        if (RightChild != null)
        {
            foreach (var child in RightChild)
                yield return child;
        }
    }
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

用法：

var child1 = new Node<int> { Data = 1 };
var child2 = new Node<int> { Data = 2 };
var child3 = new Node<int> { Data = 3, LeftChild = child1 };
var root = new Node<int> { Data = 4, LeftChild = child3, RightChild = child2 };
foreach (var value in root)
    Console.WriteLine(value);

选项#2非递归静态方法

public static IEnumerable<T> Preorder<T>(Node<T> root)
{
    var stack = new Stack<Node<T>>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        var node = stack.Pop();
        yield return node.Data;
        if (node.RightChild != null)
            stack.Push(node.RightChild);
        if (node.LeftChild != null)
            stack.Push(node.LeftChild);
    }
}
相关文章：