制作二叉搜索树

当我有一个包含{3,2,6,7,...,99}等100个元素的数组列表时，如何制作BST？

Answer 1

我相信TreeSet是二叉搜索树的实现。 由于整数具有自然排序，因此您可以简单地遍历整数数组并将它们全部添加到TreeSet 。

另请注意，有一个方法Arrays.binarySearch在排序数组中进行二进制搜索。

 int[] someInts = {3,2,6,7, /*...,*/ 99}; // use a TreeSet TreeSet ints = new TreeSet(); 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

除非你想自己实现一切（在这种情况下，你可能想在这里查看 ），你应该看一下[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 3

第一个排序这个数组，而不是使用BST

编辑

1- BST适用于已排序的数组。

2-使用此psudo代码请参阅此处

Answer 4

请查看http://www.java-tips.org/java-se-tips/java.lang/binary-search-tree-implementation-in-java.html

Answer 5

我最近完成了一个项目，我们基本上必须这样做。

你可以看一下这堂课

编辑：这是用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  #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  Node::Node() { leftChild = NULL; rightChild = NULL; id = NULL; }