2
У меня есть большая задача сделать это как упражнение для структур данных и алгоритмов, а частью этого является изменение этой структуры данных дерева для печати дерева в алфавитном порядке. Я не буду публиковать целая задача, потому что она огромна. Я застрял в последней части, которая просит меня изменить данное дерево Data Structure для печати дерева в алфавитном порядке. Я застрял на нем пару дней, и простые понятия не имеют, как это сделать. Спасибо, спасибо. Мое мнение таково, что я должен каким-то образом изменить метод printTreeRecursive().Структура данных дерева печати по алфавиту
Например, текущая структура данных будет печатать дерево, как это:
c: d c b a
(Первый добавил ребенок напечатан последний).
где с: корень и DCBA его дети
но им должен изменить его, чтобы выглядеть следующим образом:
c: a b c d
Вот структура данных:
public class SLLTree<E> implements Tree<E> {
// SLLNode is the implementation of the Node interface
class SLLNode<P> implements Node<P> {
// Holds the links to the needed nodes
SLLNode<P> parent, sibling, firstChild;
// Hold the data
P element;
public SLLNode(P o) {
element = o;
parent = sibling = firstChild = null;
}
public P getElement() {
return element;
}
public void setElement(P o) {
element = o;
}
}
protected SLLNode<E> root;
public SLLTree() {
root = null;
}
public Node<E> root() {
return root;
}
public Tree.Node<E> parent(Tree.Node<E> node) {
return ((SLLNode<E>) node).parent;
}
public int childCount(Tree.Node<E> node) {
SLLNode<E> tmp = ((SLLNode<E>) node).firstChild;
int num = 0;
while (tmp != null) {
tmp = tmp.sibling;
num++;
}
return num;
}
public void makeRoot(E elem) {
root = new SLLNode<E>(elem);
}
public Node<E> addChild(Node<E> node, E elem) {
SLLNode<E> tmp = new SLLNode<E>(elem);
SLLNode<E> curr = (SLLNode<E>) node;
tmp.sibling = curr.firstChild;
curr.firstChild = tmp;
tmp.parent = curr;
return tmp;
}
public void remove(Tree.Node<E> node) {
SLLNode<E> curr = (SLLNode<E>) node;
if (curr.parent != null) {
if (curr.parent.firstChild == curr) {
// The node is the first child of its parent
// Reconnect the parent to the next sibling
curr.parent.firstChild = curr.sibling;
} else {
// The node is not the first child of its parent
// Start from the first and search the node in the sibling list
// and remove it
SLLNode<E> tmp = curr.parent.firstChild;
while (tmp.sibling != curr) {
tmp = tmp.sibling;
}
tmp.sibling = curr.sibling;
}
} else {
root = null;
}
}
class SLLTreeIterator<T> implements Iterator<T> {
SLLNode<T> start, current;
public SLLTreeIterator(SLLNode<T> node) {
start = node;
current = node;
}
public boolean hasNext() {
return (current != null);
}
public T next() throws NoSuchElementException {
if (current != null) {
SLLNode<T> tmp = current;
current = current.sibling;
return tmp.getElement();
} else {
throw new NoSuchElementException();
}
}
public void remove() {
if (current != null) {
current = current.sibling;
}
}
}
public Iterator<E> children(Tree.Node<E> node) {
return new SLLTreeIterator<E>(((SLLNode<E>) node).firstChild);
}
void printTreeRecursive(Node<E> node, int level) {
if (node == null)
return;
int i;
SLLNode<E> tmp;
for (i = 0; i < level; i++)
System.out.print(" ");
System.out.println(node.getElement().toString());
tmp = ((SLLNode<E>) node).firstChild;
while (tmp != null) {
printTreeRecursive(tmp, level + 1);
tmp = tmp.sibling;
}
}
public void printTree() {
printTreeRecursive(root, 0);
}
public int countMaxChildren() {
return countMaxChildrenRecursive(root);
}
int countMaxChildrenRecursive(SLLNode<E> node) {
int t = childCount(node);
SLLNode<E> tmp = node.firstChild;
while (tmp != null) {
t = Math.max(t, countMaxChildrenRecursive(tmp));
tmp = tmp.sibling;
}
return t;
}
}
public interface Tree<E> {
// //////////Accessors ////////////
public Tree.Node<E> root();
public Tree.Node<E> parent(Tree.Node<E> node);
public int childCount(Tree.Node<E> node);
// //////////Transformers ////////////
public void makeRoot(E elem);
public Tree.Node<E> addChild(Tree.Node<E> node, E elem);
public void remove(Tree.Node<E> node);
// //////////Iterator ////////////
public Iterator<E> children(Tree.Node<E> node);
// //////Inner interface for tree nodes ////////
public interface Node<E> {
public E getElement();
public void setElement(E elem);
}
}
public class SLLTreeTest {
public static void main(String[] args) {
Tree.Node<String> a, b, c, d;
SLLTree<String> t = new SLLTree<String>();
t.makeRoot("C:");
a = t.addChild(t.root, "Program files");
b = t.addChild(a, "CodeBlocks");
c = t.addChild(b, "codeblocks.dll");
c = t.addChild(b, "codeblocks.exe");
b = t.addChild(a, "Nodepad++");
c = t.addChild(b, "langs.xml");
d = c;
c = t.addChild(b, "readme.txt");
c = t.addChild(b, "notepad++.exe");
a = t.addChild(t.root, "Users");
b = t.addChild(a, "Darko");
c = t.addChild(b, "Desktop");
c = t.addChild(b, "Downloads");
c = t.addChild(b, "My Documents");
c = t.addChild(b, "My Pictures");
b = t.addChild(a, "Public");
a = t.addChild(t.root, "Windows");
b = t.addChild(a, "Media");
t.printTree();
t.remove(d);
t.printTree();
System.out.println("The maximum number of children is "
+ t.countMaxChildren());
}
}
Не могли бы вы также показать, как вы инициализируете дерево перед печатью? – August
Хорошо, я добавлю пример класса SLLTreeTest. – mouseepaad
Никто не имеет понятия? :/ – mouseepaad