java 平衡二叉搜索树
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16138809/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
提示：将鼠标放在中文语句上可以显示对应的英文。显示中英文
时间：2020-10-31 22:01:36 来源:igfitidea点击:
Balanced Binary Search Tree
提问by user2303070
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.
我需要建立一个平衡的二叉搜索树。到目前为止，我的程序插入了从 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*/
}
}
}
How can I fix the balance function to properly balance my tree?
如何修复平衡功能以正确平衡我的树？
回答by Catherine
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 Treedata structure.
如果您无论如何都希望树保持平衡，则需要注意班级中的平衡。例如，看看红黑树数据结构。
回答by user2303070
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());
}
}
