首页 > 代码库 > 二叉树的遍历(递归、非递归)
二叉树的遍历(递归、非递归)
1 public class BinTree { 2 private char date; 3 private BinTree lchild; 4 private BinTree rchild; 5 6 public BinTree(char c) { 7 date = c; 8 } 9 10 // 先序遍历递归 11 public static void preOrder(BinTree t) { 12 if (t == null) { 13 return; 14 } 15 System.out.print(t.date); 16 preOrder(t.lchild); 17 preOrder(t.rchild); 18 } 19 20 // 中序遍历递归 21 public static void InOrder(BinTree t) { 22 if (t == null) { 23 return; 24 } 25 InOrder(t.lchild); 26 System.out.print(t.date); 27 InOrder(t.rchild); 28 } 29 30 // 后序遍历递归 31 public static void PostOrder(BinTree t) { 32 if (t == null) { 33 return; 34 } 35 PostOrder(t.lchild); 36 PostOrder(t.rchild); 37 System.out.print(t.date); 38 } 39 40 // 先序遍历非递归 41 public static void preOrder2(BinTree t) { 42 Stack<BinTree> s = new Stack<BinTree>(); 43 while (t != null || !s.empty()) { 44 while (t != null) { 45 System.out.print(t.date); 46 s.push(t); 47 t = t.lchild; 48 } 49 if (!s.empty()) { 50 t = s.pop(); 51 t = t.rchild; 52 } 53 } 54 } 55 56 // 中序遍历非递归 57 public static void InOrder2(BinTree t) { 58 Stack<BinTree> s = new Stack<BinTree>(); 59 while (t != null || !s.empty()) { 60 while (t != null) { 61 s.push(t); 62 t = t.lchild; 63 } 64 if (!s.empty()) { 65 t = s.pop(); 66 System.out.print(t.date); 67 t = t.rchild; 68 } 69 } 70 } 71 72 // 后序遍历非递归 73 public static void PostOrder2(BinTree t) { 74 Stack<BinTree> s = new Stack<BinTree>(); 75 Stack<Integer> s2 = new Stack<Integer>(); 76 Integer i = new Integer(1); 77 while (t != null || !s.empty()) { 78 while (t != null) { 79 s.push(t); 80 s2.push(new Integer(0)); 81 t = t.lchild; 82 } 83 while (!s.empty() && s2.peek().equals(i)) { 84 s2.pop(); 85 System.out.print(s.pop().date); 86 } 87 88 if (!s.empty()) { 89 s2.pop(); 90 s2.push(new Integer(1)); 91 t = s.peek(); 92 t = t.rchild; 93 } 94 } 95 } 96
二叉树的遍历(递归、非递归)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。