首页 > 代码库 > C#先序遍历2叉树（非递归）
C#先序遍历2叉树（非递归）
找了下先序遍历二叉树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 Node112 {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 =http://www.mamicode.com/ data;120 }121 }122 }
C#先序遍历2叉树（非递归）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。