二叉树的遍历--C#程序举例二叉树的遍历
关于二叉树的介绍笨男孩前面写过一篇博客
二叉树的简单介绍以及二叉树的存储结构
遍历方案
二叉树的遍历分为以下三种：
先序遍历：遍历顺序规则为【根左右】
中序遍历：遍历顺序规则为【左根右】
后序遍历：遍历顺序规则为【左右根】
举例说明如下图是一个颗二叉树：
图1一棵二叉树
上图是一颗二叉树：
先序遍历（根左右）：ABCDEFGHI
中序遍历（左根右）：BDCAEHGIF
后序遍历（左右根）：DCBHIGFEA
C#代码举例
一棵简单的二叉树结构
1 public class BinaryTree 2 { 3 public string Value; 4 public BinaryTree lChild; 5 public BinaryTree rChild; 6 }
先序遍历
1 //先序遍历-递归实现 //根左右 2 public static void PreorderTraversal(BinaryTree tree) 3 { 4 if (tree == null) 5 return; 6 System.Console.WriteLine(tree.Value); 7 PreorderTraversal(tree.lChild); 8 PreorderTraversal(tree.rChild); 9 }
中序遍历
1 //中序遍历-递归实现 //左根右 2 public static void InorderTraversal(BinaryTree tree) 3 { 4 if (tree == null) 5 return; 6 7 InorderTraversal(tree.lChild); 8 System.Console.WriteLine(tree.Value); 9 InorderTraversal(tree.rChild); 10 }
后序遍历
1 //后序遍历-递归实现 //左右根 2 public static void PostorderTraversal(BinaryTree tree) 3 { 4 if (tree == null) 5 return; 6 7 PostorderTraversal(tree.lChild); 8 PostorderTraversal(tree.rChild); 9 System.Console.WriteLine(tree.Value); 10 }
程序测试
创建一棵如下图所示的二叉树
1 /// <summary> 2 /// 创建一颗二叉树 3 /// </summary> 4 /// <returns></returns> 5 public static BinaryTree CreatBinaryTree() 6 { 7 //创建一个tree 8 BinaryTree tree = new BinaryTree(); 9 10 //添加二叉树的值 11 tree.Value = "A"; 12 13 //添加该树左子树 14 tree.lChild = new BinaryTree() 15 { 16 Value = "B", 17 lChild = null, 18 rChild = new BinaryTree() 19 { 20 Value = "C", 21 lChild = new BinaryTree() 22 { 23 Value = "D", 24 }, 25 rChild = null, 26 } 27 }; 28 29 //添加该树右子树 30 tree.rChild = new BinaryTree() 31 { 32 Value = "E", 33 lChild = null, 34 rChild = new BinaryTree() 35 { 36 Value = "F", 37 lChild = new BinaryTree() 38 { 39 Value = "G", 40 lChild = new BinaryTree() 41 { 42 Value = "H", 43 lChild = null, 44 rChild = null 45 }, 46 rChild = new BinaryTree() 47 { 48 Value = "I", 49 lChild = null, 50 rChild = null 51 52 } 53 }, 54 rChild = null 55 } 56 57 }; 58 return tree; 59 }
测试代码
1 static void Main(string[] args) 2 { 3 BinaryTree tree = CreatBinaryTree(); 4 5 Console.WriteLine("------------先序遍历------------"); 6 PreorderTraversal(tree); 7 8 Console.WriteLine("------------中序遍历------------"); 9 InorderTraversal(tree); 10 Console.WriteLine("------------后序遍历------------"); 11 PostorderTraversal(tree); 12 13 Console.Read(); 14 }
测试结果：
有了上面的知识储备，那么涉及到二叉树的问题，那基本就有点普了，下面看一道试题（面试的题，具体是哪个公司就不说了，免得大伙百度搜索）
试题：找出一颗二叉树中是否存在值与某一个值的相等的元素 (记忆里大概是这个意思)
这就很简单了，实际上就考一个二叉树的遍历，这里写一个先序遍历查找的例子
查找节点函数
1 /// <summary> 2 /// 先序遍历查找二叉树中是否存在某一个值，并返回该元素 3 /// </summary> 4 /// <param name="tree"></param> 5 /// <param name="value"></param> 6 /// <returns></returns> 7 public static BinaryTree PreorderTraversalSelectValue(BinaryTree tree, string value) 8 { 9 if (tree == null) 10 { 11 return null; 12 } 13 if (tree.Value == value) 14 { 15 return tree; 16 } 17 //找左子树 18 BinaryTree node = PreorderTraversalSelectValue(tree.lChild,value); 19 if (node != null) 20 { 21 return tree; 22 } 23 else 24 { 25 //找右子树 26 node = PreorderTraversalSelectValue(tree.rChild,value); 27 return node; 28 } 29 }
测试代码：
1 BinaryTree tree2 = PreorderTraversalSelectValue(tree,"F"); 2 if (tree2 == null) 3 { 4 Console.WriteLine("该二叉树中不存在F"); 5 } 6 else 7 { 8 Console.WriteLine("该二叉树中存在值为{0}的元素",tree2.Value); 9 } 10 BinaryTree tree3 = PreorderTraversalSelectValue(tree, "J"); 11 if (tree3 == null) 12 { 13 Console.WriteLine("该二叉树中不存该元素J"); 14 } 15 else 16 { 17 Console.WriteLine("该二叉树中存在值为{0}的元素", tree3.Value); 18 }
程序运行结果：
有需要源代码工程的可以自己下载
程序源代码工程下载
以上是一个面试经历，面试官给的试题，当时我记得用先序遍历做的，用笔写（确实和用VS写感觉是不一样的，O(∩_∩)O哈哈~）自我感觉当时做的并不满意，公司就不给大伙公开了，这是个职业素养问题，免得大伙来百度搜索，为此特意总结出这么一篇来！关于二叉树，这里还有一篇二叉链表存储的博客，喜欢可以去查看！