Java 实现中的二叉树

Question

我的任务是在 Java 中实现一个 Binary Tree 并对树进行一些操作，例如添加元素或显示树的最小或最大元素。我在解决这个问题时遇到了麻烦，所以如果有人能提供帮助，我将不胜感激。我们可以使用的所有方法和变量都已经在 class 中，所以我们只需要使用那些。到目前为止我的代码如下：

/**
 * A binary tree with int values.
 */
class Tree {



    /**
     * The value of this node in the tree.
     */
    private int node;
    

    /**
     * The left subtree.
     */
    private Tree lhs;

    /**
     * The right subtree.
     */
    private Tree rhs;

    /**
     * Creates a new tree with the value node.
     * @param node The value of this node in the tree.
     */
    public Tree(int node) {
        this.node = node;
        this.lhs = null;
        this.rhs = null;

    }

    /**
     * Method to add a node to the tree. Duplicates will be refused.
     *
     * @param insert the new number
    */
    public void add(int insert) {
        

    }

    /**
     * Method to calculate the depth of a tree. It is defined by the maximal
     * number of edges to a leaf.
     *
     * @return the depth of the tree
    */
    public int depth(Tree tree) {
    // Root being null means tree doesn't exist.
    if (tree == null) {
        return 0;
    }

    // Get the depth of the left and right subtree
    // using recursion.
    int leftDepth = depth(tree.lhs);
    int rightDepth = depth(tree.rhs);

    // Choose the larger one and add the root to it.
    if (leftDepth > rightDepth) {
        return (leftDepth + 1);
    }
    else {
        return (rightDepth + 1);
}
        
        
    }


    /**
     * Method to find a number in the tree.
     *
     * @param wanted the wanted number
     * @return true, if the wanted number exists in the try, else false
    */
    public boolean exists(int wanted) {

    }

    /**
     * Method to find the smallest number in the tree.
     *
     * @return the smallest number in the tree
    */
    public int smallest( int min) {
        while (Tree.lhs != null) {
            Tree.lhs + 1;
        }
            minimum = Tree.lhs
            return min;

    }

    /**
     * Method to find the biggest number in the tree.
     *
     * @return the biggest number in the tree
    */
    public int biggest(int max) {
    while(Tree.rhs != nil) {
        Tree.rhs++;
    }
    return max;
        
    }

    /**
     * Method to check whether a tree is degenerate.
     *
     * @return true if every node has either no or one child node, else false
    */
    public boolean isDegenerate() {

    }

    /**
     * Method that formats the tree into a readable string.
     *
     * @return the formatted string
    */
    public String toString() {

    }
}

这是主要的 class 它假设与以下项目一起工作：

class Main {

    public static void main(String[] args) {

        Tree tree = new Tree(15);

        int[] set1 = {15, 21, 8, 41, 8, 5, 41, 33};
        int[] set2 = {18, 45, 36, 19, 3, 24, 19, 10};

        for (int i = 0; i < set1.length; i++) {
            tree.add(set1[i]);
        }

        System.out.println(tree.toString());
        System.out.println("The depth of the tree is " + tree.depth() + ".");
        System.out.println("Does the number 8 exist in the tree? " + tree.exists(8));
        System.out.println("Does the number 24 exist in the tree? " + tree.exists(24));
        System.out.println(tree.smallest() + " is the smallest number in the tree. ");
        System.out.println(tree.biggest() + " is the biggest number in the tree. ");
        System.out.println("Is the tree degenerate? " + tree.isDegenerate());

        for (int i = 0; i < set2.length; i++) {
            tree.add(set2[i]);
        }

        System.out.println(tree.toString());
        System.out.println("The depth of the tree is " + tree.depth() + ".");
        System.out.println("Does the number 8 exist in the tree? " + tree.exists(8));
        System.out.println("Does the number 24 exist in the tree? " + tree.exists(24));
        System.out.println(tree.smallest() + " is the smallest number in the tree. ");
        System.out.println(tree.biggest() + " is the biggest number in the tree. ");
        System.out.println("Is the tree degenerate? " + tree.isDegenerate());

    }
}

Answer 1

我假设这是一棵二叉树（不是二叉搜索树）。首先，您需要正确定义树 class 和节点 class。我给你树和节点的代码 class 加上 add 方法。 add 方法逐层添加。从那里，您可以完成其余的方法。

import java.util.*;
class Tree {
   private static class Node{
      int data;
      Node left, right;
      Node(int data){
         this.data=data;
      }
   }
   private Node root;
   public void add(int data){
      Node n = new Node(data);
      if (root == null){
        root = n; return;
      }
      Queue<Node> queue = new LinkedList<>();
      queue.add(root);
      while(!queue.isEmpty()){
         Node t = queue.remove();
         if (t.left == null) {
            t.left = n; break;
         }
         else if (t.right == null) {
            t.right = n; break;
         }
         else {
            queue.add(t.left); queue.add(t.right);
         }
      }
   }
}

Java 实现中的二叉树

Binary tree in Java implementation

java

jobs

implementation

binary-tree

binary-search-tree