Trouver la profondeur d'un nœud donné dans un arbre k-aire

J'ai un arbre k-aire, et je dois être capable de calculer la profondeur des nœuds une fois l'arbre construit.Trouver la profondeur d'un nœud donné dans un arbre k-aire

est ici la classe arbre

public class DirectoryTree implements Serializable { 

    private TreeNode Root; 
    private int numNodes; 
    private TreeNode Focus; 
    private LocalDateTime date; 
    private long totalSizeOnDisk;

Heres la classe TreeNode:

public class TreeNode implements Serializable{ 

    private FileSystemEntry data; 
    private boolean directory; 
    private TreeNode parent; 
    private ArrayList<TreeNode> children; 
    private int numChildren; 
    private int nodeKey; 
    private int depth;

Mon idée originale était de faire la queue tous les nœuds de l'arbre de largeur premier ordre, et en utilisant la variable numNodes , sauter des nœuds enfants donnés et définir leur profondeur pour être quelle que soit la variable de compteur, mais cela ne fonctionne pas depuis lors, je ne peux pas lire les nœuds sautés afin de trouver la profondeur de leurs enfants. Il semble donc que j'ai besoin d'un algorithme récursif ou quelque chose comme ça. Peut-être une largeur modifiée première ?:

public void BFTree() { 

    Queue<TreeNode> queue = new LinkedList<TreeNode>(); 
    queue.add(this.Root); 
    TreeNode current; 
    while ((current = queue.poll()) != null) { 
     BFTree(current, queue); 
    } 
} 

private void BFTree(TreeNode n, Queue<TreeNode> queue) { 

    System.out.println(n.getData().getName()); 
    if (n.isDirectory()) { 
     for (int i = 0; i < n.getChildren().size(); i++) { 
      queue.add(n.getChildren().get(i)); 
     } 
    } 
}

Source

2017-03-28 Richardweber32

Vous pouvez d'abord chercher l'arbre en profondeur ou en largeur. La clé est que lorsque vous avez besoin de calculer la profondeur d'un nœud, vous avez toujours accès à la profondeur du parent. Il y a plusieurs façons d'y parvenir. – Gene

Depth first search ... lorsque vous effectuez un appel récursif, passez la profondeur du parent + 1 pour définir le niveau de profondeur suivant. – mba12

Oh ouais cela a beaucoup de sens ... Je vais juste récursivement accéder à chaque nœud et faire le parent de profondeur + 1. Si simple haha. Merci pour l'aide – Richardweber32

Au cas où quelqu'un d'autre trébuche sur ce

Je viens de modifier ma largeur d'abord Traversal ceci:

if(!n.equals(this.Root)){ 
     n.setDepth(n.getParent().getDepth() + 1); 
}

Il est évident que la profondeur d'un nœud donné est juste son profondeur du parent + 1. La racine n'a pas de parent, donc je l'ai juste défini comme 0 dans la fonction accès/cas de base

Source

2017-03-29 19:21:47 Richardweber32

Trouver la profondeur d'un nœud donné dans un arbre k-aire

Répondre

Questions connexes