找了下先序遍历hashu.html" target="_blank">二叉树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 }