平衡二进制搜索树 [英] Balanced Binary Search Tree

问题描述

我需要构建一个平衡的二叉搜索树。到目前为止，我的程序插入从1到26的数字，但我的程序不会将其构建为平衡的二叉搜索树。如果有人能看到我的代码并帮助我，我将不胜感激。

I need to build a balanced binary search tree. So far my program inserts the numbers from 1 to 26, but my program does not build it into a balanced binary search tree. If anyone could look at my code and help me out it would be much appreciated.

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*/

      }

      }
}

如何修复余额功能以正确平衡我的树？

How can I fix the balance function to properly balance my tree?

推荐答案

由于你的树不能自我平衡，它的平衡是否取决于元素的插入顺序。

Since your tree does not self-balance, whether or not it's balanced will depend on the order of insertion of the elements.

如果你想让你的树平衡，你需要在课堂上保持平衡。例如，请查看红黑树数据结构。

If you want your tree to be balanced regardless, you will need to take care of the balancing in your class. For example, take a look at the Red-Black Tree data structure.

这篇关于平衡二进制搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！