18、数据结构与算法 C#:树的前中后序遍历查找

将误标 Java 的树遍历资料明确为 C#,用 .NET 8 完整程序核对三种遍历、命中、未找到与空树。

简明结论

遍历顺序决定访问与首次命中顺序;普通二叉树的中序并不保证排序,示例语言应明确为 C#。

原资料的 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();
}

测试结果:
 

版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: