avl tree rotation

我正在尝试做一个avl树，每次树不平衡时更新自己。旋转正在工作，但我有一个bug，如果例如树节点7,leftChild 6, leftChild 5的leftChild变成节点6,leftChild 5, rightchild 7，平衡后我添加了一个新节点，该节点首先与7而不是6进行比较。如何解决这个问题?

这是主类:

import java.io.*;
import javax.swing.*;
import java.util.*;
import java.lang.*;
public class NewMain  implements Cloneable{
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args)
    {
        File file = new File ("AVLTree.txt");
        ArrayList <TreeNode> array = new ArrayList ();
        Scanner kb = new Scanner (System.in);
        int num = 0;
        TreeNode root = new TreeNode ();
        do {
            System.out.print("              AVL Tree            nnnn");
            System.out.println("1. Create a new binary tree");
            System.out.println("2. Save Tree");
            System.out.println("3. Load Tree");
            System.out.println("4. Enter a new node in the tree");
            System.out.println("5. Show current AVL tree");
            System.out.println("6. Show inorder traversal");
            System.out.println("7. Search");
            System.out.println("8. Quit  nnnnnnn");
            System.out.print("Enter a number: ");
            num = kb.nextInt ();
            if (num == 1){
                if (array.isEmpty ())
                {
                    System.out.print ("Enter the root value: ");
                    int value = kb.nextInt ();
                    root = new TreeNode();
                    root.setValue(value);
                    array.add(root);
                }
                else
                {
                    array.clear();
                    System.out.print ("Enter the root value: ");
                    int value = kb.nextInt ();
                    root = new TreeNode();
                    root.setValue(value);
                    array.add(root);
                }
            }
            if (num == 2) 
            {
                    FileOutputStream outFile = null;
                    ObjectOutputStream oos = null;
                    try 
                    {
                        outFile = new FileOutputStream(file);             
                        oos = new ObjectOutputStream(outFile);
                        for (TreeNode list : array) 
                        {                 
                            oos.writeObject(list);                                      
                        }
                        oos.close();
                    }
                    catch (Exception e) 
                    {
                        System.out.print("Save Not Successful!");
                    }
               }
            if (num == 3) 
            {
                if (file.exists()) 
                {
                    FileInputStream inFile = null;
                    ObjectInputStream ios = null;
                    try 
                    {
                        Object obj = null;
                        inFile = new FileInputStream(file); 
                        ios = new ObjectInputStream(inFile); 
                        while ((obj = ios.readObject()) != null) {              
                            if (obj instanceof TreeNode) 
                            { 
                                array.add((TreeNode) obj);
                            }
                        }
                        ios.close(); 
                    } 
                    catch(EOFException e)
                    {   
                    }
                    catch (Exception e) 
                    {
                        System.out.print("File was not found while loading");
                    }
                }
            }
            if (num == 4)
            {
                System.out.print ("Enter a new child node: ");
                int value = kb.nextInt ();              
                try 
                {
                    array.add(root.insert(value));  
                    root.balance();
                }
                catch (Exception e)
                {
                    System.out.print (e.getMessage());
                }
            }
            if (num == 5){
                System.out.print ("Pointer NumberttLeftttNodettRightttLeft HeightttRight Heightn");
                for (int i=0; i<array.size();i++)
                {                     
                      System.out.print (i+"ttt"+array.indexOf(array.get(i).getLeftChild())+"tt"+array.get(i).getValue()+"tt"+array.indexOf(array.get(i).getRightChild())+"tt"+array.get(i).getLeftHeight()+"ttt"+array.get(i).getRightHeight()+"n");
                }
            }
            if (num == 6)
            {
                System.out.print("Inorder traversal: ");
                System.out.println(root.InOrderTraversal());
                System.out.print("Postorder traversal: ");
                System.out.println(root.PostOrderTraversal());
                System.out.print("Preorder traversal: ");
                System.out.println(root.PreOrderTraversal());
            }
            if (num == 7)
            {
                System.out.print("Enter node to be searched: ");
                int node = kb.nextInt ();
                for (int i = 0; i<array.size();i++)
                {
                    if (node == array.get(i).getValue())
                    {
                        System.out.print ("Node is in index "+i+"n");
                        break;
                    }
                    if (i == array.size()-1 && node != array.get(i).getValue())
                    {
                        System.out.print ("Node not found in the tree!"+"n");
                        break;
                    }
                }
            }            
        }while (num != 8);
    }
}

这是一个普通的java类:

import java.lang.StringBuilder;
import java.util.ArrayList;
import java.io.*;
import java.util.logging.Level;
import java.util.logging.Logger;
import javax.swing.*;
public class TreeNode implements Serializable, Cloneable
{
    public Integer value;
    public TreeNode leftChild;
    public TreeNode rightChild;
    public TreeNode()
    {
        this.value = null;
        this.leftChild = null;
        this.rightChild = null;
    }
    public TreeNode(int value)
    {
        this.value = value;
        this.leftChild = null;
        this.rightChild = null;
    }
    public int getValue()
    {
        return this.value;
    }
    public void setValue(int value)
    {
        this.value = value;
    }
    public TreeNode getLeftChild()
    {
        return this.leftChild;
    }
    public void setLeftChild(TreeNode leftChild)
    {
        this.leftChild = leftChild;
    }
    public TreeNode getRightChild()
    {
        return this.rightChild;
    }
    public void setRightChild(TreeNode rightChild)
    {
        this.rightChild = rightChild;        
    }
    public int getLeftHeight()
    {
        if (this.leftChild == null)
        {
            return 0;
        }
        else
        {    
            return this.getLeftChild().getHeight() + 1;
        }
    }
    public int getRightHeight()
    {
        if (this.rightChild == null)
        {
            return 0;
        }
        else
        {
            return this.getRightChild().getHeight() + 1;
        }
    }
    public TreeNode insert(int value) throws Exception
    {
      if(this.value == null && this.leftChild == null && this.rightChild == null)
      {
            this.value = value;
            return this;
      }
        else
        {
            TreeNode node = new TreeNode (value);
            if(value < this.value)
            {
                if(this.getLeftChild() == null)
                {
                    this.setLeftChild (node);
                    return node;
                }
                else
                {
                    return this.getLeftChild().insert(value);
                }
            }
            else if(value > this.value)
            {
                if(this.getRightChild() == null)
                {
                    this.setRightChild(node);
                    return node;
                }
                else
                {
                    return this.getRightChild().insert(value);
                }
            }
            else 
            {
                return null;
            }
        } 
    }
    public TreeNode balance() throws Exception
    {
        if (Math.abs(this.getLeftHeight() - this.getRightHeight())==2)
        {
            if (this.rightChild == null)
            {
                if(this.leftChild.leftChild != null)
                { 
                    return this.LLRotation ();
                }
                if(this.leftChild.rightChild != null)
                { 
                    return this.LRRotation ();
                }
            }
            if (this.leftChild == null)
            {
                if (this.rightChild.rightChild != null)
                {
                    return this.RRRotation ();
                }
                if (this.rightChild.leftChild != null)
                {
                    return this.RLRotation ();
                }
            }
        }
        else
        {
            if (this.getLeftChild () != null)
            {
                return this.getLeftChild().balance();
            }
            if (this.getRightChild () != null)
            {
                return this.getRightChild().balance();
            }
        }
        return this;
    }
    public int getHeight ()
    {
        if (this.leftChild == null && this.rightChild == null)
        {
            return 0;
        }
        else
        {
            int leftH = 0;
            int rightH = 0;
            if (this.leftChild != null)
            {
                leftH++;
                leftH += this.getLeftChild().getHeight();
            }
            if (this.rightChild != null)
            {
                rightH++;
                rightH += this.getRightChild().getHeight();
            }
            return Math.max(leftH,rightH);
        }
    }
    public TreeNode LLRotation ()
    {
        TreeNode temp = this.leftChild;
        this.leftChild = null;
        temp.rightChild = this;
        return temp;
    }
    public TreeNode RRRotation ()
    {  
        TreeNode temp = this.rightChild;
        this.rightChild = temp.leftChild;
        try 
        {
            temp.leftChild = (TreeNode)this.clone();
        } 
        catch (CloneNotSupportedException ex) 
        {
        }
        this.value = temp.value;
        this.rightChild = temp.rightChild;
        this.leftChild = temp.leftChild;
        return temp;
    }
    public TreeNode LRRotation ()
    {
        this.leftChild = this.leftChild.RRRotation();
        return LLRotation();
    }
    public TreeNode RLRotation ()
    {
        this.rightChild = this.rightChild.RRRotation();
        return RRRotation();
    }
    public String InOrderTraversal ()
    {
        StringBuilder sb = new StringBuilder ();
        if (this.leftChild == null && this.rightChild == null)
        {
            sb.append(this.value).append(" ");
        }
        else
        {
            if(this.leftChild != null)
            {
                sb.append(this.getLeftChild().InOrderTraversal());
            }
            sb.append(this.value).append(" ");
            if (this.rightChild != null)
            {
                sb.append(this.getRightChild().InOrderTraversal());
            }
        }
        return sb.toString();
    }
    public String PostOrderTraversal ()
    {
        StringBuilder sb = new StringBuilder ();
        if (this.leftChild == null && this.rightChild == null)
        {
            sb.append(this.value).append(" ");
        }
        else
        {
            if(this.leftChild != null)
            {
                sb.append(this.getLeftChild().PostOrderTraversal());
            }
            if (this.rightChild != null)
            {
                sb.append(this.getRightChild().PostOrderTraversal());
            }
            sb.append(this.value).append(" ");
        }
        return sb.toString();
    }
    public String PreOrderTraversal ()
    {
        StringBuilder sb = new StringBuilder ();
        if (this.leftChild == null && this.rightChild == null)
        {
            sb.append(this.value).append(" ");
        }
        else
        {
            sb.append(this.value).append(" ");
            if(this.leftChild != null)
            {
                sb.append(this.getLeftChild().PreOrderTraversal());
            }
            if (this.rightChild != null)
            {
                sb.append(this.getRightChild().PreOrderTraversal());
            }
        }
        return sb.toString();
    }
}

代码需要更复杂一点。我希望在这里给你一个简单的版本，它与你自己可以正确地平衡。也许你应该更好地在插入中做指针旋转/再平衡。不要觉得有义务给分;
仅注:字段value可能是ìnt

对于递归算法来说，如果"this"对象可能为空，则肯定更容易。这可以通过将整个树包装在一个公共类中来实现，该公共类在内部使用TreeNode类。

public class Tree {
private static class TreeNode {
    private int value;
    private TreeNode left;
    private TreeNode right;
    private TreeNode(int value, TreeNode left, TreeNode right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}
private static class AlreadyExistsException extends Exception {
    private TreeNode node;
    private AlreadyExistsException(TreeNode node) {
        this.node = node;
    }
    public TreeNode getNode() {
        return node;
    }
}
private TreeNode root;
private int size;
public boolean insert(int value) {
    try {
        root = insertInto(root, value);
        ++size;
        return true;
    } catch (AlreadyExistsException e) {
        // Fine.
        return false;
    }
}
private TreeNode insertInto(TreeNode node, int value) throws AlreadyExistsException {
    if (node == null) {
        return new TreeNode(value, null, null);
    }
    if (value < node.value) {
        node.left = insertInto(node.left, value);
        return node;
    } else if (value > node.value) {
        node.right = insertInto(node.right, value);
        return node;
    } else {
        throw new AlreadyExistsException(node);
    }
}
}

正如您在插入期间立即看到的平衡，可以使用指针旋转<和>(3个指针:左侧最右叶或右侧最左叶)进行插入。从递归中返回，可以收集最左边叶子的父节点，并执行旋转。或者在任何其他点。有3个变体!

可能是因为root仍然指向旧节点。确定要忽略balance()在标记行处的返回值吗?

if (num == 4) {
    System.out.print ("Enter a new child node: ");
    int value = kb.nextInt ();              
    try {
        array.add(root.insert(value));  
        root.balance();  // look here
    } catch (Exception e) {
        System.out.print (e.getMessage());
    }
}

顺便说一句，文献中描述的AVL树不会递归整个树来找到节点的平衡。

相关内容

最新更新

热门标签：