C#先序遍历2叉树（非递归）

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› c#›C#教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

找了下先序遍历二叉树C# 实现貌似没有顺手些了一个

大致思路是：

传入根节点，然后依次循环其子节点推入到栈中，

当推入的节点没有子节点的时候（叶子）或者所有子节点均已经遍历过后（上一次遍历的节点是该节点的右子节点），再依次退出栈。

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 using System.Threading.Tasks;
  6  
  7 namespace ConsoleApplication5
  8 {
  9     class Program
 10     {
 11         static void Main(string[] args)
 12         {
 13             Node treeRoot = CreateTree();
 14             scanTree(treeRoot);
 15         }
 16  
 17         private static void scanTree(Node treeRoot)
 18         {
 19             List<Node> list = new List<Node>();
 20             list.Add(treeRoot);
 21             Node point = treeRoot;
 22             Write(treeRoot);
 23             while (true)
 24             {
 25                 if (!list.Contains(point))
 26                 { //上一轮是移除的操作
 27                     if (treeRoot.leftSon == point)
 28                     {//移除的是左结点
 29                         if (treeRoot.rightSon != null)
 30                         {
 31                             treeRoot = treeRoot.rightSon;
 32                             list.Add(treeRoot);
 33                             Write(treeRoot);
 34                             point = treeRoot;
 35                             continue;
 36                         }
 37                         list.Remove(treeRoot);
 38                         if (list.Count == 0)
 39                         {
 40                             break;
 41                         }
 42                         point = treeRoot;
 43                         treeRoot = list[list.Count - 1];
 44                     }
 45                     else
 46                     {//移除的是右结点
 47                         list.Remove(treeRoot);
 48                         if (list.Count == 0)
 49                         {
 50                             break;
 51                         }
 52                         point = treeRoot;
 53                         treeRoot = list[list.Count - 1];
 54                     }
 55                     continue;
 56                 }
 57  
 58                 if (treeRoot.leftSon != null)
 59                 {
 60                     treeRoot = treeRoot.leftSon;
 61                     Write(treeRoot);
 62                     list.Add(treeRoot);
 63                     point = treeRoot;
 64                     continue;
 65                 }
 66                 if (treeRoot.rightSon != null)
 67                 {
 68                     treeRoot = treeRoot.rightSon;
 69                     Write(treeRoot);
 70                     point = treeRoot;
 71                     list.Add(treeRoot);
 72                     continue;
 73                 }
 74                 //当前的节点是叶子节点   if (treeRoot.leftSon == null && treeRoot.rightSon == null)
 75                 //{
 76                     list.Remove(treeRoot);
 77                     if (list.Count == 0)
 78                     {
 79                         break;
 80                     }
 81                     point = treeRoot;
 82                     treeRoot = list[list.Count - 1];
 83                // }
 84             }
 85  
 86         }
 87  
 88         public static void Write(Node node)
 89         {
 90             Console.WriteLine(node.Data);
 91         }
 92  
 93         private static Node CreateTree()
 94         {
 95             Node a = new Node("A");
 96            a.leftSon = new Node("B");
 97             a.rightSon = new Node("C");
 98            
 99            a.leftSon.leftSon = new Node("D");
100            a.leftSon.rightSon = new Node("E");
101            
102            a.rightSon.leftSon = new Node("F");
103            a.rightSon.rightSon = new Node("G");
104  
105            a.leftSon.leftSon.leftSon = new Node("H");
106            a.leftSon.leftSon.rightSon = new Node("I");
107             return a;
108         }
109     }
110  
111     class Node
112     {
113         public string Data { get; set; }
114         public Node leftSon { get; set; }
115         public Node rightSon { get; set; }
116  
117         public Node(string data)
118         {
119             Data = data;
120         }
121     }
122 }