递归地将项目添加到BST

2022-03-17 00:00:00 binary-search-tree java

我正在尝试创建一个将项目添加到树中的方法,然后我希望将此树打印到控制台。我有一个继承的类,基于它我需要编写所需的方法:

public abstract class BinaryTreeNode {
    protected int data; // value stored in the node
    protected BinaryTreeNode left, right; // left and right sub-trees

    // constructor
    public BinaryTreeNode(int data) {
        this.data = data;
    }

    // recursively adds an item to the BST
    // @param new data to be stored in the new node
    public abstract void addBSTRecursion(int newNode);

    // prints the tree
    // for example, for a tree:
    //        7
    //    6        8
    // 2     7  4     9
    //
    // write:
    //
    //      2
    //   6
    //      7
    // 7
    //      4
    //   8
    //      9

    // method pseudocode
    //if there is a left subtree then print the left one (recursive call)
    //write out gaps (depending on level), write out data, go to new line
    //if it is right, print the right one (recursive call)
    //@param level the distance of the node from the root. We start from 0.
    public abstract void print(int level);

}
addBSTRecursion(int newNode)-以递归方式将项目添加到BST
print(int level)-如果有左边的子树,则打印左边的子树(递归调用),写出间隙(取决于级别),写出数据,转到新行,如果正确,打印右边的子树(递归调用) 以下是我设法做到的:

public class Node extends BinaryTreeNode {
    public Node(int data) {
        super(data);
    }

    @Override
    public void addBSTRecursion(int newNode) {
        if (data < this.data) {
            if (left != null) {
                left.addBSTRecursion(newNode);
            } else {
                left = new Node(newNode);
            }
        } else {
            if (right != null) {
                right.addBSTRecursion(newNode);
            } else {
                right = new Node(newNode);
            }
        }
    }

    @Override
    public void print(int level) {
        if(this.left != null)this.left.print(level+1);
        for(int n =0; n<level; n++) System.out.print(" ");
        System.out.println(data);
        if(this.right != null)this.right.print(level+1);
    }
}

我的输出:

10
 5
  14

我想收到:

   5
10
   14

解决方案

这将始终为false,因为它将this.data与自身进行比较:

    if (data < this.data) {

应该是:

    if (newNode < this.data) {

NB:调用参数newNode具有误导性,因为它不是Node类型,而是整数。也可以称之为newData

相关文章