遍历 二叉树 递归 循环
C#实现二叉树的前序、中序、后序遍历。
- public class BinaryTreeNode
- {
- int value;
- BinaryTreeNode left;
- BinaryTreeNode right;
- /// <summary>
- /// 前序遍历
- /// </summary>
- /// <param name="tree"></param>
- public static void PreOrder(BinaryTreeNode tree)
- {
- if (tree == null)
- return;
- System.Console.Write(tree.value + " ");
- PreOrder(tree.left);
- PreOrder(tree.right);
- }
- /// <summary>
- /// 前序遍历循环实现
- /// </summary>
- /// <param name="tree"></param>
- public static void PreOrderLoop(BinaryTreeNode tree)
- {
- if (tree == null)
- return;
- Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
- BinaryTreeNode node = tree;
- while(node != null || stack.Any()){
- if(node != null)
- {
- stack.Push(node);
- System.Console.Write(node.value + " ");
- node = node.left;
- }
- else
- {
- var item = stack.Pop();
- node = item.right;
- }
- }
- }
- /// <summary>
- /// 中序遍历
- /// </summary>
- /// <param name="tree"></param>
- public static void InOrder(BinaryTreeNode tree)
- {
- if (tree == null)
- return;
- InOrder(tree.left);
- System.Console.Write(tree.value + " ");
- InOrder(tree.right);
- }
- /// <summary>
- /// 中序遍历循环实现
- /// </summary>
- /// <param name="tree"></param>
- public static void InOrderLoop(BinaryTreeNode tree)
- {
- if (tree == null)
- return;
- Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
- BinaryTreeNode node = tree;
- while (node != null || stack.Any())
- {
- if (node != null)
- {
- stack.Push(node);
- node = node.left;
- }
- else
- {
- var item = stack.Pop();
- System.Console.Write(item.value + " ");
- node = item.right;
- }
- }
- }
- /// <summary>
- /// 后序遍历
- /// </summary>
- /// <param name="tree"></param>
- public static void PostOrder(BinaryTreeNode tree)
- {
- if (tree == null)
- return;
- PostOrder(tree.left);
- PostOrder(tree.right);
- System.Console.Write(tree.value + " ");
- }
- /// <summary>
- /// 后序遍历循环实现1
- /// </summary>
- /// <param name="tree"></param>
- public static void PostOrderLoop(BinaryTreeNode tree)
- {
- if (tree == null)
- return;
- Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
- BinaryTreeNode node = tree;
- BinaryTreeNode pre = null;
- stack.Push(node);
- while (stack.Any())
- {
- node = stack.Peek();
- if ((node.left == null && node.right == null) ||
- (pre != null && (pre == node.left || pre == node.right)))
- {
- System.Console.Write(node.value + " ");
- pre = node;
- stack.Pop();
- }
- else
- {
- if (node.right != null)
- stack.Push(node.right);
- if (node.left != null)
- stack.Push(node.left);
- }
- }
- }
- /// <summary>
- /// 后续遍历循环实现2
- /// </summary>
- /// <param name="tree"></param>
- public static void PostOrderLoop2(BinaryTreeNode tree)
- {
- HashSet<BinaryTreeNode> visited = new HashSet<BinaryTreeNode>();
- Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
- BinaryTreeNode node = tree;
- while (node != null || stack.Any())
- {
- if (node != null)
- {
- stack.Push(node);
- node = node.left;
- }
- else
- {
- var item = stack.Peek();
- if (item.right != null && !visited.Contains(item.right))
- {
- node = item.right;
- }
- else
- {
- System.Console.Write(item.value + " ");
- visited.Add(item);
- stack.Pop();
- }
- }
- }
- }
- }
来源: http://www.bubuko.com/infodetail-2316037.html