• 【算法与数据结构】--常见数据结构--树与图

    一、二叉树

    二叉树（Binary Tree）是一种重要的树状数据结构，它由节点构成，每个节点最多有两个子节点：一个左子节点和一个右子节点。这种结构使得二叉树在计算机科学和编程中具有广泛的应用。

    1.1 二叉树的基本特性：
    1. 根节点：二叉树的顶部节点称为根节点，它是树的起点。
    2. 子树：树中的任何节点都可以作为根节点形成子树。
    3. 父节点和子节点：节点可以有零、一个或两个子节点。父节点指向子节点。
    4. 叶子节点：没有子节点的节点称为叶子节点。
    5. 深度：从根节点到某个节点的路径长度称为深度。根节点深度为0。
    6. 高度：树中最深节点的深度称为树的高度。
    7. 层次：节点的深度加1就是该节点所在的层次。
    1.2 二叉树的常见类型：
    1. 二叉搜索树（Binary Search Tree，BST）：一种有序二叉树，左子树上的节点值小于根节点，右子树上的节点值大于根节点，这个性质使得二叉搜索树用于快速查找、插入和删除操作。
    2. 平衡二叉树：一种特殊的二叉搜索树，保持树的左右子树高度差不超过1，以保持查找操作的高效性能。常见的平衡二叉树包括AVL树和红黑树。
    3. 二叉堆（Binary Heap）：一种特殊的二叉树结构，通常用于实现堆排序和优先队列。有最大堆和最小堆两种类型。
    1.3 二叉树的遍历方式：
    1. 前序遍历（Preorder Traversal）：先访问根节点，然后依次遍历左子树和右子树。
    2. 中序遍历（Inorder Traversal）：先遍历左子树，然后访问根节点，最后遍历右子树。对于二叉搜索树，中序遍历的结果是有序的。
    3. 后序遍历（Postorder Traversal）：先遍历左子树，然后遍历右子树，最后访问根节点。
    4. 层次遍历（Level Order Traversal）：按层次从上到下，从左到右遍历树的节点。
    1.4 C#和Java示例代码：

    下面是C#和Java示例代码，演示如何创建一个简单的二叉树、进行前序遍历和中序遍历。
    C# 示例：

    using System;

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;
    }
}

class BinaryTree
{
    public TreeNode Root { get; set; }

    public BinaryTree()
    {
        Root = null;
    }

    public void PreorderTraversal(TreeNode node)
    {
        if (node == null)
            return;

        Console.Write(node.Data + " ");
        PreorderTraversal(node.Left);
        PreorderTraversal(node.Right);
    }

    public void InorderTraversal(TreeNode node)
    {
        if (node == null)
            return;

        InorderTraversal(node.Left);
        Console.Write(node.Data + " ");
        InorderTraversal(node.Right);
    }
}

class Program
{
    static void Main()
    {
        BinaryTree tree = new BinaryTree();
        tree.Root = new TreeNode(1);
        tree.Root.Left = new TreeNode(2);
        tree.Root.Right = new TreeNode(3);
        tree.Root.Left.Left = new TreeNode(4);
        tree.Root.Left.Right = new TreeNode(5);

        Console.WriteLine("Preorder Traversal:");
        tree.PreorderTraversal(tree.Root);

        Console.WriteLine("\nInorder Traversal:");
        tree.InorderTraversal(tree.Root);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64

    Java 示例：

    class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    public TreeNode(int data) {
        this.data = data;
        left = null;
        right = null;
    }
}

class BinaryTree {
    TreeNode root;

    public BinaryTree() {
        root = null;
    }

    void preorderTraversal(TreeNode node) {
        if (node == null)
            return;

        System.out.print(node.data + " ");
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }

    void inorderTraversal(TreeNode node) {
        if (node == null)
            return;

        inorderTraversal(node.left);
        System.out.print(node.data + " ");
        inorderTraversal(node.right);
    }
}

public class Main {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new TreeNode(1);
        tree.root.left = new TreeNode(2);
        tree.root.right = new TreeNode(3);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.right = new TreeNode(5);

        System.out.print("Preorder Traversal: ");
        tree.preorderTraversal(tree.root);

        System.out.print("\nInorder Traversal: ");
        tree.inorderTraversal(tree.root);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54

    这些示例演示了如何创建一个二叉树、进行前序和中序遍历，以及如何在C#和Java中实现二叉树的基本操作。二叉树是一种重要的数据结构，用于各种应用，包括数据库索引、解析表达式、图形处理等。

    二、图的基本概念

    图（Graph）是一种抽象数据结构，用于表示多个对象之间的关系。图是计算机科学中非常重要的数据结构，用于解决许多实际问题。以下是图的基本概念：

    1. 节点（Node 或 Vertex）：图中的基本元素，通常表示一个实体或对象。节点可以有不同的属性和类型，具体取决于应用。节点可以包含有关实体的信息，如名称、权重等。
    2. 边（Edge 或 Arc）：图中连接两个节点的线，表示节点之间的关系。边可以是有向的（从一个节点到另一个节点）或无向的（没有方向）。通常，边可能具有权重，用于表示关系的强度或成本。
    3. 顶点数（Vertex Count）：图中节点的总数。
    4. 边数（Edge Count）：图中边的总数。
    5. 路径（Path）：在图中，路径是一系列相邻的节点，它们通过边相连。路径的长度可以通过经过的边数或权重来度量。
    6. 有向图（Directed Graph）：也称为有向图，图中的边具有方向。在有向图中，从一个节点到另一个节点的边是单向的。
    7. 无向图（Undirected Graph）：在无向图中，图中的边没有方向，可以双向移动。
    8. 环（Cycle）：在图中，如果一条路径可以回到起始节点，形成一个闭合的环，那么该路径被称为环。
    9. 连通性（Connectivity）：一个图或图中的一部分被称为连通的，如果从任何一个节点到另一个节点都存在路径。
    10. 度数（Degree）：节点的度数是与该节点相连的边的数量。在有向图中，分为入度（In-Degree）和出度（Out-Degree）。
    11. 子图（Subgraph）：一个图的子集，包括一些节点和连接这些节点的边。
    12. 稀疏图和稠密图：稀疏图是具有相对较少边的图，而稠密图具有相对较多的边。

    图是一种非常通用的数据结构，它在许多领域中都有广泛的应用，包括网络分析、社交网络、路线规划、数据库系统、编译器设计、图像处理等。不同类型的图和图算法被用于不同的问题，如最短路径问题、网络流问题、最小生成树问题等。了解这些基本概念是理解和使用图的关键。

    三、常见图算法

    图算法是解决图数据结构中的各种问题的算法。以下是一些常见的图算法，以及它们的简要介绍和C#、Java的代码示例：

    3.1 深度优先搜索（DFS）：
    • 算法介绍：DFS 用于遍历图，从一个起始节点开始，沿着一条路径尽可能深入，直到无法再继续。然后，回溯到上一个节点，继续深入其他路径，直到所有节点都被访问。
    • 应用：查找连通组件、拓扑排序、解决迷宫问题等。
    • C# 示例：
    using System;
 using System.Collections.Generic;

 class Graph
 {
     private int V; // 节点数
     private List<int>[] adj; // 邻接表

     public Graph(int v)
     {
         V = v;
         adj = new List<int>[v];
         for (int i = 0; i < v; i++)
         {
             adj[i] = new List<int>();
         }
     }

     public void AddEdge(int v, int w)
     {
         adj[v].Add(w);
     }

     public void DFS(int v)
     {
         bool[] visited = new bool[V];
         DFSUtil(v, visited);
     }

     private void DFSUtil(int v, bool[] visited)
     {
         visited[v] = true;
         Console.Write(v + " ");

         foreach (int neighbor in adj[v])
         {
             if (!visited[neighbor])
             {
                 DFSUtil(neighbor, visited);
             }
         }
     }
 }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • Java 示例：
    import java.util.LinkedList;

class Graph {
    private int V; // 节点数
    private LinkedList<Integer> adj[];

    public Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    public void addEdge(int v, int w) {
        adj[v].add(w);
    }

    public void DFS(int v) {
        boolean[] visited = new boolean[V];
        DFSUtil(v, visited);
    }

    private void DFSUtil(int v, boolean[] visited) {
        visited[v] = true;
        System.out.print(v + " ");

        for (int neighbor : adj[v]) {
            if (!visited[neighbor]) {
                DFSUtil(neighbor, visited);
            }
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    3.2 广度优先搜索（BFS）：
    • 算法介绍：BFS 用于遍历图，从起始节点开始，首先访问所有与该节点直接相邻的节点，然后逐层向外扩展。
    • 应用：最短路径问题、网络分析、查找最近的连接等。
    • C# 示例：
    using System;
using System.Collections.Generic;

class Graph
{
    private int V; // 节点数
    private List<int>[] adj; // 邻接表

    public Graph(int v)
    {
        V = v;
        adj = new List<int>[v];
        for (int i = 0; i < v; i++)
        {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int v, int w)
    {
        adj[v].Add(w);
    }

    public void BFS(int s)
    {
        bool[] visited = new bool[V];
        Queue<int> queue = new Queue<int>();

        visited[s] = true;
        queue.Enqueue(s);

        while (queue.Count != 0)
        {
            s = queue.Dequeue();
            Console.Write(s + " ");

            foreach (int neighbor in adj[s])
            {
                if (!visited[neighbor])
                {
                    visited[neighbor] = true;
                    queue.Enqueue(neighbor);
                }
            }
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • Java 示例：
    import java.util.LinkedList;
import java.util.Queue;

class Graph {
    private int V; // 节点数
    private LinkedList<Integer> adj[];

    public Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    public void addEdge(int v, int w) {
        adj[v].add(w);
    }

    public void BFS(int s) {
        boolean[] visited = new boolean[V];
        Queue<Integer> queue = new LinkedList<>();

        visited[s] = true;
        queue.add(s);

        while (!queue.isEmpty()) {
            s = queue.poll();
            System.out.print(s + " ");

            for (int neighbor : adj[s]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    3.3 最短路径算法（Dijkstra、Bellman-Ford、Floyd-Warshall）：
    • 算法介绍：这些算法用于查找图中两个节点之间的最短路径。Dijkstra 适用于带正权边的图，Bellman-Ford 适用于带负权边的图，Floyd-Warshall 适用于任何图。
    • 应用：路线规划、导航、网络路由、最短路径查找等。
    • C# 示例：以Dijkstra算法为例，下面是C#示例
    using System;
using System.Collections.Generic;

class Graph
{
    private int V; // 节点数
    private int[,] graph; // 邻接矩阵

    public Graph(int v)
    {
        V = v;
        graph = new int[V, V];
    }

    public void AddEdge(int v, int w, int weight)
    {
        graph[v, w] = weight;
        graph[w, v] = weight;
    }

    public void Dijkstra(int start)
    {
        int[] dist = new int[V];
        bool[] visited = new bool[V];

        for (int i = 0; i < V; i++)
        {
            dist[i] = int.MaxValue;
            visited[i] = false;
        }

        dist[start] = 0;

        for (int count = 0; count < V - 1; count++)
        {
            int u = MinDistance(dist, visited);
            visited[u] = true;

            for (int v = 0; v < V; v++)
            {
                if (!visited[v] && graph[u, v] != 0 && dist[u] != int.MaxValue &&
                    dist[u] + graph[u, v] < dist[v])
                {
                    dist[v] = dist[u] + graph[u, v];
                }
            }
        }

        PrintSolution(dist);
    }

    private int MinDistance(int[] dist, bool[] visited)
    {
        int min = int.MaxValue;
        int minIndex = -1;

        for (int v = 0; v < V; v++)
        {
            if (!visited[v] && dist[v] <= min)
            {
                min = dist[v];
                minIndex = v;
            }
        }

        return minIndex;
    }

    private void PrintSolution(int[] dist)
    {
        Console.WriteLine("Vertex \t Distance from Source");
        for (int i = 0; i < V; i++)
        {
            Console.WriteLine(i + " \t " + dist[i]);
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • Java 示例：以Dijkstra算法为例，下面是Java示例
    import java.util.Arrays;

class Graph {
    private int V; // 节点数
    private int[][] graph; // 邻接矩阵

    public Graph(int v) {
        V = v;
        graph = new int[V][V];
    }

    public void addEdge(int v, int w, int weight) {
        graph[v][w] = weight;
        graph[w][v] = weight;
    }

    public void dijkstra(int start) {
        int[] dist = new int[V];
        boolean[] visited = new boolean[V];

        for (int i = 0; i < V; i++) {
            dist[i] = Integer.MAX_VALUE;
            visited[i] = false;
        }

        dist[start] = 0;

        for (int count = 0; count < V - 1; count++) {
            int u = minDistance(dist, visited);
            visited[u] = true;

            for (int v = 0; v < V; v++) {
                if (!visited[v] && graph[u][v] != 0 && dist[u] != Integer.MAX_VALUE &&
                        dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }

        printSolution(dist);
    }

    private int minDistance(int[] dist, boolean[] visited) {
        int min = Integer.MAX_VALUE;
        int minIndex = -1;

        for (int v = 0; v < V; v++) {
            if (!visited[v] && dist[v] <= min) {
                min = dist[v];
                minIndex = v;
            }
        }

        return minIndex;
    }

    private void printSolution(int[] dist) {
        System.out.println("Vertex \t Distance from Source");
        for (int i = 0; i < V; i++) {
            System.out.println(i + " \t " + dist[i]);
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63

    这是一些常见的图算法及其C#和Java的代码示例。这些算法在许多领域中都有广泛的应用，包括网络分析、路线规划、社交网络分析等。根据具体问题需求，选择合适的算法和数据结构来解决问题非常重要。

    四、总结

    二叉树是一种树状数据结构，每个节点最多有两个子节点。常见的二叉树类型包括二叉搜索树、平衡二叉树和二叉堆。遍历方式有前序、中序、后序和层次遍历。图是用于表示多个对象之间关系的数据结构，具有节点和边，包括有向图和无向图。常见图算法包括深度优先搜索、广度优先搜索和最短路径算法。 C#和Java代码示例演示了如何创建二叉树和实现这些算法。二叉树和图在计算机科学中有广泛的应用。

  • 相关阅读:
    改进你的c#代码的5个技巧
    如何快速定位BUG？BUG定位技巧及测试人员定位的N板斧
    肝了一星期，终于把堆的创建、插入、删除和堆排序肝完了（超详细图文讲解）
    Pytest电商项目实战(上)
    07 【动态组件 组件注册】
    突破编程_C++_设计模式（观察者模式）
    防止SQL注入的四种方案
    【Pyqt5】windows和linux安装Pyqt5+designer
    FFmpeg滤镜效果--镜头聚焦和移动走位
    最佳实践：REST API 的 HTTP 请求参数
  • 原文地址：https://blog.csdn.net/gangzhucoll/article/details/133844805