原资料的 Console.WriteLine、override string 与所在专栏表明它是 C# 示例,原 Java 语言标记和部分 String 写法混杂。本文新增一个 .NET 8 的完整 C# 程序,保留原 URL、来源与历史片段。
三种顺序分别做什么
前序先根再左子树、右子树;中序先左、根、右;后序先左、右、根。这里是一棵普通二叉树,不假定编号满足二叉搜索树顺序。中序输出因此不保证按编号排序,查找最坏需要访问全部节点,不能当作 O(log n) 查找。
可编译的完整文件
将以下三个文件放入同一目录,项目无第三方包,NuGet 源清空便于离线复现。程序核对三种顺序、查找命中、未找到与空树。
<Project Sdk="Microsoft.NET.Sdk">
<PropertyGroup><OutputType>Exe</OutputType><TargetFramework>net8.0</TargetFramework><ImplicitUsings>enable</ImplicitUsings><Nullable>enable</Nullable></PropertyGroup>
</Project>
<configuration><packageSources><clear /></packageSources></configuration>
enum Order { Pre, In, Post }
sealed record Node(int Id, string Name, Node? Left = null, Node? Right = null);
static class Program
{
static IEnumerable<Node> Traverse(Node? node, Order order)
{
if (node is null) yield break;
if (order == Order.Pre) yield return node;
foreach (var child in Traverse(node.Left, order)) yield return child;
if (order == Order.In) yield return node;
foreach (var child in Traverse(node.Right, order)) yield return child;
if (order == Order.Post) yield return node;
}
static Node? Find(Node? root, int id, Order order) =>
Traverse(root, order).FirstOrDefault(node => node.Id == id);
static void Main()
{
var root = new Node(1, "root", new Node(2, "left"),
new Node(3, "right", new Node(5, "right-left"), new Node(4, "right-right")));
var expected = new Dictionary<Order, string>
{
[Order.Pre] = "1,2,3,5,4",
[Order.In] = "2,1,5,3,4",
[Order.Post] = "2,5,4,3,1"
};
foreach (var order in Enum.GetValues<Order>())
{
var actual = string.Join(",", Traverse(root, order).Select(node => node.Id));
if (actual != expected[order] || Find(root, 5, order)?.Name != "right-left"
|| Find(root, 99, order) is not null || Find(null, 5, order) is not null)
throw new InvalidOperationException("Traversal or search mismatch");
Console.WriteLine($"{order}={actual}; found=5; missing=null");
}
}
}
dotnet run --project TreeTraversal.csproj
本次 .NET 8 输出:
Pre=1,2,3,5,4; found=5; missing=null
In=2,1,5,3,4; found=5; missing=null
Post=2,5,4,3,1; found=5; missing=null
Find 返回所选遍历顺序中的第一个匹配节点;如果编号允许重复,返回对象可能随顺序变化。递归栈深度与树高有关,本例没有验证极深链状树、循环引用或性能。yield 使遍历按需生成,FirstOrDefault 在命中后停止枚举,不需要异常“弹出”模拟查找。
下一步阅读
原资料片段(未重建原环境)
下方保留原资料的上下文、示例与截图;本轮验证只对应上方新增文件,未将旧运行结果记为本轮结果。
前言
树的前中后序遍历 是根据前中后序的顺序来查找,找到了则弹出。
正文
节点模型:
public class HeroNode
{
private int no;
private string name;
private HeroNode left;
private HeroNode right;
public HeroNode(int no, string name) {
this.no = no;
this.name = name;
}
public int getNo() {
return no;
}
public void setNo(int no)
{
this.no = no;
}
public string getName()
{
return name;
}
public void setName(string name)
{
this.name = name;
}
public HeroNode getLeft()
{
return left;
}
public void setLeft(HeroNode left)
{
this.left = left;
}
public HeroNode getRight()
{
return right;
}
public void setRight(HeroNode right)
{
this.right = right;
}
public override string ToString()
{
return "姓名:" + name + "编号:" + no;
}
//编写前序遍历的方法 是根、左、右
public void preOrder() {
Console.WriteLine(this);
if (this.left != null)
{
this.left.preOrder();
}
if (this.right != null)
{
this.right.preOrder();
}
}
//中序遍历 是左、根、右
public void infixOrder() {
if (this.left != null)
{
this.left.infixOrder();
}
Console.WriteLine(this);
if (this.right != null)
{
this.right.infixOrder();
}
}
// 后续遍历为 左、右、根
public void postOrder()
{
if (this.left != null)
{
this.left.postOrder();
}
if (this.right != null)
{
this.right.postOrder();
}
Console.WriteLine(this);
}
//前序遍历查找
public HeroNode preOrderSearch(int no)
{
HeroNode resNode = null;
record();
if (this.no == no)
{
return this;
}
if (this.left != null)
{
resNode=this.left.preOrderSearch(no);
}
if (resNode != null)
{
return resNode;
}
if (this.right != null)
{
resNode = this.right.preOrderSearch(no);
}
return resNode;
}
//中序遍历查找
public HeroNode infixOrderSearch(int no)
{
HeroNode resNode = null;
if (this.left != null)
{
resNode = this.left.infixOrderSearch(no);
}
if (resNode != null)
{
return resNode;
}
record();
if (this.no == no)
{
return this;
}
if (this.right != null)
{
resNode = this.right.infixOrderSearch(no);
}
return resNode;
}
//后序遍历查找
public HeroNode postOrderSearch(int no)
{
HeroNode resNode = null;
if (this.left != null)
{
resNode = this.left.postOrderSearch(no);
}
if (resNode != null)
{
return resNode;
}
if (this.right != null)
{
resNode = this.right.postOrderSearch(no);
}
if (resNode != null)
{
return resNode;
}
record();
if (this.no == no)
{
resNode=this;
}
return resNode;
}
public void record()
{
Console.WriteLine("查找步骤为:名字" + this.name + " 编号:" + this.no);
}
}
树模型:
public class BinaryTree
{
private HeroNode root;
public void setRoot(HeroNode root)
{
this.root = root;
}
//前序遍历
public void preOrder()
{
if (this.root != null)
{
this.root.preOrder();
}
else
{
Console.WriteLine("二叉树为空,无法遍历");
}
}
//中序遍历
public void infixOrder()
{
if (this.root != null)
{
this.root.infixOrder();
}
else
{
Console.WriteLine("二叉树为空,无法遍历");
}
}
//后序遍历
public void postOrder()
{
if (this.root != null)
{
this.root.postOrder();
}
else
{
Console.WriteLine("二叉树为空,无法遍历");
}
}
//前序遍历查找
public HeroNode preOrderSearch(int no)
{
if (root != null)
{
return this.root.preOrderSearch(no);
} else {
return null;
}
}
//中序遍历查找
public HeroNode infixOrderSearch(int no)
{
if (root != null)
{
return this.root.infixOrderSearch(no);
}else
{
return null;
}
}
//后序遍历查找
public HeroNode postOrderSearch(int no)
{
if (root != null)
{
return this.root.postOrderSearch(no);
}else {
return null;
}
}
}
测试:
static void Main(string[] args)
{
//先需要创建一颗二叉树
BinaryTree binaryTree = new BinaryTree();
//创建需要的结点
HeroNode root = new HeroNode(1, "宋江");
HeroNode node2 = new HeroNode(2, "吴用");
HeroNode node3 = new HeroNode(3, "卢俊义");
HeroNode node4 = new HeroNode(4, "林冲");
HeroNode node5 = new HeroNode(5, "关胜");
//设置节点
root.setLeft(node2);
root.setRight(node3);
node3.setRight(node4);
node3.setLeft(node5);
binaryTree.setRoot(root);
//前序遍历
Console.WriteLine("前序遍历查找");
binaryTree.preOrderSearch(5);
Console.WriteLine("中序遍历查找");
binaryTree.infixOrderSearch(5);
Console.WriteLine("后续遍历查找");
binaryTree.postOrderSearch(5);
Console.ReadKey();
}
测试结果:
版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: