java - 获取二叉树每个节点的级别

Question

我正在学习实现二叉树，我试图获取每个节点的级别，我尝试从根节点遍历到叶节点，但无法得到正确的答案。这是我的代码

public class BinaryTree
 {
 private Node root;

 /**
   Constructs an empty tree.
 */
 public BinaryTree() { 
   root=new Node();
   root = null; }

 /**
   Constructs a tree with one node and no children.
  @param rootData the data for the root
 */
 public BinaryTree(Object rootData)
 { root=new Node();
 root.data=rootData;
  }

 /**
   Constructs a binary tree.
  @param rootData the data for the root
  @param left the left subtree
  @param right the right subtree
  */
 public BinaryTree(Object rootData, BinaryTree left, BinaryTree right)
  {
   root = new Node();
   root.data = rootData;
   root.left = left.root;
   root.right = right.root;
}

 class Node
  {
  public Object data;
  public Node left;
  public Node right;

  public String printTree(int level)
  {

     return null;

   }
  }

  int getLevelUtil(Node n, Object data, int level)
 {
   if (n == null)
       return 0;

   if (n.data == data)
       return level;

   int downlevel = getLevelUtil(n.left, data, level+1);
   if (downlevel != 0)
       return downlevel;

   downlevel = getLevelUtil(n.right, data, level+1);
   return downlevel;
  }

  /* Returns level of given data value */
 int getLevel(Node n, int data)
  {
   return getLevelUtil(n,data,1);
  }

 /**
  Returns the height of the subtree whose root is the given node.
  @param n a node or null
    @return the height of the subtree, or 0 if n is null
 */
 private static int height(Node n)
  {
   if (n == null) { return 0; }
   else { return 1 + Math.max(height(n.left), height(n.right)); }
  }

 /**
  Returns the height of this tree.
  @return the height
 */

 public Object data() 
 { 
 return root.data;
 }

 /**
  Gets the left subtree of this tree
  @return the left child of the root
 */
 public BinaryTree left()
 {
  return null;
 }

 /**
  Gets the right subtree of this tree
  @return the right child of the root
 */
 public BinaryTree right()
 {
  return null;
 }

   /**
   * Sets a new right child
   * @param child the new right child
   */
   public void setRight(BinaryTree child)
    {
   root.right=child.root;
  }

  /**
   * Sets a new left child
  * @param child the new left child
  */
  public void setLeft(BinaryTree child)
  {
   root.left=child.root;
  }

  public void setData(Object data)
 {
   root.data=data;
  }

  public boolean isLeaf()
  {
  if(root.left==null&& root.right==null)
      return true;
  else
      return false;
 }

  public String printTree()
  {
  String s=new String();

  s= s+printTree(root);
  return s;

  }

  public String printTree(Node parent)
 { String s=new String();

   if (parent == null) { return ""+" "; }
   s=s+parent.data+"(level:"+(height(parent))+")";

 s=s+printTree(parent.left);

 s=s+ printTree(parent.right);


   return(s);
     }


  }

有什么方法可以做到这一点......？？？

Answer 1

我认为您需要为每个节点添加 PARENT 属性。如果您有 Parent 属性，下面的代码可以帮助您获取节点的级别:

class Node
{
    public Object data;
    public Node left;
    public Node right;

    public Node parent;



    public int getLevel() {
        int level = 1;
        Node n = this;
        while (n != null && n.parent != null) {
            level++;
            n = n.parent;
        }
        return level;
   }
}

注意:

• 我假设 ROOT 节点的 Level = 1

• 数据成员不应使用 PUBLIC，可以使用 Private、Protected 和 Getter/setter。

• 其他注意事项:不应该使用RECURSIVE，它可能会导致StackOverflowException。