Comprendre les arbres et les graphiques en Java : explorer l'application et la mise en œuvre de structures de données non linéaires
class Node { int data; Node left; Node right; public Node(int item) { data = item; left = right = null; } } class BinarySearchTree { Node root; public BinarySearchTree() { root = null; } public void insert(int data) { root = insertRec(root, data); } private Node insertRec(Node root, int data) { if (root == null) { root = new Node(data); return root; } if (data < root.data) root.left = insertRec(root.left, data); else if (data > root.data) root.right = insertRec(root.right, data); return root; } public boolean search(int data) { return searchRec(root, data); } private boolean searchRec(Node root, int data) { if (root == null) return false; if (data == root.data) return true; if (data < root.data) return searchRec(root.left, data); return searchRec(root.right, data); } } public class Main { public static void main(String[] args) { BinarySearchTree bst = new BinarySearchTree(); bst.insert(50); bst.insert(30); bst.insert(70); bst.insert(20); bst.insert(40); bst.insert(60); bst.insert(80); System.out.println("Is 20 present? " + bst.search(20)); System.out.println("Is 100 present? " + bst.search(100)); } }
Dans l'exemple ci-dessus, nous avons défini une classe Node pour représenter les nœuds de l'arbre binaire et la classe BinarySearchTree pour représenter l'arbre de recherche binaire. Nous pouvons utiliser la méthode insert pour insérer des éléments dans l'arborescence et la méthode search pour rechercher des éléments.
import java.util.*; class Graph { private int V; private LinkedList<Integer>[] adjList; public Graph(int v) { V = v; adjList = new LinkedList[v]; for (int i = 0; i < v; ++i) adjList[i] = new LinkedList(); } void addEdge(int v, int w) { adjList[v].add(w); } void BFS(int s) { boolean[] visited = new boolean[V]; LinkedList<Integer> queue = new LinkedList<Integer>(); visited[s] = true; queue.add(s); while (queue.size() != 0) { s = queue.poll(); System.out.print(s + " "); Iterator<Integer> i = adjList[s].listIterator(); while (i.hasNext()) { int n = i.next(); if (!visited[n]) { visited[n] = true; queue.add(n); } } } } } public class Main { public static void main(String args[]) { Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); System.out.println("BFS traversal starting from vertex 2:"); g.BFS(2); } }
Dans l'exemple ci-dessus, nous utilisons des listes chaînées de contiguïté pour représenter la structure de données du graphique. Nous définissons la classe Graph, dans laquelle la méthode addEdge est utilisée pour ajouter des arêtes et la méthode BFS est utilisée pour effectuer un parcours de recherche en largeur d'abord. Dans l'exemple, nous effectuons un parcours BFS à partir du sommet 2 et imprimons l'ordre de parcours.
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!