using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication5
{
 class Program
 {
  static void Main(string[] args)
  {
   Node treeRoot = CreateTree();
   scanTree(treeRoot);
  }
  private static void scanTree(Node treeRoot)
  {
   List<Node> list = new List<Node>();
   list.Add(treeRoot);
   Node point = treeRoot;
   Write(treeRoot);
   while (true)
   {
    if (!list.Contains(point))
    { //上一輪是移除的操作
     if (treeRoot.leftSon == point)
     {//移除的是左結(jié)點(diǎn)
      if (treeRoot.rightSon != null)
      {
       treeRoot = treeRoot.rightSon;
       list.Add(treeRoot);
       Write(treeRoot);
       point = treeRoot;
       continue;
      }
      list.Remove(treeRoot);
      if (list.Count == 0)
      {
       break;
      }
      point = treeRoot;
      treeRoot = list[list.Count - 1];
     }
     else
     {//移除的是右結(jié)點(diǎn)
      list.Remove(treeRoot);
      if (list.Count == 0)
      {
       break;
      }
      point = treeRoot;
      treeRoot = list[list.Count - 1];
     }
     continue;
    }
    if (treeRoot.leftSon != null)
    {
     treeRoot = treeRoot.leftSon;
     Write(treeRoot);
     list.Add(treeRoot);
     point = treeRoot;
     continue;
    }
    if (treeRoot.rightSon != null)
    {
     treeRoot = treeRoot.rightSon;
     Write(treeRoot);
     point = treeRoot;
     list.Add(treeRoot);
     continue;
    }
    if (treeRoot.leftSon == null && treeRoot.rightSon == null)
    {
     list.Remove(treeRoot);
     if (list.Count == 0)
     {
      break;
     }
     point = treeRoot;
     treeRoot = list[list.Count - 1];
    }
   }
  }
  public static void Write(Node node)
  {
   Console.WriteLine(node.Data);
  }
  private static Node CreateTree()
  {
   Node a = new Node("A");
   a.leftSon = new Node("B");
   a.rightSon = new Node("C");
   a.leftSon.leftSon = new Node("D");
   a.leftSon.rightSon = new Node("E");
   a.rightSon.leftSon = new Node("F");
   a.rightSon.rightSon = new Node("G");
   a.leftSon.leftSon.leftSon = new Node("H");
   a.leftSon.leftSon.rightSon = new Node("I");
   return a;
  }
 }
 class Node
 {
  public string Data { get; set; }
  public Node leftSon { get; set; }
  public Node rightSon { get; set; }
  public Node(string data)
  {
   Data = data;
  }
 }
}