Ausgewogener binärer Suchbaum
Ich muss einen ausgeglichenen binären Suchbaum erstellen. Bisher fügt mein Programm die Zahlen von 1 bis 26 ein, aber mein Programm baut sie nicht in einen ausgeglichenen binären Suchbaum ein. Wenn jemand meinen Code anschauen und mir helfen könnte, wäre er sehr dankbar.
public class TreeNode {
TreeNode leftTreeNode, rightTreeNode;// the nodes
int data;
//int size;
public TreeNode(){//Constructer
leftTreeNode = null;
rightTreeNode = null;
}
public TreeNode(int newData){//Constructer with new Data coming in for comparison
leftTreeNode = null;
rightTreeNode = null;
data = newData;
}
public TreeNode getLeft(){
return leftTreeNode;
}
public TreeNode getRight(){
return rightTreeNode;
}
public void setLeft(TreeNode leftTreeNode){
this.leftTreeNode = leftTreeNode;
}
public void setRight(TreeNode rightTreeNode){
this.rightTreeNode = rightTreeNode;
}
public int getData(){
return data;
}
// public boolean isEmpty(){//Checking to see if the the root is empty
// if(size == 0) return true;
// else return false;
public void print(){
System.out.println("Data is: " + getData());
}
}
// public void traverse (Node root){ // Each child of a tree is a root of its subtree.
// if (root.getLeft() != null){
// traverse (root.getLeft());
// }
// System.out.println(root.data);
// if (root.getRight() != null){
// traverse (root.getRight());
// }
//}
public class BinarySearchTree {
TreeNode root;
public BinarySearchTree(){
root = null;
}
public TreeNode getRoot(){
return root;
}
public void insert(int data) { //Insert method checking to see where to put the nodes
TreeNode node1 = new TreeNode(data);
if (root == null) {
root = node1;
}
else{
TreeNode parIns = root;//Parent
TreeNode insNode = root;//Insertion Node
while(insNode != null){
parIns = insNode;
if(data < insNode.getData()){//If the data is less than the data coming in place it on the left
insNode = insNode.getLeft();
}else{//Place it on the right
insNode = insNode.getRight();
}
}//Searching where to put the node
if(data < parIns.getData()){
parIns.setLeft(node1);
}else{
parIns.setRight(node1);
}
}
}
public void printInorder(TreeNode n){
if(n != null){
printInorder(n.getLeft());//L
n.print();//N
printInorder(n.getRight());//R
}
}
// public TreeNode balance(tree, int start, int end){
// if(start > end) return null;
// int mid = (start + end) /2;
// TreeNode node;
// TreeNode leftChild;
// TreeNode rightChild;
//
// if(node <= mid){
// leftChild = balance(arr[mid -1], start, end);/*Make the left child if the node coming in is
// less than the mid node */
//
//
// }else{
// rightChild = balance(arr[mid]+1, start, end);/*Make the rigth child if the node is
// greater than the mid node*/
//
// }
// return node;
// }
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
tree.insert(1);
tree.insert(2);
tree.insert(3);
tree.insert(4);
tree.insert(5);
tree.insert(6);
tree.insert(7);
tree.insert(8);
tree.insert(9);
tree.insert(10);
tree.insert(11);
tree.insert(12);
tree.insert(13);
tree.insert(14);
tree.insert(15);
tree.insert(16);
tree.insert(17);
tree.insert(18);
tree.insert(19);
tree.insert(20);
tree.insert(21);
tree.insert(22);
tree.insert(23);
tree.insert(24);
tree.insert(25);
tree.insert(26);
tree.printInorder(tree.getRoot());
}
}
//for(int i = 1; i <= 26; i++)
//tree.insert(i);
public void balance(TreeNode tree, int start, int end){
TreeNode tree1 = new TreeNode(data);
if(start <= end){
int mid = (start + end) /2;
//TreeNode node;
TreeNode leftChild;
TreeNode rightChild;
if(tree1.getData() <= mid){
leftChild = balance(tree1(mid -1), start, end);/*Make the left child if the node coming in is
less than the mid node */
}else{
rightChild = balance(tree1(mid+1), start, end);/*Make the rigth child if the node is
greater than the mid node*/
}
}
}
Wie kann ich die Balance-Funktion reparieren, um meinen Baum richtig zu balancieren?