C# 数据结构之【树】C#树
以二叉树为例进行演示。二叉树每个节点最多有两个子节点。
1. 新建二叉树节点模型
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;namespace DataStructure
{class TreeNode{public int Data { get; set; }public TreeNode Left { get; set; }public TreeNode Right { get; set; }public TreeNode(int data){Data = data;Left = null;Right = null;}}
}
2. 简单应用
using System;namespace DataStructure
{class Program{static async Task Main(string[] args){// 创建二叉树的根节点TreeNode root = new TreeNode(1);TreeNode node2 = new TreeNode(222);TreeNode node3 = new TreeNode(333);// 添加左子节点root.Left = node2;// 添加右子节点root.Right = node3;// 先序遍历二叉树并输出节点值Console.WriteLine("先序遍历二叉树：");PreorderTraversal(root);//添加新的节点TreeNode node4 = new TreeNode(444);TreeNode node5 = new TreeNode(555);TreeNode node6 = new TreeNode(666);TreeNode node7 = new TreeNode(777);TreeNode node8 = new TreeNode(888);node2.Left = node4;node2.Right = node5;node3.Left = node6;node3.Right = node7;node6 .Left = node8;Console.WriteLine("---");Console.WriteLine("先序遍历二叉树：");PreorderTraversal(root);}static void PreorderTraversal(TreeNode node){if (node != null){Console.Write(node.Data + " ");PreorderTraversal(node.Left);PreorderTraversal(node.Right);}}}
}运行输出
3. 应用拓展
3.1 二叉树的应用场景
- 文件系统和目录结构：在文件系统中，目录可以看作是节点，子目录就是子节点，文件可以是叶子节点。这种层次结构类似于二叉树（实际可能是多叉树，但原理类似），方便进行文件和目录的组织、查找和遍历。例如，当要在一个复杂的文件夹结构中查找特定文件时，就需要对这个树形结构进行遍历。
- 表达式求值：二叉树可以用来表示数学表达式。例如，对于表达式
(3 + 4) * 2，可以构建一棵二叉树，其中运算符*为根节点，3 + 4和2分别为左右子树。左子树又可以进一步展开，+为节点，3和4为其子节点。这样的表示方式有助于按照运算符的优先级来计算表达式的值。 - 决策树：在机器学习和数据挖掘中，决策树是一种常用的分类和预测模型。每个节点代表一个属性上的测试，分支代表测试的输出，叶子节点代表类别或值。例如，在判断一个水果是苹果还是橙子时，可以根据颜色、形状等属性构建决策树来进行分类。
- 霍夫曼编码：这是一种用于数据压缩的编码方式。霍夫曼树是一种二叉树，通过统计字符出现的频率构建。频率高的字符对应的编码路径短，频率低的字符编码路径长，从而实现数据的高效压缩。
3.2 关于二叉树常见的算法
3.2.1 遍历算法
- 前序遍历：根节点 -> 左子树 -> 右子树
- 中序遍历：左子树 -> 根节点 -> 右子树
- 后序遍历：左子树 -> 右子树 -> 根节点
二叉树模型用第一小节的模型，分别演示三种遍历算法
using System;namespace DataStructure
{class Program{static async Task Main(string[] args){// 创建二叉树的根节点TreeNode root = new TreeNode(1);TreeNode node2 = new TreeNode(222);TreeNode node3 = new TreeNode(333);// 添加左子节点root.Left = node2;// 添加右子节点root.Right = node3;//添加新的节点TreeNode node4 = new TreeNode(444);TreeNode node5 = new TreeNode(555);TreeNode node6 = new TreeNode(666);TreeNode node7 = new TreeNode(777);TreeNode node8 = new TreeNode(888);node2.Left = node4;node2.Right = node5;node3.Left = node6;node3.Right = node7;node6.Left = node8;Console.WriteLine("先序遍历二叉树：");PreOrder(root);Console.WriteLine("");Console.WriteLine("中序遍历二叉树：");InOrder(root);Console.WriteLine("");Console.WriteLine("后序遍历二叉树：");PostOrder(root);}static void PreorderTraversal(TreeNode node){if (node != null){Console.Write(node.Data + " ");PreorderTraversal(node.Left);PreorderTraversal(node.Right);}}public static void PreOrder(TreeNode root){if (root == null) return;Console.Write(root.Data + " ");PreOrder(root.Left);PreOrder(root.Right);}public static void InOrder(TreeNode root){if (root == null) return;InOrder(root.Left);Console.Write(root.Data + " ");InOrder(root.Right);}public static void PostOrder(TreeNode root){if (root == null) return;PostOrder(root.Left);PostOrder(root.Right);Console.Write(root.Data + " ");}}
}运行结果
