0
트리가 불균형 할 때마다 자체 업데이트하는 avl 트리를 수행하려고합니다. 회전은 작동하지만 버그가 있습니다. 예를 들어 트리 노드 7, leftChild 6, leftchild 5의 왼손잡이가 노드 6, leftchild 5, rightchild 7, 그리고 새 노드를 추가 한 후에 노드가 먼저 비교됩니다. 7이 아니라 6이 아닙니다. 어떻게이 문제를 해결합니까?자체 균형 조정 avl 트리
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);
}
}
이 정상 자바 클래스이다 :
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();
}
}
여기에 학부 과정을 게시 하시겠습니까? :) – daghan