当前位置：首页 > article >正文

C# 数据结构之【树】C#树

article 2024/11/25 21:59:57

以二叉树为例进行演示。二叉树每个节点最多有两个子节点。

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 + " ");
        }

    }
}

运行结果