Как отобразить плоскую структуру данных в иерархическую структуру данных (Java)?
Я недавно столкнулся с этим вопросом в практическом тесте для задания.
Предположим, что Вам дают плоскую структуру данных как это:
**Category** **Name** **Parent**
1 electronics 0
2 Television 1
3 21inch 2
4 23inch 2
5 LCD display 2
6 player 1
7 mp3player 6
8 vcd player 6
9 dvd player 6
10 hd quality 8
Теперь от вышеупомянутой плоской структуры данных мы хотим показать что-то как ниже иерархической древовидной структуры.
-Electronics
| -Television
| | -21 inch
| | -23 inch
| | -lcd display
| -Player
| | -mp3player
| | -vcdplayer
| | | -HD display
| | -DVD player
Затем, Если я добавляю другую запись в свой массив как:
11 Test 3
затем это должно показать Test запись чуть ниже 21inch .
Таким образом для этого вида вещи я в настоящее время использую ArrayList и смогли пересечь до второго уровня, но не может сделать так для третьего уровня. Таким образом, каков лучший способ для того, чтобы сделать это?
Спасибо
РЕДАКТИРОВАНИЕ:
Меня попросили создать это понятие с помощью основанного на DOS JAVA-приложения только.
4 ответа
Вот пример кода, который перечисляет их в иерархии с использованием рекурсии. Класс Item имеет список дочерних элементов. Хитрость заключается в добавлении любых новых дочерних элементов к правильному родителю. Вот метод, который я создал для этого:
public Item getItemWithParent(int parentID){
Item result = null;
if(this.categoryID == parentID){
result = this;
} else {
for(Item nextChild : children){
result = nextChild.getItemWithParent(parentID);
if(result != null){
break;
}
}
}
return result;
}
Возможно, есть более эффективный способ, но он работает.
Затем, когда вы хотите добавить новые элементы в свою иерархию, сделайте что-то вроде этого:
public void addItem(int categoryID, String name, int parentID) {
Item parentItem = findParent(parentID);
parentItem.addChild(new Item(categoryID, name, parentID));
}
private Item findParent(int parentID) {
return rootNode.getItemWithParent(parentID);
}
Для фактического отображения я просто передаю «уровень вкладки», в котором указано, насколько далеко вставлять вкладки, а затем увеличиваю его для каждому ребенку нравится это:
public String toStringHierarchy(int tabLevel){
StringBuilder builder = new StringBuilder();
for(int i = 0; i < tabLevel; i++){
builder.append("\t");
}
builder.append("-" + name);
builder.append("\n");
for(Item nextChild : children){
builder.append(nextChild.toStringHierarchy(tabLevel + 1));
}
return builder.toString();
}
Что дает мне следующее:
-electronics
-Television
-21inch
-Test
-23inch
-LCD display
-player
-mp3player
-vcd player
-hd quality
-dvd player
У вас может быть дизайн, вдохновленный Swing TreeModel.
EDIT Когда я говорю это, я имею в виду, что вы можете использовать класс, реализующий подобный интерфейс; заметьте, вы можете даже пойти дальше, чем использовать непосредственно этот интерфейс, поскольку Swing является частью стандартной JRE и доступен везде, где доступна стандартная Java.
Более того, поскольку это интерфейс (а не класс), он является лишь способом структурирования ваших вызовов. Как следствие, вы можете легко использовать его в консольном приложении.
Используя ваш ArrayList в качестве входных данных, потребуется рекурсивный метод для печати всех узлов в иерархическом / древовидном представлении.
Если вы не используете рекурсию, это может быть причиной того, что вы не можете перейти на уровни выше второго, о котором вы говорите.
Некоторые ссылки на рекурсию:
Чтобы быть эффективным, я бы создал что-то вроде этого:
public class Node
{
// My name
public String name;
// My first child. Null if no children.
public Node child;
// The next child after me under the same parent.
public Node sibling;
// The top node in the tree.
public static Node adam;
// Add first node to tree
public Node(String name)
{
this.name=name;
this.child=null;
this.sibling=null;
adam=this;
}
// Add a non-Adam node to the tree.
public Node(String name, Node parent)
{
// Copy my name. Easy part.
this.name=name;
// Make me the first child of my parent. The previous first child becomes
// my sibling. If the previous first child was null, fine, now my sibling is null.
// Note this means that children always add to the front. If this is undesirable,
// we could make this section a little more complicated to impose the desired
// order.
this.sibling=parent.child;
parent.child=this;
// As a new node, I have no children.
this.child=null;
}
// Print the current node and all nodes below it.
void printFamily(int level)
{
// You might want a fancier print function than this, like indenting or
// whatever, but I'm just trying to illustrate the principle.
System.out.println(level+" "+name);
// First process children, then process siblings.
if (child!=null)
child.printFamiliy(level+1);
if (sibling!=null)
sibling.printFamily(level);
}
// Print all nodes starting with adam
static void printFamily()
{
adam.printFamily(1);
}
// Find a node with a given name. Must traverse the tree.
public static Node findByName(String name)
{
return adam.findByName(name);
}
private Node findByNameFromHere(String name)
{
if (this.name.equals(name))
return this;
if (child!=null)
{
Node found=child.findByNameFromHere(name);
if (found!=null)
return found;
}
if (sibling!=null)
{
Node found=sibling.findByNameFromHere(name);
if (found!=null)
return found;
}
return null;
}
// Now we can add by name
public Node(String name, String parentName)
{
super(name, findByName(parentName));
}
}
Обычный отказ от ответственности: этот код - из моей головы, совершенно не проверен.
Если бы я делал это для реального приложения, я бы включил проверку ошибок и, несомненно, всевозможные периферийные вещи.