{3,2,6,7,...,99}
과 같은 100 개 요소의 배열 목록이있을 때 어떻게 BST를 만들 수 있습니까?이진 탐색 트리 만들기
답변
은 이진 검색 트리의 구현입니다. 정수는 자연 순서가 있기 때문에 정수 배열을 반복하여 모두 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
내가 모르는 내가 여기에 의사 코드를 넣어 주시겠습니까 감사 – user472221
당신이 모든 자신을 구현하고자하지 않는 한 당신이 [Collections.binarySearch]에서 살펴 보셔야합니다 (이 경우, 당신은 here을 확인 할 수 있습니다) [2].
[2] : http://download.oracle.com/javase/1.4.2/docs/api/java/util/Collections.html#binarySearch(java.util.List, java.lang.Object 상위)
내가 최근에 우리가 기본적으로이 작업을 수행했던 프로젝트를 완료 http://www.java-tips.org/java-se-tips/java.lang/binary-search-tree-implementation-in-java.html
를 살펴 보자.
이 클래스에서
편집을 살펴 수 :이 C++에, 나는 당신이 자바에 내 사과를 코딩하고보세요!
/**************************************
* 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;
}
- 1. 이진 트리 탐색 추상화
- 2. 스키마의 첫 번째 이진 트리 탐색
- 3. 이진 트리 높이
- 4. 사전 주문 bitstring에서 이진 트리 만들기
- 5. 도움이 진실이 주어진 이진 트리 만들기
- 6. 정수 스트림에서 균형 이진 검색 트리 만들기
- 7. 이진 트리
- 8. 이진 트리
- 9. 이진 탐색 트리의 분석
- 10. 이진 트리 오른쪽 스레딩
- 11. 이진 검색 트리
- 12. 왼쪽 균형 이진 트리
- 13. 균형 이진 트리
- 14. 스레드 이진 트리 문제
- 15. 이진 트리 탐색의 복잡도
- 16. 이진 트리 스와핑 방법
- 17. 자바 이진 검색 트리
- 18. Prolog의 이진 트리
- 19. 이진 트리 로테이션
- 20. balanced() 이진 트리
- 21. preorder bitstring의 이진 트리
- 22. 네트워크 마케팅 이진 트리
- 23. 특수 이진 트리
- 24. Java의 이진 검색 트리
- 25. 잘못된 이진 트리
- 26. ruby의 이진 검색 트리
- 27. 비 - 이진 트리
- 28. 이진 검색 트리 문제
- 29. 불균형 이진 트리
- 30. 기울이기 이진 트리
을 그렇지 않은이 자연 순서가있는 경우 웹 페이지를 열 수없는 이유, 나는 그들이 {95,54,23,87,13,14,12}와 비슷한 것을 의미하므로이 코드도 사용할 수 있습니까? – user472221
또한 위의 배열로 이진 검색 트리를 만드는 방법을 얻을 수 없습니다 !!! – user472221
예. 'TreeSet'는 원소를 순서없이 삽입하면 문제가되지 않습니다. – aioobe