递归地将项目添加到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)
-以递归方式将项目添加到BSTprint(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
。
相关文章