java - 平衡二叉搜索树

Question

我需要构建一个平衡二叉搜索树。到目前为止，我的程序插入了从 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*/

      }

      }
}

如何修复平衡函数以正确平衡我的树？

Answer 1

由于您的树不能自平衡，因此它是否平衡将取决于元素的插入顺序。

如果您希望您的树无论如何都保持平衡，您将需要注意类(class)中的平衡。例如，看一下 Red-Black Tree数据结构。