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)
     {//移除的是左结点
      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
     {//移除的是右结点
      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;
  }
 }
}