时间戳

首页 > 解决方案 > 在相同标签的 n 叉树中搜索最低（最深层次）节点

java - 在相同标签的 n 叉树中搜索最低（最深层次）节点

问题描述

这是我的 n 叉树的节点类

import java.util.ArrayList;

public class Node{
    public String label;
    public ArrayList<Node> children;
    public Node(String label){
        this.label =label;
        this.children = new ArrayList<Node>();
    }
    public void addChild(String child){
        Node childNode = new Node(child);
        this.children.add(childNode);
    }
    public void addChild(Node child){
        this.children.add(child);
    }
    public Node findNode(String label){
        if(this.label.equals(label))
            return this;
        for(Node child : this.children)
            if (child.findNode(label) != null)
                return child.findNode(label);
        return null;
    }
}

我需要一个像“ Node findNode(String label)”这样的方法，但给出具有相同标签的最低节点。

此图中的示例

图片

标签： javaarraylisttree

解决方案

修改您Node.class以存储另一个变量，int height当您Tree objectTree从rootNode.

rootNode.getHeight()=0 默认情况下。从rootNode函数 in的简单遍历Node.class将如下所示：

//note : This assumes you are at any Node. The root Node will have height = 0 ~important
public Node findLabel(String label){ 
   Node tempNode = null;
   assert this.getHeight()!=null;
   if(this.label.equals(label)){
     tempNode = this;
   }
   //traverse this' children 
   for(Node child : this.children){
         child.setHeight(this.getHeight()+1); //setting children height
         Node t = child.findNode(label);
         if(t!=null){
           if(tempNode!=null){ 
              if(tempNode.getHeight()>t.getHeight()){
                 tempNode=t;
              }
           }else{
             tempNode=t; //set TempNode = t as tempNode is null as this is our first solution
           }
         }      
    }
  return tempNode; //can be null and Contains the lowest node in the tree with label
}

推荐阅读