создание двоичного дерева поиска

Question

Как создать BST, когда у меня есть список массивов из 100 элементов, таких как {3,2,6,7,...,99}?

Answer 1

Я считаю, что TreeSet является реализация бинарного дерева поиска. Так как целые числа имеют естественный порядок, вы можете просто перебрать свой массив целых чисел и добавить их все в TreeSet<Integer>.

Обратите внимание, что существует метод Arrays.binarySearch, который выполняет двоичный поиск в отсортированном массиве.

int[] someInts = {3,2,6,7, /*...,*/ 99}; 

// use a TreeSet 
TreeSet<Integer> ints = new TreeSet<Integer>(); 
for (int i : someInts) 
    ints.add(i); 

System.out.println(ints.contains(2)); // true  
System.out.println(ints.contains(5)); // false 

// or sort the array and use Arrays.binarySearch 
Arrays.sort(someInts); 
System.out.println(Arrays.binarySearch(someInts, 2) >= 0); // true 
System.out.println(Arrays.binarySearch(someInts, 5) >= 0); // false 

Answer 2

первого рода этот массив, чем использование BST

EDIT

1- BST работает на отсортированном массиве.

2- Используйте этот psudo код See Here

Answer 3

Если вы не хотите, чтобы реализовать все самостоятельно (в этом случае, вы можете проверить here) вы должны смотреть на [Collections.binarySearch] [2].

[2]: http://download.oracle.com/javase/1.4.2/docs/api/java/util/Collections.html#binarySearch(java.util.List, java.lang.Object)

Answer 4

Посмотрите на http://www.java-tips.org/java-se-tips/java.lang/binary-search-tree-implementation-in-java.html

Answer 5

Я недавно закончил проект, где мы в основном должны были сделать это.

Вы могли бы взглянуть на этот класс

Edit: Это в C++, я вижу, вы кодирования в Java, мои извинения!

/************************************** 
* Tree.cpp - Created by DT 
************************************** 
* 
* Functions: 
* 
* public: 
*  Tree(); 
*  void addNode(int); 
*  bool findID(int); 
*  Node* findNode(int); 
*  Node* findParent(int); 
*  bool deleteID(int); 
*  Node* findMaximum(Node*); 
*  Node* findMinimum(Node*); 
*  void printInOrder(); 
*  void printPreOrder(); 
*  void printPostOrder(); 
*  int recurseHeight(Node*); 
*  int getHeight(); 
*  void inOrder(Node*); 
*  void preOrder(Node*); 
*  void postOrder(Node*); 
* 
***************************************/ 
#include <iostream> 
#include "Node.h" 
#include "Tree.h" 

using namespace std; 

Tree::Tree() { 
    root = NULL; 
} 
/////////////////////////////// 
// AddNode Function: 
/////////////////////////////// 
void Tree::addNode(int id) { 
    if(findNode(id)) { 
     cout << "This ID already exists in the tree" << endl; 
     return; 
    } 
    //if(id == 2147483647) { 
    // cout << "Overflow Detected: Did you enter a really big number?\n"; 
    // cout << "This ID is being stored as 2147483647\n"; 
    //} 
    Node *newNode = new Node(); 
    newNode->id = id; 
    if(root == NULL) { 
     root = newNode; 
     return; 
    } 
    Node *nextNode = root; 
    Node *lastNode = nextNode; 
    while(nextNode != NULL) { 
     if(id <= nextNode->id) { 
      lastNode = nextNode; 
      nextNode = nextNode->leftChild; 
     } 
     else { 
      lastNode = nextNode; 
      nextNode = nextNode->rightChild; 
     } 
    } 
    if(id <= lastNode->id) 
     lastNode->leftChild = newNode; 
    else 
     lastNode->rightChild = newNode; 
} 
/////////////////////////////// 
// FindID Function: 
/////////////////////////////// 
bool Tree::findID(int id) { 
    Node *finder = root; 
    while(finder != NULL) { 
     if(id == finder->id) 
      return true; 
     if(id <= finder->id) 
      finder = finder->leftChild; 
     else 
      finder = finder->rightChild; 
    } 
    return false; 
} 
/////////////////////////////// 
// FindNode Helper Function: 
/////////////////////////////// 
Node* Tree::findNode(int id) { 
    Node *finder = root; 
    while(finder != NULL) { 
     if(id == finder->id) 
      return finder; 
     if(id <= finder->id) 
      finder = finder->leftChild; 
     else 
      finder = finder->rightChild; 
    } 
    return NULL; 
} 
/////////////////////////////// 
// FindParent Helper Function: 
/////////////////////////////// 
Node* Tree::findParent(int id) { 
    Node *parent = NULL; 
    Node *finder = root; 
    while(finder != NULL) { 
     if(id == finder->id) 
      return parent; 
     parent = finder; 
     if(id <= finder->id) 
      finder = finder->leftChild; 
     else 
      finder = finder->rightChild; 
    } 
    return NULL; 
} 
/////////////////////////////// 
// DeleteID Function: 
/////////////////////////////// 
bool Tree::deleteID(int id) { 
    if(root == NULL) 
     return false; 
    Node *toDelete = findNode(id);  //Find the node to delete 
    if(toDelete == NULL)    //If we can't find it, return false 
     return false; 
    Node *parent = findParent(id);  //Find the parent of the node to delete 
    Node *justInCase;     //In case we are deleting the root node 
    bool deletingRoot = false;   //This is a special case so handle it differently 
    if(root->id == id) {    //If we're deleting the root node 
     justInCase = new Node();  //Let's create a fake parent for the root 
     justInCase->leftChild = root; //Just to make sure that we can run checks on parents 
     justInCase->rightChild = NULL; 
     justInCase->id = 0;    //Later on in the code 
     parent = justInCase;   //Set the parent of the root to our new fake node 
     deletingRoot = true;   //Let the end of our function know we're deleting the root 
    } 
    bool deletingLeftChild = (parent->leftChild == toDelete); 
    if(toDelete->leftChild == NULL && toDelete->rightChild == NULL) { 
     if(toDelete == root) 
      root = NULL; 
     if(deletingLeftChild) 
      parent->leftChild = NULL; 
     else 
      parent->rightChild = NULL; 
     delete toDelete; 
     return true; 
    } 
    if((toDelete->leftChild == NULL || toDelete->rightChild == NULL) && (parent != NULL && !deletingRoot)) { 
     if(deletingLeftChild) 
      parent->leftChild = (toDelete->leftChild == NULL) ? toDelete->rightChild : toDelete->leftChild; 
     else 
      parent->rightChild = (toDelete->leftChild == NULL) ? toDelete->rightChild : toDelete->leftChild; 
     delete toDelete; 
     return true; 
    } 
    Node *replacer = findMaximum(toDelete->leftChild);   //Replace the node we're deleting with the hightest LEFT Child 
    if(replacer == NULL || replacer == toDelete)    //If we can't find a left child (in case of deleting root) 
     replacer = findMinimum(toDelete->rightChild);   //Find the smallest RIGHT child 
    Node *replacerParent = findParent(replacer->id);   //Find the parent of this child 
    if(replacerParent != NULL) {        //If this child has a parent 
     if(replacerParent->leftChild == replacer) {    //If the child is to the left of the parent 
      if(replacer->leftChild != NULL)      //And the left child has a child of its own (in case of findMinimum/maximum) 
       replacerParent->leftChild = replacer->leftChild;//set the parent's child to this child's node 
      else 
       replacerParent->leftChild = NULL;    //Otherwise, set the parent's child to NULL 
     } 
     else {             //In the case of Right Child 
      if(replacer->rightChild != NULL)     //Do the same thing 
       replacerParent->rightChild = replacer->rightChild; 
      else 
       replacerParent->rightChild = NULL; 
     } 
    } 
    toDelete->id = replacer->id;        //Swap the IDs of the nodes we're deleting 
    delete replacer;           //And delete the minimum or maximum that we found 
    return true; 
} 
/////////////////////////////// 
// FindMaximum Helper Function: 
/////////////////////////////// 
Node* Tree::findMaximum(Node *theNode) { 
    if(theNode == NULL) 
     return NULL; 
    Node *finder = theNode; 
    Node *last = finder; 
    while(finder != NULL) { 
     last = finder; 
     finder = finder->rightChild; 
    } 
    return last; 
} 
/////////////////////////////// 
// FindMinimum Helper Function: 
/////////////////////////////// 
Node* Tree::findMinimum(Node *theNode) { 
    if(theNode == NULL) 
     return NULL; 
    Node *finder = theNode; 
    Node *last = finder; 
    while(finder != NULL) { 
     last = finder; 
     finder = finder->leftChild; 
    } 
    return last; 
} 
/////////////////////////////// 
// PrintInOrder Function: 
/////////////////////////////// 
void Tree::printInOrder() { 
    inOrder(root);          //Recurse through our root 
    cout << "\b " << endl; 
} 
/////////////////////////////// 
// PrintPostOrder Function: 
/////////////////////////////// 
void Tree::printPostOrder() { 
    postOrder(root);         //Recurse through our root 
    cout << "\b " << endl; 
} 
/////////////////////////////// 
// PrintPreOrder Function: 
/////////////////////////////// 
void Tree::printPreOrder() { 
    preOrder(root);         //Recurse through our root 
    cout << "\b " << endl; 
} 
/////////////////////////////// 
// RecurseHeight Function: 
/////////////////////////////// 
int Tree::recurseHeight(Node *node) { 
    if(node == NULL) return -1; 
    return 1 + max(recurseHeight(node->leftChild),recurseHeight(node->rightChild)); 
} 
/////////////////////////////// 
// GetHeight Function: 
/////////////////////////////// 
int Tree::getHeight() { return recurseHeight(root); } //Recurse through our root 
/////////////////////////////// 
// InOrder Function: 
/////////////////////////////// 
void Tree::inOrder(Node *cNode) { 
    if(cNode == NULL) 
     return; 
    inOrder(cNode->leftChild); 
    cout << cNode->id << "-"; 
    inOrder(cNode->rightChild); 
} 
/////////////////////////////// 
// PostOrder Function: 
/////////////////////////////// 
void Tree::postOrder(Node *cNode) { 
    if(cNode == NULL) 
     return; 
    postOrder(cNode->leftChild); 
    postOrder(cNode->rightChild); 
    cout << cNode->id << "-"; 
} 
/////////////////////////////// 
// PreOrder Function: 
/////////////////////////////// 
void Tree::preOrder(Node *cNode) { 
    if(cNode == NULL) 
     return; 
    cout << cNode->id << "-"; 
    preOrder(cNode->leftChild); 
    preOrder(cNode->rightChild); 
} 

Класс узла:

/************************************** 
* Node.cpp - Created by DT 
************************************** 
* 
* An incredibly simple class that 
* apparently deserves its own header 
* 
***************************************/ 
#include "Node.h" 
#include <iostream> 
Node::Node() { 
    leftChild = NULL; 
    rightChild = NULL; 
    id = NULL; 
}