我正在尝试在bst.template文件中实现插入函数。我还没有实现任何重要的东西，因为我不知道该怎么做。insert函数应该是，只要项目还不存在，就将其添加到这个二进制搜索树中，如果项目已经在树中，则返回false，如果项目确实添加到树中，那么返回true。以下是我到目前为止得到的。
#include "bst.h"
#include <string>
#include <iostream>
/**
* Add the item to this binary search tree as long as it
* is not already present.
* Return false if item is already in the tree.
* Return true if item is actually added to the tree.
*/
template <class T>
bool binary_search_tree<T>::insert(const T &item) {
if(item )
}
/*
* the target value removed -> return true
* if not -> return false
*/
template <class Item>
bool bst_remove(binary_tree_node<Item>*& root_ptr, const Item& target) {
binary_tree_node<Item> *oldroot_ptr;
if (root_ptr == NULL)
{
return false;
}
if (target < root_ptr->data( ))
{
return bst_remove(root_ptr->left( ), target);
}
if (target > root_ptr->data( ))
{
return bst_remove(root_ptr->right( ), target);
}
if (root_ptr->left( ) == NULL)
{
oldroot_ptr = root_ptr;
root_ptr = root_ptr->right( );
delete oldroot_ptr;
return true;
}
bst_remove_max(root_ptr->left( ), root_ptr->data( ));
return true;
}
template <class Item>
void bst_remove_max(binary_tree_node<Item>*& root_ptr, Item& removed) {
binary_tree_node<Item> *oldroot_ptr;
assert(root_ptr != NULL);
if (root_ptr->right( ) != NULL)
bst_remove_max(root_ptr->right( ), removed);
else
{
removed = root_ptr->data( );
oldroot_ptr = root_ptr;
root_ptr = root_ptr->left( );
delete oldroot_ptr;
}
}
template <class T>
bool binary_search_tree<T>::remove(const T &item) {
return bst_remove(root, item);
}
template <class T>
binary_tree_node<T> *binary_search_tree<T>::search(const T &key) const {
binary_tree_node<T> *p = root;
while(p != NULL && p->data() != key) {
if(key < p->data())
p = p->left();
else
p = p->right();
}
}
template <class T>
binary_search_tree<T>::~binary_search_tree() {
tree_clear(root);
}
/**
* return the depth of the tree if the tree is balanced.
* Return -2 if not. Return -1 if it is an empty tree.
*/
template <class T>
int check_balanced(binary_tree_node<T> *root) {
if(root == NULL)
return -1;
else {
int ibl = check_balanced(root->left());
if(ibl == -2)
return -2;
int ibr = check_balanced(root->right());
if(ibr == -2)
return -2;
if(abs(ibr-ibl) > 1)
return -2;
if(ibr > ibl)
return ibr+1;
else
return ibl+1;
}
}
/**
* return the depth of the tree if the tree is balanced.
* Return -2 if not.
*/
template <class T>
int binary_search_tree<T>::is_balanced() {
return check_balanced(root);
}
template <class T>
std::ostream &operator<<(std::ostream &out, const binary_tree_node<T> *root) {
if(root != NULL) {
out << "[";
out << root->left() << " ";
out << root->data();
out << " " << root->right();
out << "]";
}
return out;
}
template <class T>
std::ostream &operator<<(std::ostream &out, const binary_search_tree<T> &tree) {
out << tree.root;
return out;
}
这是头文件
#ifndef BST_H
#define BST_H
#include "bintree.h"
#include <iostream>
template <class T>
class binary_search_tree {
public:
binary_search_tree() {
root = NULL;
}
/**
* Search for the key in this binary search tree.
* Return a node containing the key, if found.
* Return null if not found.
*/
binary_tree_node<T>* search(const T& key) const;
/**
* Add the item to this binary search tree as long as it
* is not already present.
* Return false if item is already in the tree.
* Return true if item is actually added to the tree.
*/
bool insert(const T& item);
/**
* Remove the item from the tree.
* Return true if the item was actually removed.
* Return false if the item was not in the tree to begin with.
*/
bool remove(const T& item);
~binary_search_tree();
/**
* return the depth of the tree if the tree is balanced.
* Return -2 if not.
*/
int is_balanced();
template <class S>
friend std::ostream& operator<<(std::ostream& out, const binary_search_tree<S>& tree);
binary_tree_node<T>* get_root() { return root; }
private:
binary_tree_node<T>* root;
};
template <class T>
std::ostream& operator<<(std::ostream& out, const binary_tree_node<T>* root);
/**
* return the depth of the tree rooted at root if the tree is balanced.
* Return -2 if not.
*/
template <class T>
int check_balanced(binary_tree_node<T>* root);
template <class Item>
bool bst_remove(
binary_tree_node<Item>*& root_ptr,
const Item& target
);
// Precondition: root_ptr is a root pointer of a binary search tree (or may
// be NULL for the empty tree).
// Postcondition: If target was in the tree, then one copy of target has been
// removed, root_ptr now points to the root of the new (smaller) binary
// search tree, and the function returns true. Otherwise, if target was not
// in the tree, then the tree is unchanged, and the function returns false.
template <class Item>
void bst_remove_max(
binary_tree_node<Item>*& root_ptr,
Item& removed
);
// Precondition: root_ptr is a root pointer of a non-empty binary search
// tree.
// Postcondition: The largest item in the binary search tree has been
// removed, and root_ptr now points to the root of the new (smaller) binary
// search tree. The reference parameter, removed, has been set to a copy
// of the removed item.
#include "bst.template"
#endif // BST_H
这里是我的二进制树模板文件
// FILE: bintree.template
// IMPLEMENTS: The binary_tree node class (see bintree.h for documentation).
#include <cassert> // Provides assert
#include <cstdlib> // Provides NULL, std::size_t
#include <iomanip> // Provides std::setw
#include <iostream> // Provides std::cout
template<class Process, class BTNode>
void inorder(Process f, BTNode *node_ptr)
// Library facilities used: cstdlib
{
if (node_ptr != NULL) {
inorder(f, node_ptr->left());
f(node_ptr->data());
inorder(f, node_ptr->right());
}
}
template<class Process, class BTNode>
void postorder(Process f, BTNode *node_ptr)
// Library facilities used: cstdlib
{
if (node_ptr != NULL) {
postorder(f, node_ptr->left());
postorder(f, node_ptr->right());
f(node_ptr->data());
}
}
template<class Process, class BTNode>
void preorder(Process f, BTNode *node_ptr)
// Library facilities used: cstdlib
{
if (node_ptr != NULL) {
f(node_ptr->data());
preorder(f, node_ptr->left());
preorder(f, node_ptr->right());
}
}
template<class Item, class SizeType>
void print(binary_tree_node <Item> *node_ptr, SizeType depth)
// Library facilities used: iomanip, iostream, stdlib
{
if (node_ptr != NULL) {
print(node_ptr->right(), depth + 1);
std::cout << std::setw(4 * depth) << ""; // Indent 4*depth spaces.
std::cout << node_ptr->data() << std::endl;
print(node_ptr->left(), depth + 1);
}
}
template<class Item>
void tree_clear(binary_tree_node <Item> *&root_ptr)
// Library facilities used: cstdlib
{
binary_tree_node<Item> *child;
if (root_ptr != NULL) {
child = root_ptr->left();
tree_clear(child);
child = root_ptr->right();
tree_clear(child);
delete root_ptr;
root_ptr = NULL;
}
}
template<class Item>
binary_tree_node <Item> *tree_copy(const binary_tree_node <Item> *root_ptr)
// Library facilities used: cstdlib
{
binary_tree_node<Item> *l_ptr;
binary_tree_node<Item> *r_ptr;
if (root_ptr == NULL)
return NULL;
else {
l_ptr = tree_copy(root_ptr->left());
r_ptr = tree_copy(root_ptr->right());
return
new binary_tree_node<Item>(root_ptr->data(), l_ptr, r_ptr);
}
}
template<class Item>
size_t tree_size(const binary_tree_node <Item> *node_ptr)
// Library facilities used: cstdlib
{
if (node_ptr == NULL)
return 0;
else
return
1 + tree_size(node_ptr->left()) + tree_size(node_ptr->right());
}
这是二叉树头
// FILE: bintree.h (part of the namespace main_savitch_10)
// PROVIDES: A template class for a node in a binary tree and functions for
// manipulating binary trees. The template parameter is the type of data in
// each node.
//
// TYPEDEF for the binary_tree_node<Item> template class:
// Each node of the tree contains a piece of data and pointers to its
// children. The type of the data (binary_tree_node<Item>::value_type) is
// the Item type from the template parameter. The type may be any of the C++
// built-in types (int, char, etc.), or a class with a default constructor,
// and an assignment operator.
//
// CONSTRUCTOR for the binary_tree_node<Item> class:
// binary_tree_node(
// const item& init_data = Item( ),
// binary_tree_node<Item>* init_left = NULL,
// binary_tree_node<Item>* init_right = NULL
// )
// Postcondition: The new node has its data equal to init_data,
// and it's child pointers equal to init_left and init_right.
//
// MEMBER FUNCTIONS for the binary_tree_node<Item> class:
// const item& data( ) const <----- const version
// and
// Item& data( ) <----- non-const version
// Postcondition: The return value is a reference to the data from
// this binary_tree_node.
//
// const binary_tree_node* left( ) const <----- const version
// and
// binary_tree_node* left( ) <----- non-const version
// and
// const binary_tree_node* right( ) const <----- const version
// and
// binary_tree_node* right( ) <----- non-const version
// Postcondition: The return value is a pointer to the left or right child
// (which will be NULL if there is no child).
//
// void set_data(const Item& new_data)
// Postcondition: The binary_tree_node now contains the specified new data.
//
// void set_left(binary_tree_node* new_link)
// and
// void set_right(binary_tree_node* new_link)
// Postcondition: The binary_tree_node now contains the specified new link
// to a child.
//
// bool is_leaf( )
// Postcondition: The return value is true if the node is a leaf;
// otherwise the return value is false.
//
// NON-MEMBER FUNCTIONS to maniplulate binary tree nodes:
// tempate <class Process, class BTNode>
// void inorder(Process f, BTNode* node_ptr)
// Precondition: node_ptr is a pointer to a node in a binary tree (or
// node_ptr may be NULL to indicate the empty tree).
// Postcondition: If node_ptr is non-NULL, then the function f has been
// applied to the contents of *node_ptr and all of its descendants, using
// an in-order traversal.
// Note: BTNode may be a binary_tree_node or a const binary tree node.
// Process is the type of a function f that may be called with a single
// Item argument (using the Item type from the node).
//
// tempate <class Process, class BTNode>
// void postorder(Process f, BTNode* node_ptr)
// Same as the in-order function, except with a post-order traversal.
//
// tempate <class Process, class BTNode>
// void preorder(Process f, BTNode* node_ptr)
// Same as the in-order function, except with a pre-order traversal.
//
// template <class Item, class SizeType>
// void print(const binary_tree_node<Item>* node_ptr, SizeType depth)
// Precondition: node_ptr is a pointer to a node in a binary tree (or
// node_ptr may be NULL to indicate the empty tree). If the pointer is
// not NULL, then depth is the depth of the node pointed to by node_ptr.
// Postcondition: If node_ptr is non-NULL, then the contents of *node_ptr
// and all its descendants have been written to cout with the << operator,
// using a backward in-order traversal. Each node is indented four times
// its depth.
//
// template <class Item>
// void tree_clear(binary_tree_node<Item>*& root_ptr)
// Precondition: root_ptr is the root pointer of a binary tree (which may
// be NULL for the empty tree).
// Postcondition: All nodes at the root or below have been returned to the
// heap, and root_ptr has been set to NULL.
//
// template <class Item>
// binary_tree_node<Item>* tree_copy(const binary_tree_node<Item>* root_ptr)
// Precondition: root_ptr is the root pointer of a binary tree (which may
// be NULL for the empty tree).
// Postcondition: A copy of the binary tree has been made, and the return
// value is a pointer to the root of this copy.
//
// template <class Item>
// size_t tree_size(const binary_tree_node<Item>* node_ptr)
// Precondition: node_ptr is a pointer to a node in a binary tree (or
// node_ptr may be NULL to indicate the empty tree).
// Postcondition: The return value is the number of nodes in the tree.
#ifndef BINTREE_H
#define BINTREE_H
#include <cstdlib> // Provides NULL and size_t
template <class Item>
class binary_tree_node
{
public:
// TYPEDEF
typedef Item value_type;
// CONSTRUCTOR
binary_tree_node(
const Item& init_data = Item(),
binary_tree_node* init_left = NULL,
binary_tree_node* init_right = NULL
)
{
data_field = init_data;
left_field = init_left;
right_field = init_right;
}
// MODIFICATION MEMBER FUNCTIONS
Item& data() { return data_field; }
binary_tree_node*& left() { return left_field; }
binary_tree_node*& right() { return right_field; }
void set_data(const Item& new_data) { data_field = new_data; }
void set_left(binary_tree_node* new_left) { left_field = new_left; }
void set_right(binary_tree_node* new_right) { right_field = new_right; }
// CONST MEMBER FUNCTIONS
const Item& data() const { return data_field; }
const binary_tree_node* left() const { return left_field; }
const binary_tree_node* right() const { return right_field; }
bool is_leaf() const
{
return (left_field == NULL) && (right_field == NULL);
}
private:
Item data_field;
binary_tree_node* left_field;
binary_tree_node* right_field;
};
// NON-MEMBER FUNCTIONS for the binary_tree_node<Item>:
template <class Process, class BTNode>
void inorder(Process f, BTNode* node_ptr);
template <class Process, class BTNode>
void preorder(Process f, BTNode* node_ptr);
template <class Process, class BTNode>
void postorder(Process f, BTNode* node_ptr);
template <class Item, class SizeType>
void print(binary_tree_node<Item>* node_ptr, SizeType depth);
template <class Item>
void tree_clear(binary_tree_node<Item>*& root_ptr);
template <class Item>
binary_tree_node<Item>* tree_copy(const binary_tree_node<Item>* root_ptr);
template <class Item>
std::size_t tree_size(const binary_tree_node<Item>* node_ptr);
#include "bintree.template"
#endif // BINTREE_H
这是我的测试文件
#include <string>
#include "bst.h"
using namespace std;
int rnd() {
return rand() % 10000;
}
int main() {
binary_search_tree<string> bst;
cout << bst << endl;
bst.insert("baker");
cout << bst << endl;
// making sure the output operator was working properly.
bst.get_root()->set_left(new binary_tree_node<string>("able"));
cout << bst << endl;
bst.get_root()->set_right(new binary_tree_node<string>("charlie"));
cout << bst << endl;
bst.insert("arthur");
print(bst.get_root(), 0);
cout << endl;
string data[] = { "able", "baker", "charlie", "dog", "easy", "fox", "george" };
int size = 7;
binary_search_tree<string> bst1;
for (int i = 0; i < size; ++i) {
bst1.insert(data[i]);
cout << bst1 << endl;
}
cout << "balanced? " << bst1.is_balanced() << endl << endl;;
string data2[] = { "dog", "baker", "able", "fox", "charlie", "george", "easy" };
binary_search_tree<string> bst2;
for (int i = 0; i < size; ++i) {
bst2.insert(data2[i]);
cout << bst2 << endl;
}
print(bst2.get_root(), 0);
cout << "balanced? " << bst2.is_balanced() << endl << endl;
binary_search_tree<int> bst3;
for (int i = 0; i < 50; i++) {
bst3.insert(rnd());
}
cout << bst3 << endl;
cout << "balanced? " << bst3.is_balanced() << endl << endl;
cout << "remove " << bst2.remove("able") << endl;
cout << bst2 << endl;
cout << "remove " << bst2.remove("baker") << endl;
cout << bst2 << endl;
cout << "remove " << bst2.remove("fox") << endl;
cout << bst2 << endl;
print(bst2.get_root(), 0);
}
看着我的书只会让我感到困惑，因为它处理的是节点，而不是bools。
您需要为insert创建一个助手函数，该函数还传递树的节点。
bool插入(项目、节点(
私有函数的声明。
template <class Item>
bool bst_insert(binary_tree_node<Item>*& root_ptr, const Item& target) ;
算法
- 检查root_ptr是否为null，分配一个节点并设置root_ptr目标
- 如果target==root_ptr数据，则返回false
- 否则如果目标<root_ptr，调用bst_insert(&root_ptr->left，target(
- else如果target>root_prt，则调用bst_insert(&root_prt->right，target(