英文:
I don't understand how to move portions of a tree
问题
我的目标是创建一个二叉搜索树（BST）：当我插入一个节点时，我将其插入为根节点，如果要插入的元素已经存在，则将现有元素移动到根节点。如果你移除一个节点，将该节点的父节点移动到根节点。
class BSTNode {
BSTNode left = null;
BSTNode rigth = null;
int data = 0;
public BSTNode() {
super();
}
public BSTNode(int data) {
this.left = null;
this.rigth = null;
this.data = data;
}
@Override
public String toString() {
return "BSTNode [left=" + left + ", rigth=" + rigth + ", data=" + data + "]";
}
}
class BinarySearchTree {
BSTNode root = null;
public BinarySearchTree() {
}
public void insert(int data) {
BSTNode node = new BSTNode(data);
if (root == null) {
root = node;
return;
} else {
BSTNode currentNode = root;
BSTNode parentNode = null;
if (currentNode.data == data)
return;
if (currentNode.data > data) {
parentNode = node;
BSTNode existing = searchNode(data);
if (existing != null) {
parentNode = existing;
parentNode.rigth = currentNode;
} else {
parentNode.rigth = currentNode;
}
} else {
parentNode = node;
BSTNode existing = searchNode(data);
if (existing != null) {
parentNode = existing;
parentNode.left = currentNode;
} else {
parentNode.left = currentNode;
}
}
root = parentNode;
}
}
public BSTNode searchNode(int data) {
if (empty())
return null;
return searchNode(data, root);
}
public BSTNode searchNode(int data, BSTNode node) {
if ((node.left != null && node.left.data == data) || (node.rigth != null && node.rigth.data == data)) {
if (node.left.data == data) {
BSTNode existing = node.left;
node.left = null;
return existing;
}
if (node.rigth.data == data) {
BSTNode existing = node.rigth;
node.rigth = null;
return existing;
} else if (node.data > data)
return searchNode(data, node.left);
else if (node.data < data)
return searchNode(data, node.rigth);
}
return null;
}
}
我还没有处理删除操作。我在插入函数中遇到了困难。
我的想法是：
如果新插入的节点比旧的根节点小，将旧的根节点替换为新的根节点，并将旧的根节点挂接到新的根节点的左侧；如果新插入的节点比旧的根节点大，将旧的根节点替换为新的根节点，并将旧的根节点挂接到新的根节点的右侧。此外，如果旧的根节点比新的根节点小，要在旧的根节点的右分支中寻找第一个比新根节点大的元素，并将其移动并挂接为新根节点的右分支；反之亦然。
但我无法做到。有人能帮助我吗？
也许在结束这个“问题”之前，我还需要一些关于删除操作的建议。
英文:
My goal is to create a BST that: when I insert a node I insert it at the root, if the element to insert already exists move the existing element to the root. If you remove a node, move the father of that node to the root.
class BSTNode {
BSTNode left = null;
BSTNode rigth = null;
int data = 0;
public BSTNode() {
super();
}
public BSTNode(int data) {
this.left = null;
this.rigth = null;
this.data = data;
}
@Override
public String toString() {
return "BSTNode [left=" + left + ", rigth=" + rigth + ", data=" + data + "]";
}
}
class BinarySearchTree {
BSTNode root = null;
public BinarySearchTree() {
}
public void insert(int data) {
BSTNode node = new BSTNode(data);
if (root == null) {
root = node;
return;
}else{
BSTNode currentNode = root;
BSTNode parentNode = null;
if (currentNode.data == data)
return;
if (currentNode.data > data) {
parentNode = node;
BSTNode existing = searchNode(data);
if (existing != null){
parentNode = existing;
parentNode.rigth = currentNode;
}else{
parentNode.rigth = currentNode;
}
} else {
parentNode = node;
BSTNode existing = searchNode(data);
if (existing != null){
parentNode = existing;
parentNode.left = currentNode;
}else{
parentNode.left = currentNode;
}
}
root = parentNode;
}
}
public BSTNode searchNode(int data) {
if (empty())
return null;
return searchNode(data, root);
}
public BSTNode searchNode(int data, BSTNode node) {
if ((node.left != null && node.left.data == data) || (node.rigth != null && node.rigth.data == data)) {
if (node.left.data == data){
BSTNode existing = node.left;
node.left = null;
return existing;
}
if(node.rigth.data == data){
BSTNode existing = node.rigth;
node.rigth = null;
return existing;
}
else if (node.data > data)
return searchNode(data, node.left);
else if (node.data < data)
return searchNode(data, node.rigth);
}
return null;
}
I haven't dealt with the Delete yet. I'm stuck at the insert function.
My idea here was:
replace the old root with the new one and hook the old root to the left of the new one, if it is smaller, or to the right if it is larger. Also if it is the old root is smaller than the new one, look for the first largest element of the new root on the right branch of the old root, and move it by hooking it as the right branch of the new root. In reverse if it is bigger.
But I'm not capable. Can anyone help me?
Maybe before closing the "question" I would also need some advice on the delete operation.
专注分享java语言的经验与见解，让所有开发者获益！
评论