N叉树深度和度数算法

Question

我在使用一些算法时遇到了一些问题，这些算法应该 return 一棵树的最大度数（一个节点的最大子节点数）和深度（最长分支的维度）。看起来它们对某些树结构有效，而对其他一些则无效。如果我对代码做错了什么，有人可以告诉我吗？

我的树结构是

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());
}

这个returns 5但是应该return6

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());
}

这应该 return 3 但 returns 2

e1 到 e7 是整数。

Answer 1

两件事。

首先，您的 searchAux 函数是错误的。下面一行没有用，因为它的 return 值被忽略了：

searchAux(node.getSibling(), key);

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

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

如果您访问的节点没有子节点，则为 false，无论其键值如何；这意味着随后的 return node; 指令可能会被执行 即使您 returning 的节点不是您正在寻找的父节点 .

这就是您的第二个示例中发生的情况。这是前三个insert后的情况（竖线=父子，横线=兄弟）：

e1
|
e2--e3

到目前为止一切顺利。但是，当您调用 tree.insert(e3, e4) 时，会访问 e3 但会被忽略； e2 取而代之的是 returned（尝试遍历您的代码）。因此：

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);
}

（附带说明，在 return 秒后不需要 else 秒。）

N叉树深度和度数算法

N-ary tree depth and degree algorithm

java

n-ary-tree

depth