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