理解Java中的树和图:探索非线性数据结构的应用与实现
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.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));
}
}
登录后复制
在上面的示例中,我们定义了一个Node类来表示二叉树的节点,以及BinarySearchTree类来表示二叉搜索树。我们可以使用insert方法向树中插入元素,使用search方法来搜索元素。
import java.util.*;
class Graph {
private int V;
private LinkedList[] 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 queue = new LinkedList();
visited[s] = true;
queue.add(s);
while (queue.size() != 0) {
s = queue.poll();
System.out.print(s + " ");
Iterator 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);
}
}
登录后复制
在上述示例中,我们使用邻接链表来表示图的数据结构。我们定义了Graph类,其中addEdge方法用于添加边,BFS方法用于进行广度优先搜索遍历。在示例中,我们从顶点2开始进行BFS遍历,并打印出遍历顺序。
以上就是深入探索Java中树和图的非线性数据结构应用和实现方法的详细内容,更多请关注每日运维网(www.mryunwei.com)其它相关文章!