我需要在这个实现中编写后继和前身,但是我不知道没有父类如何做到这一点。你能建议如何最好地制作这些方法吗?它是TreeNode类
public class TreeNodee<K extends Comparable<K>> {
public K data;
int counter;
public TreeNodee<K> left, right;
public int height;
public int bf;
TreeNodee parent;
public TreeNodee(K data, TreeNodee parent) {
this.data = data;
counter = 1;
this.parent = parent;
}
public TreeNodee(K data) {
this.data = data;
counter = 1;
}
}
和AVL树:
public class AVL<T extends Comparable<T>> {
private TreeNodee<T> root;
private int size;
public void add(T data) {
if (contains(data)){
root.counter++;
return;
}
TreeNodee<T> newNode = new TreeNodee<T>(data);
root = add(root,newNode);
size++;
}
public boolean contains(T data) {
if (isEmpty())return false;
return contains(root,data);
}
private boolean contains(TreeNodee<T> current, T n){
if(current==null)return false;
if(compare(current.data,n) == 0){
return true;
}
else{
if(contains(current.right,n)){return true;}
else if(contains(current.left,n)){return true;}
return false;
}
}
private TreeNodee<T> add(TreeNodee<T> current, TreeNodee<T> n){
if (current == null){
n.bf = 0;
n.height = 0;
return n;
}
if (compare(n.data,current.data)>0){
current.right = rotate(add(current.right,n));
}
else{
current.left = rotate(add(current.left,n));
}
current = rotate(current);
return current;
}
public T remove(T data) {
if(!contains(data)){
return null;
}
root = rotate(remove(root,data));
size--;
return data;
}
private TreeNodee<T> remove(TreeNodee<T> current, T n){
if (compare(current.data,n)==0){
if(current.right == null && current.left== null){
return null;
}
else if(current.right == null){
return rotate(current.left);
}
else if(current.left == null){
return rotate(current.right);
}
else{
TreeNodee<T> pre = current.left;
TreeNodee<T> predecessor;
if (pre.right==null){
predecessor = pre;
predecessor.right = current.right;
}
else{
while(pre.right.right!=null){
pre = pre.right;
}
predecessor = pre.right;
pre.right = predecessor.left;
predecessor.left = current.left;
predecessor.right = current.right;
}
return predecessor;
}
}
else{
if (compare(n,current.data)>0){
current.right = rotate(remove(current.right,n));
}
else{
current.left = rotate(remove(current.left,n));
}
return rotate(current);
}
}
private TreeNodee<T> updateHeightAndBF(TreeNodee<T> n) {
int left,right;
left = n.left!=null ? n.left.height : -1;
right = n.right!=null ? n.right.height : -1;
n.bf = left-right;
n.height = (right>left ? right : left) +1;
return n;
}
private TreeNodee<T> rotate(TreeNodee<T> n) {
if(n == null)return n;
n = updateHeightAndBF(n);
if(n.bf<-1){
if(n.right.bf>0){
n = rightLeft(n);
}
else{
n = left(n);
}
}
else if(n.bf>1){
if(n.left.bf<0){
n = leftRight(n);
}
else{
n = right(n);
}
}
return n;
}
private TreeNodee<T> left(TreeNodee<T> n) {
TreeNodee<T> newRoot = n.right;
TreeNodee<T> temp = n.right.left;
n.right.left = n;
n.right = temp;
n = updateHeightAndBF(n);
return newRoot;
}
private TreeNodee<T> right(TreeNodee<T> n) {
TreeNodee<T> newRoot = n.left;
TreeNodee<T> temp = n.left.right;
n.left.right = n;
n.left = temp;
n = updateHeightAndBF(n);
return newRoot;
}
private TreeNodee<T> leftRight(TreeNodee<T> n) {
n.left = left(n.left);
n = right(n);
return n;
}
private TreeNodee<T> rightLeft(TreeNodee<T> n) {
n.right = right(n.right);
n = left(n);
return n;
}
public boolean isEmpty() {
if (size==0) return true;
return false;
}
private int compare(T d1,T d2){
if (d1==null && d2 == null){
return 0;
}
else if(d1==null){
return 1;
}
else if(d2==null){
return -1;
}
else{
return d1.compareTo(d2);
}
}
}
不需要父链接。你只要顺着树下去,直到找到一片叶子。问题是"哪个叶子包含这个值的后继/前继?"
我将取节点的直接前身,考虑到您在树中找到了该节点。此外,我将考虑左子节点更小,右子节点高于当前节点。
现在,您已经有了节点,您想要找到它的前身。前导意味着你想要最大的节点,它更小。我们只检查一下箱子。
案例1:我没有孩子假设你的树是这个,你想要3的前身。别紧张,这是他的父母。你可以用递归来实现,从树的根开始。你只需要记住在你前进的道路上遇到的最好的前辈。
2
/
1 3
执行如下:
I'm at node 2, looking for the predecessor of 3 -> go right
I'm at node 3, looking for a predecessor of 3 -> go left
There's nothing, I didn't find any predecessor -> recursion rewinds
Crap, there is no predecessor found and 3 is not a predecessor of 3 -> recursion rewinds
Still no predecessor, but 2 is a predecessor of 3 -> recursion rewinds sending 2
Recursion ends: 2 is your value.
现在,如果你想找到它的前身节点没有左子树,并且是它父节点的左子节点,该怎么办? ->在你的递归过程中寻找它的祖父节点,直到你找到一个更小的节点。
如果没有更小的节点怎么办?那么,这个节点实际上是树中最小的节点,并且它没有前身。
案例2:我有孩子希望这是一个困难的例子。现在,我们看的这个节点有一棵左子树。很简单:前任隐藏在左子树的某个地方。更棒的是,它是其中最大的节点(根据定义)。
所以你的前身是左子树中最大的节点,这很容易找到->向右直到你遇到叶节点。
继任者呢?相同的,但是相反。节点的后继节点是其右子树的最左叶节点。同样,边缘情况也是一样的,有可能你正在寻找树中不存在的最大节点的后继节点。
实现提示要实现这种操作,完全放弃在AVL树上工作的事实更容易,只需考虑如何在标准二叉树中执行即可。
当你没有父指针时,你可以迭代:从根开始,总是考虑父、当前、左子和右子在这些操作。实际上,这种方法通常更复杂,因为您需要同时跟踪许多节点。此外,您必须更新在每次迭代中找到的值,因为没有指针就无法向上。
我们倾向于递归地处理二叉树,因为结构本身是递归的。你可以在递归中一直传递parent,但不是强制的(这里它们不是必需的)。您只需要记住,您是刚刚向您返回值的节点的父节点,并相应地执行操作。
这需要一点练习,但一旦你掌握了它,它就很直观了。
在这个实现中我需要编写后继和前继,但是我不知道如何在没有父的情况下实现。
嗯……怎么啦?
public class TreeNodee<K extends Comparable<K>> {
public K data;
int counter;
public TreeNodee<K> left, right;
public int height;
public int bf;
// ------------------------------------
// Why, this parent is not good enough?
// |
// V
TreeNodee parent;