پیاده سازی یک درخت با نود هایی از آرایه

[Ma_Y_R]

سلام دوستان.برای پیاده سازی یک درخت که هر نود اون باید یه آرایه باشه به نظرتون از چه ابزارهایی استفاده کنم بهتره؟؟؟array list,link list،آرایه یا هرچیز دیگه ای که فکر میکنید بهتره.من باید این درخت رو تولید کرده و هر دفعه اونو سرچ کنم.خواهش میکنم راهنمایی کنید.

[ahmad.mo74]

سلام

مشخصا نگفتید که چه نوع درختی میخواید (binary یا tree) و اینکه چه نوع سرچی؟

توی جاوا کلاس هایی مثل TreeSet و TreeMap هست که اینا باینری هستن و برای سرچ هم از binary search tree استفاده میشه توشون، در واقع اصل کاری TreeMap هست و TreeSet از متدهای کلاس TreeMap استفاده میکنه...

برای پیاده سازی tree هم میتونی از Map استفاده کنی.

مثال :


package com.treesample.test;


import java.util.Map;
import java.util.TreeMap;
import java.util.TreeSet;


public class Main {


public static void main(String[] args) {
Map<String, TreeSet<Integer>> studentMarks = new TreeMap<>();
studentMarks.put("ali", new TreeSet<Integer>() {
{
add(14);
add(16);
}
});
studentMarks.put("reza", new TreeSet<Integer>() {
{
add(15);
add(19);
}
});
studentMarks.put("jafar", new TreeSet<Integer>() {
{
add(17);
add(16);
}
});
studentMarks.put("gholam", new TreeSet<Integer>() {
{
add(20);
add(20);
}
});
System.out.println(studentMarks);
}


}



پیاده سازی tree :


package com.treesample.test;


import java.util.*;
import java.util.function.Consumer;
import java.util.stream.Collectors;


/**
* @author avb
*/
public class Tree<E> {


private final Map<E, Node<E>> nodes = new TreeMap<>();
private Node<E> root;


private static class Node<E> {


private E e;
private Node<E> parent;
private List<Node<E>> children = new ArrayList<>();


private Node(E e, Node<E> parent) {
this.e = e;
this.parent = parent;
}


private E getParent() {
return parent.e;
}


private List<E> getChildren() {
return children.stream().map(child -> child.e).collect(Collectors.toList());
}


@Override
public String toString() {
return "\"" + e + "\"" + (children.size() > 0 ? " : " + children : "");
}


}


public void put(E e, E parent) {
Objects.requireNonNull(e);
Node<E> parentNode = parent == null ? null : nodes.get(parent);
Node<E> node = new Node<>(e, parentNode);
if (nodes.containsKey(e)) {
remove(e);
}
nodes.put(e, node);
if (root == null) {
root = node;
} else if (parentNode == null) {
node.children.add(root);
root.parent = node;
root = node;
} else {
parentNode.children.add(node);
}
}


public void putIfAbsent(E e, E parent) {
Objects.requireNonNull(e);
if (nodes.containsKey(e)) {
put(e, parent);
}
}


public E getParent(E e) {
Node<E> node = nodes.get(e);
return node == null ? null : node.getParent();
}


public List<E> getChildren(E e) {
Node<E> node = nodes.get(e);
return node == null ? null : node.getChildren();
}


public void remove(E e) {
Node<E> node = nodes.remove(e);
if (node == null) {
return;
}
if (node.children.size() > 0) {
Node<E> child = node.children.remove(0);
node.children.forEach(c -> c.parent = child);
child.children.addAll(0, node.children);
if (Objects.equals(root.e, node.e)) {
child.parent = null;
root = child;
} else {
node.parent.children.remove(node);
node.parent.children.add(child);
}
} else {
if (Objects.equals(root.e, node.e)) {
root = null;
} else {
node.parent.children.remove(node);
}
}
}


public List<E> removeChildren(E e) {
Objects.requireNonNull(e);
Node<E> node = nodes.get(e);
if (node == null) {
return null;
}
List<E> children = node.getChildren();
children.forEach(nodes::remove);
node.children.clear();
return children;
}


public int size() {
return nodes.size();
}


public void clear() {
root = null;
nodes.clear();
}


public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
nodes.forEach((e, eNode) -> action.accept(e));
}


@Override
public String toString() {
if (root == null) {
return "{}";
}
return '{' + root.toString() + '}';
}


public static void main(String[] args) {
Tree<String> tree = new Tree<>();
tree.put("a", null);
tree.put("b", "a");
tree.put("c", "a");
tree.put("d", "b");
tree.put("e", "c");
System.out.println(tree);
System.out.println(tree.getChildren("a"));
System.out.println(tree.getParent("e"));
System.out.println(tree.removeChildren("a"));
System.out.println(tree);
}


}

[Ma_Y_R]

public class node<integer> {

private int[] data=new int[6];
private node<int[]> parent;
private LinkedList<node<int[]>> children;
private int depth;
node<int[]> next;}

با سلام.در واقع من یه کلاس نودی دارم که بخش Data داره که این بخش یه آرایست.به نظرتون این تعریفی ک الان من نوشتم ایرادی داره؟؟