1

我正在尝试做一个 avl 树，它每次树不平衡时都会自我更新。旋转正在工作，但我有一个错误，例如，如果树节点 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            \n\n\n\n");
            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  \n\n\n\n\n\n\n");
            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 Number\t\tLeft\t\tNode\t\tRight\t\tLeft Height\t\tRight Height\n");
                for (int i=0; i<array.size();i++)
                {                     
                      System.out.print (i+"\t\t\t"+array.indexOf(array.get(i).getLeftChild())+"\t\t"+array.get(i).getValue()+"\t\t"+array.indexOf(array.get(i).getRightChild())+"\t\t"+array.get(i).getLeftHeight()+"\t\t\t"+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();
    }
}
4

2 回答 2

0

  1. 该代码需要更复杂一些。我希望在这里给你一个更简单的版本，你自己可以正确平衡。也许你应该更好地在插入内进行指针旋转/重新平衡。不要觉得有义务给分；这只是一半的答案。

  2. 仅备注：该字段value可能是ìnt.

  3. 如果“ 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);
    }
}
}
    1. 正如您在插入期间立即看到的平衡，可以在<和>（3 个指针：左边最右边的叶子或右边的最左边的叶子）处进行指针旋转插入。从递归中返回，可以收集左侧最右侧叶子的父节点，并执行旋转。或在任何其他点。存在 3 种变体！
于 2011-12-26T15:55:23.107 回答
0

可能是因为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 树不会递归整个树来找到节点的平衡。

于 2011-12-26T14:49:35.560 回答