binary-search-tree 相关问题

二叉搜索树是由具有左子节点和右子节点的根节点组成的数据结构。左节点及其所有后代的值小于根节点，而右节点及其所有后代的值大于根节点。根节点的子节点遵循相同的模式。这给了我们一个由有序元素组成的树。

所以对于这个类，我必须写出函数，包括递归查找函数，插入函数和operator[]函数，这总体上有助于插入BST #包括所以对于这个类，我必须写出函数，包括递归查找函数，插入函数和operator[]函数，这总体上有助于插入BST #include <compare> #include <cstddef> #include <format> #include <iostream> #include <string> #include <utility> template<typename Key, typename Value> struct BST { using KeyValue_Pair = std::pair<Key const, Value>; struct Node { Node() = default; Node( KeyValue_Pair const & pair ) : _pair{ pair } {} KeyValue_Pair _pair = { Key{}, Value{} }; Node * _left = nullptr; Node * _right = nullptr; Node * _parent = nullptr; }; Node * _root = nullptr; std::size_t _size = 0; Node * find( Key const & key ) { return find(key, _root); // Delegate the call to the private helper function } Node* find(Key const& key, Node* current) { // Base Case: Node not found if (current == nullptr) { return nullptr; } // Visit: Node found if (key == current->_pair.first) { return current; } // Recurse: Search left or right subtree if (key < current->_pair.first) { return find(key, current->_left); } else { return find(key, current->_right); } } Node * insert( KeyValue_Pair const & pair ) { Node * newNode = new Node( pair ); if(_root == nullptr){ _root = newNode; ++_size; return newNode; } Node * current = _root; Node * parent = nullptr; while(current != nullptr){ parent = current; auto comp = std::compare_weak_order_fallback( pair.first, current->_pair.first ); if( comp == 0 ) return current; else if(comp < 0 ) current = current->_left; current = current->_right; } auto comp = std::compare_weak_order_fallback( pair.first, current->_pair.first ); if( comp < 0 ) parent->_left = newNode; else parent->_right = newNode; newNode->_parent = parent; ++_size; return newNode; } Value & operator[]( Key const & key ) { return insert( { key, Value{} } )->_pair.second; } //everything under this comment already came with the code void print() { auto count = 0uz; print( _root, count ); } void print( Node * current, std::size_t & count ) // in-order traversal { // Base case if( current == nullptr ) return; // Recurse left print( current->_left, count ); // Visit auto && [key, value] = current->_pair; std::cout << std::format( "{:3}: {{{}, {}}}\n", ++count, key, value ); // Recurse right print( current->_right, count ); } ~BST() noexcept { clear(); } }; int main() { BST<unsigned int, std::string> myTree; std::cout << "Test Case 1:\n"; // 50 // myTree[50] = "indeed"; // / \ // myTree.insert( { 40, "Structures" } ); // 40 60 // myTree.insert( { 60, "very" } ); // / \ / \ // myTree.insert( { 30, "Lego" } ); // 30 45 55 70 // myTree.insert( { 45, "are" } ); myTree[55] = "truly"; myTree[70] = "entertaining"; myTree.print(); std::cout << "------------------------------\n"; } 但是，我收到测试用例 1 的分段错误（核心转储）错误消息。我不确定错误是否出现在递归查找或插入函数中。我非常感谢一些反馈，请并谢谢。如果代码太长，我也表示歉意，我想包含 main 中的测试用例 1，但我不确定是否应该包含 void print 函数。您的 while 循环要么在找到匹配项时退出，要么在超出底部时退出——此时 current 为空。下一条语句取消引用 current。你可能指的是父母。这是您期望的输出吗： 1: {30, Lego} 2: {40, Structures} 3: {45, are} 4: {50, indeed} 5: {55, truly} 6: {60, very} 7: {70, entertaining} 这就是我进行两项更改时得到的结果： cout << "while....\n"; while(current != nullptr){ parent = current; auto comp = std::compare_weak_order_fallback( pair.first, current->_pair.first ); if( comp == 0 ) return current; else if(comp < 0 ) current = current->_left; else current = current->_right; } cout << "while done\n"; auto comp = std::compare_weak_order_fallback( pair.first, parent->_pair.first ); 请参阅 while 循环末尾的 else 子句（您刚刚设置了它）以及对 Parent 而不是 current 的取消引用。

c++ binary-search-tree

回答 1 投票 0

返回二叉树中节点的父节点

我正在编写一个代码来返回任何节点的父节点，但我遇到了困难。我不想使用任何预定义的 ADT。 //假设节点由 1...n 中的数字表示，其中 1=root 甚至 ...

java algorithm tree binary-search-tree

回答 2 投票 0

二元运算符 ">" 的操作数类型错误？

我正在编写一个BST程序。我收到错误： “二元运算符 "> 的错误操作数类型第一种类型：java.lang.Object 第二种类型：java.lang.Object” 这就是它给我呃...

java tree binary-search-tree

回答 7 投票 0

高效合并两个二叉搜索树并创建一个 BST

假设我必须通过合并两个 BST 来创建一个 BST，其中 T1 和 T2 都是 BST，这样 T1 的节点比 T2 更多，并且使用此算法，对于 T2 中的每个节点，从 T2 中删除节点并插入...