我需要建立一个平衡的二叉搜索树。 到目前为止,我的程序插入数字1到26,但我的程序不其打造成为一个平衡二叉搜索树。 如果任何人都可以看看我的代码,并帮助我走出这将是大加赞赏。
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*/
}
}
}
我怎样才能解决这个平衡功能适当的平衡我的树?