java - 二叉搜索树递归 - 我需要使用 setLeft 和 right 吗?
问题描述
public class BSTNode {
Profile data = null;
BSTNode l = null;
BSTNode r = null;
public BSTNode(Profile data) {
super();
this.data = data;
}
public Profile getData() { //not sure
return data;
}
public void setData(Profile data) { //not sure
this.data = data;
}
public Profile getProfile() {
return data;
}
public BSTNode getL() {
return l;
}
public void setL(BSTNode l) {
this.l = l;
}
public BSTNode getR() {
return r;
}
public void setR(BSTNode r) {
this.r = r;
}
@Override
public String toString() {
return "BSTNode [data=" + data + ", l=" + l + ", r=" + r + "]";
}
}
public class BST {
BSTNode root = null;
public BST() {
}
public void insertProfile(Profile p) {
BSTNode node = new BSTNode(p);
if (root == null) {
root = node;
return;
}
}
}
到目前为止我所做的一切。如果 root 不为空,我需要它来调用私有递归方法。在那个新方法中,它需要递归调用 BSTNode 的 getL 或 getR。
解决方案
您可以尝试像这样插入:
Node root;
class Node {
Item data;
Node left;
Node right;
public Node(Item e) {
data = e;
}
}
public void insert(Item item) {
root = insert(root, item);
}
private Node insert(Node node, Item item) {
if (node== null) {
return new Node(item);
} else if (item.compareTo(node.data) == 0) {
return node;
} else if (item.compareTo(node.data) < 0) {
node.right = insert(node.right, item);
return node;
} else {
node.left = insert(node.left, item);
return node;
}
}
, 更新版本
public class BST {
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
// Tree building...
tree.insert(new Profile("50"));
tree.insert(new Profile("70"));
tree.insert(new Profile("80"));
tree.insert(new Profile("60"));
tree.insert(new Profile("30"));
tree.insert(new Profile("40"));
tree.insert(new Profile("20"));
System.out.println("\nSearch the node with data 60: " + tree.find(new Profile("60")));
System.out.println("Search the node with data 65: " + tree.find(new Profile("65")));
System.out.println("Search the node with data 20: " + tree.find(new Profile("20")));
System.out.println("Search the node with data 25: " + tree.find(new Profile("25")));
}
static class BinarySearchTree {
private BSTNode root;
public void insert(Profile item) {
root = insert(root, item);
}
private BSTNode insert(BSTNode node, Profile item) {
if (node == null) {
return new BSTNode(item);
} else if (item.id.compareTo(node.data.id) == 0) {
return node;
} else if (item.id.compareTo(node.data.id) < 0) {
node.setR(insert(node.r, item));
return node;
} else {
node.setL(insert(node.l, item));
return node;
}
}
public Profile find(Profile target) {
return find(root, target);
}
private Profile find(BSTNode node, Profile target) {
if (node == null) {
return null;
}
int cmd = target.id.compareTo(node.data.id);
if (cmd == 0) {
return node.data;
} else if (cmd < 0) {
return find(node.getR(), target);
} else {
return find(node.getL(), target);
}
}
}
static class Profile {
String id;
public Profile(String id) {
this.id = id;
}
@Override
public int hashCode() {
return id.hashCode();
}
@Override
public boolean equals(Object obj) {
return this.id.equals(((Profile) obj).id);
}
@Override
public String toString() {
return id;
}
}
static class BSTNode {
Profile data = null;
BSTNode l = null;
BSTNode r = null;
public BSTNode(Profile data) {
super();
this.data = data;
}
public Profile getData() { // not sure
return data;
}
public void setData(Profile data) { // not sure
this.data = data;
}
public Profile getProfile() {
return data;
}
public BSTNode getL() {
return l;
}
public void setL(BSTNode l) {
this.l = l;
}
public BSTNode getR() {
return r;
}
public void setR(BSTNode r) {
this.r = r;
}
@Override
public String toString() {
return "BSTNode [data=" + data + ", l=" + l + ", r=" + r + "]";
}
}
}
, 输出
Search the node with data 60: 60
Search the node with data 65: null
Search the node with data 20: 20
Search the node with data 25: null
推荐阅读
- flutter - sqflite or Shared Preference,flutter中哪个适合本地存储用户数据?
- c# - Collection.Remove(item) 与 ItemClass.Remove()。有约定还是只是口味问题?
- r - 如何在闪亮的上下文中完成任务时重置滑块输入
- r - 右 | 时间序列图中的标签
- woocommerce - 检查 Woocommerce Hook 是否来自 API
- c# - 如何将信息从 AuthorizationFilter 传递给它正在授权的操作?
- python - 有没有办法根据它们的连接程度将 Networkx 图中的节点分组在一起?
- java - 由于 recyclerView 导致 Activity/fragment 滞后
- javascript - firebase.analytics 不是函数
- javascript - 从 asp.net Button Onclick 事件中获取响应对象