递归地将项目添加到BST

recursively adding an item to the BST(递归地将项目添加到BST)

问题描述

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

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。

这篇关于递归地将项目添加到BST的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！