平衡二进制搜索树

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

如何修复平衡function以正确平衡树木？

Answer 1

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

如果你想让你的树平衡，你需要在课堂上保持平衡。 例如，看一下Red-Black Tree数据结构。

Answer 2

 public class BinarySearchTree { TreeNode root; public BinarySearchTree(){ root = new TreeNode(); } public TreeNode getRoot(){ return root; } public void insert(int data) { root = insert(root, data); }//Insert method checking to see where to put the nodes // public void insert(TreeNode node, int data){ // 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); // } // // } // } private TreeNode insert(TreeNode node, int data) { if(root.data == 0) root.data = data; else if (node==null) { node = new TreeNode(data); } else { if (data <= node.data) { node.leftTreeNode = insert(node.leftTreeNode, data); } else { node.rightTreeNode = insert(node.rightTreeNode, data); } } return(node); // in any case, return the new pointer to the caller } public void printPreOrder(){ printPreOrder(root); } public void printPreOrder(TreeNode n){ if(n != null){ n.print();//N printPreOrder(n.getLeft());//L printPreOrder(n.getRight());//R } } public TreeNode balance(int[] a, int start, int end){ TreeNode node = new TreeNode(); if(start <= end){ int mid = start + (end - start) /2; node.data = a[mid]; if(root.data == 0) root = node; node.leftTreeNode = balance(a, start, mid -1);/*Make the left child if the node coming in is less than the mid node */ node.rightTreeNode = balance(a, mid + 1, end);/*Make the rigth child if the node is greater than the mid node*/ } else{ return null; } return node; } public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); //int[] a = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,21,22,23,24,25,26}; int[] a = new int[26]; for(int i = 0; i < 26; i++){ a[i] = i + 1; } for(int i = 1; i <= 26; i++) tree.insert(i); tree.printPreOrder(); BinarySearchTree tree2 = new BinarySearchTree(); tree2.balance(a, 0, 25); System.out.println("Now I am going to balance my tree"); tree2.printPreOrder(); } } public class TreeNode { TreeNode leftTreeNode, rightTreeNode;// the nodes int data; //int size; public TreeNode(){//Constructer leftTreeNode = null; rightTreeNode = null; data = 0; } 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()); } }