迭代打印完整的二进制树

本文关键字：二进制 打印 迭代 | 更新日期: 2023-09-27 18:23:49

解决了根本问题：如果没有任何意义，请确保您的代码像您认为的那样孤立。延迟不在例程本身，而是在将结果复制到文本框中。不确定那里发生了什么，但至少现在它是有意义的。很抱歉浪费了人们的时间！不过，因为我在这方面太弱了，我仍然希望看到它的迭代实现，所以我暂时不讨论这个问题。

我有一个完整的二叉树的形式：

root
 /'
1  node
    /'
   2  3

我想做的是将其打印为"（1，（2，3））"，但使用迭代算法，因为我使用的递归算法在较大的树上莫名其妙地慢了十到几百倍，尽管代码或树的相关部分绝对没有变化。（很明显，问题出在递归本身，所以我认为这与堆栈问题有关，尽管我在这个问题上也很茫然。）

整个下午，我一直在使用传统迭代走树逻辑的变体来研究这个逻辑，但我就是无法让它工作。有人能给我指正确的方向吗？我在C#中工作，但我真的只需要一个算法，所以任何.NET语言中的例子都可以。

更新：最初的递归代码就是这样。IsBaseGem是一个自动实现的布尔，ID是一个自动化实现的字符串。

private string DoFullCombine() => this.Component1.DoSubCombine() + "+" + this.Component2.DoSubCombine();
private string DoSubCombine() => this.IsBaseGem ? this.ID : "(" + this.DoFullCombine() + ")";

当前的迭代代码，在这一点上非常明显地被破坏了，因为它从未终止：

public string GetFullCombine()
{
    var sb = new StringBuilder();
    var gemStack = new Stack<Gem>();
    Gem gem = this;
    while (gem != null)
    {
        while (!gem.IsBaseGem)
        {
            sb.Append('(');
            gemStack.Push(gem);
            gem = gem.Component1;
        }
        sb.Append(gem.ID);
        sb.Append('+');
        gem = gemStack.Pop().Component2;
        if (gem.IsBaseGem)
        {
                sb.Append(gem.ID);
                sb.Append(')');
                gem = gemStack.Pop();
            }
        }
        return sb.ToString();
}

迭代打印完整的二进制树

我不明白为什么递归算法要慢那么多。编辑：现在很明显问题出在其他地方，但我会把它放在这里作为参考。

private void DoFullCombine(StringBuilder sb)
{
    this.Component1.DoSubCombine(sb);
    sb.Append("+");
    this.Component2.DoSubCombine(sb);
}
private void DoSubCombine(StringBuilder sb)
{
    if (this.IsBaseGem)
    {
        sb.Append(this.ID);
    }
    else
    {
        sb.Append("(");
        this.DoFullCombine(sb);
        sb.Append(")");
    };
}

编辑

我制作了非递归版本。它的速度与递归变体差不多。最棘手的是括号，我在堆栈上按下null来标记它们应该在哪里

   public string GetFullCombineNonRecur()
    {
        var sb = new StringBuilder();
        var gemStack = new Stack<Gem>();
        Gem gem = this;
        int level = 0;
        while (true)
        {
            while (!gem.IsBaseGem)
            {
                sb.Append('('); level++;
                gemStack.Push(gem);
                gem = gem.Component1;
            }
            sb.Append(gem.ID);
            do
            {
                if (level == 0)
                {
                    if (gem != this) { sb.Remove(0, 1).Remove(sb.Length - 1, 1); }
                    return sb.ToString();
                }
                gem = gemStack.Pop();
                if (gem == null) // is ")" mark
                {
                    sb.Append(')'); level--;
                }
            } while (gem == null);
            sb.Append('+');
            gemStack.Push(null); // push ")" mark here
            gem = gem.Component2;
        }
    }
相关文章：