Итеративная печать полного двоичного дерева

Question

Исправлена ​​основная проблема: Когда ничего не имеет смысла, убедитесь, что ваш код такой же изолированный, как вы думаете. Задержка не была в самой процедуре, она заключалась в копировании результата в текстовое поле. Не уверен, что там происходит, но по крайней мере теперь это имеет смысл. Извините за то, что тратишь время людей! Поскольку я настолько слаб в этой области, мне все же хотелось бы увидеть итеративную реализацию этого, поэтому я оставлю этот вопрос открытым.

У меня есть полное бинарное дерево вида:

root 
/\ 
1 node 
    /\ 
    2 3 

То, что я хотел бы сделать, это распечатать его как «(1, (2,3))», но с использованием итеративного алгоритма, так как рекурсивный алгоритм, который я использовал, необъяснимо замедлился в десять-десять раз на более крупных деревьях, несмотря на то, что в коде или в соответствующих частях дерева не было никаких изменений. (Это, безусловно, рекурсивные проблемы, поэтому я предполагаю, что это имеет какое-то отношение к проблемам с стеком, хотя я честно теряю в этом вопросе.)

Я уже говорил, логично весь день, используя вариации традиционной итеративной логики древовидной ходьбы, и я просто не могу заставить ее работать. Может ли кто-нибудь указать мне в правильном направлении? Я работаю на C#, но мне действительно нужен алгоритм, поэтому примеры на любом языке .NET должны делать.

Обновление: Оригинальный, рекурсивный код был просто этим. IsBaseGem - это автоматически реализованный bool, а 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(); 
} 

Answer 1

Я не понимаю, почему рекурсивный алгоритм должен быть, что гораздо медленнее. EDIT теперь ясно, что проблема была где-то в другом месте, но я буду держать ее здесь как ссылку.

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(")"); 
    }; 
} 

EDIT

Я сделал нерекурсивную версию. Это примерно такая же скорость, как и рекурсивный вариант. Наиболее сложными были круглые скобки, я нажимаю нуль на стек, чтобы отметить, где они должны быть.

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; 
     } 
    }