首页 > 代码库 > 重拾算法(1)——优雅地非递归遍历二叉树及其它
重拾算法(1)——优雅地非递归遍历二叉树及其它
重拾算法(1)——优雅地非递归遍历二叉树及其它
本文中非递归遍历二叉树的思想和代码都来自这里（http://jianshu.io/p/49c8cfd07410#）。我认为其思想和代码都足够优雅动人了，于是稍作整理，得到如下的程序。
前中后序遍历二叉树
1 public class BinaryTreeNode<T> 2 { 3 public T Value { get;set; } 4 public BinaryTreeNode<T> Parent { get;set; } 5 public BinaryTreeNode<T> Left { get;set; } 6 public BinaryTreeNode<T> Right { get;set; } 7 8 public BinaryTreeNode(T value, BinaryTreeNode<T> parent = null, BinaryTreeNode<T> left = null, BinaryTreeNode<T> right = null) 9 { 10 this.Value = http://www.mamicode.com/value; this.Left = left; this.Right = right; 11 } 12 13 public virtual void Traverse<T1>(TraverseOrder order, Action<BinaryTreeNode<T>, T1> actionOnNode, T1 sender) 14 { 15 if (actionOnNode == null) { return; } 16 17 var left = this.Left; 18 var right = this.Right; 19 switch (order) 20 { 21 case TraverseOrder.Preorder: 22 /* recursive preorder traverse 23 actionOnNode(this, sender); 24 if (left != null) { Left.Traverse(order, actionOnNode, sender); } 25 if (right != null) { Right.Traverse(order, actionOnNode, sender); } 26 */ 27 PreorderTraverse(actionOnNode, sender); 28 break; 29 case TraverseOrder.Inorder: 30 /* recursive inorder traverse 31 if (left != null) { Left.Traverse(order, actionOnNode, sender); } 32 actionOnNode(this, sender); 33 if (right != null) { Right.Traverse(order, actionOnNode, sender); } 34 */ 35 InorderTraverse(actionOnNode, sender); 36 break; 37 case TraverseOrder.Postorder: 38 /* recursive postorder traverse 39 if (left != null) { Left.Traverse(order, actionOnNode, sender); } 40 if (right != null) { Right.Traverse(order, actionOnNode, sender); } 41 actionOnNode(this, sender); 42 */ 43 PostorderTraverse(actionOnNode, sender); 44 break; 45 default: 46 break; 47 } 48 } 49 50 void PreorderTraverse<T1>(Action<BinaryTreeNode<T>, T1> actionOnNode, T1 sender) 51 { 52 var stack = new Stack<BinaryTreeNode<T>>(); var stackReady4Visit = new Stack<bool>(); 53 54 stack.Push(this); stackReady4Visit.Push(false); 55 56 while (stack.Count > 0) 57 { 58 var node = stack.Pop(); var ready4Visit = stackReady4Visit.Pop(); 59 if (node == null) { continue; } 60 if (ready4Visit) 61 { 62 actionOnNode(node, sender); 63 } 64 else 65 { 66 stack.Push(node.Right); stackReady4Visit.Push(false); 67 stack.Push(node.Left); stackReady4Visit.Push(false); 68 stack.Push(node); stackReady4Visit.Push(true); 69 } 70 } 71 } 72 73 void InorderTraverse<T1>(Action<BinaryTreeNode<T>, T1> actionOnNode, T1 sender) 74 { 75 var stack = new Stack<BinaryTreeNode<T>>(); var stackReady4Visit = new Stack<bool>(); 76 77 stack.Push(this); stackReady4Visit.Push(false); 78 79 while (stack.Count > 0) 80 { 81 var node = stack.Pop(); var ready4Visit = stackReady4Visit.Pop(); 82 if (node == null) { continue; } 83 if (ready4Visit) 84 { 85 actionOnNode(node, sender); 86 } 87 else 88 { 89 stack.Push(node.Right); stackReady4Visit.Push(false); 90 stack.Push(node); stackReady4Visit.Push(true); 91 stack.Push(node.Left); stackReady4Visit.Push(false); 92 } 93 } 94 } 95 96 void PostorderTraverse<T1>(Action<BinaryTreeNode<T>, T1> actionOnNode, T1 sender) 97 { 98 var stack = new Stack<BinaryTreeNode<T>>(); var stackReady4Visit = new Stack<bool>(); 99 100 stack.Push(this); stackReady4Visit.Push(false);101 102 while (stack.Count > 0)103 {104 var node = stack.Pop(); var ready4Visit = stackReady4Visit.Pop();105 if (node == null) { continue; }106 if (ready4Visit)107 {108 actionOnNode(node, sender);109 }110 else111 {112 stack.Push(node); stackReady4Visit.Push(true);113 stack.Push(node.Right); stackReady4Visit.Push(false);114 stack.Push(node.Left); stackReady4Visit.Push(false);115 }116 }117 }118 }
以上三种遍历实现代码行数一模一样，如同递归遍历一样，只有三行核心代码的先后顺序有区别。用原作者的话解释就是："得以统一三种更简单的非递归遍历方法的基本思想：有重合元素的局部有序一定能导致整体有序。基于这种思想，我就构思三种非递归遍历的统一思想：不管是前序，中序，后序，只要我能保证对每个结点而言，该结点，其左子结点，其右子结点都满足以前序/中序/后序的访问顺序,整个二叉树的这种三结点局部有序一定能保证整体以前序/中序/后序访问，因为相邻的局部必有重合的结点，即一个局部的"根"结点是另外一个局部的"子"结点。"。
层次遍历
层次遍历类似图的广度优先搜索。
1 public class BinaryTree<T> 2 { 3 BinaryTreeNode<T> Node { get;set; } 4 public BinaryTree(BinaryTreeNode<T> node) 5 { 6 this.Node = node; 7 } 8 9 public void Traverse<T1>(TraverseOrder order, Action<BinaryTreeNode<T>, T1> actionOnNode, T1 sender)10 {11 if (actionOnNode == null) { return; }12 var node = this.Node;13 if (node == null) { return; }14 15 switch (order)16 {17 case TraverseOrder.Preorder:18 node.Traverse(order, actionOnNode, sender);19 break;20 case TraverseOrder.Inorder:21 node.Traverse(order, actionOnNode, sender);22 break;23 case TraverseOrder.Postorder:24 node.Traverse(order, actionOnNode, sender);25 break;26 case TraverseOrder.Layer:27 TraverseLayer<T1>( actionOnNode, sender);28 break;29 default:30 break;31 }32 }33 34 private void TraverseLayer<T1>(Action<BinaryTreeNode<T>, T1> actionOnNode, T1 sender)35 {36 var queue = new Queue<BinaryTreeNode<T>>();37 queue.Enqueue(this.Node);38 while (queue.Count > 0)39 {40 var element = queue.Dequeue();41 if (element != null)42 {43 actionOnNode(element, sender);44 var left = element.Left;45 var right = element.Right;46 if (left != null) { queue.Enqueue(left); }47 if (right != null) { queue.Enqueue(right); }48 }49 }50 }51 }
借用Traverse方法实现其他功能
1 public class BinaryTree<T> 2 { 3 /* 略 */ 4 5 public int GetNodeCount() 6 { 7 var counter = new NodeCounter(); 8 this.Traverse<NodeCounter>(TraverseOrder.Preorder, actNodeCount, counter); 9 return counter.Count;10 }11 12 static Action<BinaryTreeNode<T>, NodeCounter> actNodeCount = new Action<BinaryTreeNode<T>, NodeCounter>((node, c) => c.Count++);13 14 public int GetLeaveCount()15 {16 var counter = new LeaveCounter();17 this.Traverse<LeaveCounter>(TraverseOrder.Preorder, actLeaveCount, counter);18 return counter.Count;19 }20 21 static Action<BinaryTreeNode<T>, LeaveCounter> actLeaveCount = new Action<BinaryTreeNode<T>, LeaveCounter>(22 (node, c) => 23 {24 if (node != null)25 {26 if (node.Left == null && node.Right == null)27 {28 c.Count++;29 }30 }31 });32 33 public int GetNonLeaveCount()34 {35 var counter = new NonLeaveCounter();36 this.Traverse<NonLeaveCounter>(TraverseOrder.Preorder, actNonLeaveCount, counter);37 return counter.Count;38 }39 40 static Action<BinaryTreeNode<T>, NonLeaveCounter> actNonLeaveCount = new Action<BinaryTreeNode<T>, NonLeaveCounter>(41 (node, c) => 42 {43 if (node != null)44 {45 if (node.Left != null || node.Right != null)46 {47 c.Count++;48 }49 }50 });51 }52 53 class NonLeaveCounter54 {55 public int Count { get;set; }56 }57 58 class LeaveCounter59 {60 public int Count { get;set; }61 }62 63 class NodeCounter64 {65 public int Count { get;set; }66 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。