N 元树深度和度数算法

Question

我在使用几种算法时遇到了一些问题，这些算法应该返回树的最大次数(节点的最大子级数)和深度(最长分支的维度)。看起来有些树结构可以工作，而另一些则不工作。有人可以告诉我我是否在代码上做错了什么吗？

我的树结构是

public class Tree<T> {
public Node<T> root;
public Tree() {
root = null;
}

我的节点结构为：

public class Node<T>{
public T elem; 
private Node<T> father;
private Node<T> child; 
private Node<T> sibling;
private T epsilon;
public Node(T elem){   
this.elem = elem;
this.father = null;
this.child = null;
this.sibling = null;  
}

度数算法为：

public int degree(){
int breadth = 0;
int max = 0;
return auxDegree(this.root, breadth, max);
}
public int auxDegree(Node<T> node, int count, int maxChild){
if(node!=null){
if(node.getChild()!=null){ 
maxChild = Math.max(auxDegree(node.getChild(), 0, maxChild), auxDegree(node.getSibling(), 0, maxChild));
count = countSibling(node.getChild()) + 1;
return (count>maxChild) ? count : maxChild;
}else return maxChild;
}else return maxChild;
}

最后，深度算法：

public int depth(){
int deepness = 0;
return auxDepth(this.root, deepness);
}
public int auxDepth(Node<T> node, int maxDepth){
if(node!=null){
if(node.getChild()!=null){
maxDepth = Math.max(maxDepth, auxDepth(node.getChild(), maxDepth));
maxDepth = maxDepth + 1;
return maxDepth;
}else{
return maxDepth;
}
}else return maxDepth;
}

插入代码为：

public Node<T> search(T key){
return searchAux(this.root, key);
}
private Node<T> searchAux(Node<T> node, T key){
if(node == null) 
return null;
else{
while(node.getChild() != null && key != node.getElem()){
node = node.getChild();
searchAux(node.getSibling(), key); 
}
}  
return node;  
}
public void insert(T father_key, T child_key){
if(IsEmpty())
this.root = new Node<T>(child_key);
else{
Node<T> node = new Node<T>(child_key);
Node<T> father = search(father_key);
if(father.getChild() == null){
father.setChild(node);
node.setParent(father);
}else{
if (father.getChild() != null){
Node<T> brother = father.getChild(); 
while(brother.getSibling() != null){
brother = brother.getSibling(); 
}
brother.setSibling(node);
node.setParent(father);
}
}
}
}

不起作用的结构是：

public void Test_Depth(){
tree.insert(null, e2);
tree.insert(e2, e3);
tree.insert(e2, e1);
tree.insert(e3, e4);
tree.insert(e4, e5);
tree.insert(e5, e6);
tree.insert(e6, e7);
assertEquals(6,tree.depth());
}

这将返回 5，但应返回 6

public void Test_Depth(){
tree.insert(null, e1);
tree.insert(e1, e2);
tree.insert(e1, e3);
tree.insert(e3, e4);
tree.insert(e3, e5);
tree.insert(e3, e6);
assertEquals(3,tree.degree());
}

这应该返回 3 但返回 2

e1 到 e7 是整数。

Answer 1

两件事。

首先，你的searchAux功能是错误的。以下行是无用的，因为它的返回值被忽略：

searchAux(node.getSibling(), key);

此外，while循环允许将子节点分配给错误的父节点。条件

node.getChild() != null && key != node.getElem()

如果您正在访问的节点没有子节点，则为 false，无论其键值如何;这意味着即使您返回的节点不是您要查找的父节点，也可能执行随后的return node;指令。

例如，在您的第二个示例中，就会发生这种情况。这是前三个inserts之后的情况(垂直线=父子，水平线=兄弟姐妹)：

e1
|
e2--e3

目前为止，一切都好。但是，当您调用tree.insert(e3, e4)时，会访问 e3 但会被忽略;将返回 E2 代替它(尝试遍历代码)。因此：

e1
|
e2--e3
|
e4

顺便说一下，这是第二棵树最后的样子：

e1
|
e2--e3
|
e4
|
e5
|
e6

第二：据我所知，第一棵树是正确的，即使你的搜索算法是错误的。它的深度是 5，而不是 6(根节点的深度为零)：

0: e2
|
1: e3--e1
|
2: e4
|
3: e5
|
4: e6
|
5: e7

话虽如此，以下是递归深度优先搜索的快速草稿：

private Node<T> searchAux(Node<T> node, T key){
if(node == null) 
return null;
if (node.getElem() == key)
return node;
if (node.getChild() != null) {
Node<T> foundNode = searchAux(node.getChild(), key);
if (foundNode != null)
return foundNode;
} 
return searchAux(node.getSibling(), key);
}

(附带说明一下，returns之后不需要elses。