Я пытаюсь заставить мою функцию inOrder работать для моего тестового файла. Моя функция должна упорядочить строку данных в двоичном дереве поиска. Я ожидал, что мой код сделает это, но до сих пор только получил код для распечатки root. Я попытался изменить параметры моей функции, чтобы они соответствовали строке данных, но я выдает ошибки. Я знаю, что алгоритм прост, но я просто не могу понять, какие части кода go где. Код, который я показываю, является моей единственной попыткой, которая выполняется. Код ниже - мой тестовый файл
#include <string>
#include "bst.h"
using namespace std;
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;
bst1.inOrder(bst1.get_root());
Это мой шаблон
#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) {
root = new binary_tree_node<T>(item);
if(root == NULL)
{
insert(item);
}
if(root->data() == item)
{
return false;
}else
{
return true;
}
}
/**
* 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;
}
template<class T>
void binary_search_tree<T>::inOrder(binary_tree_node<T>* ptr)
{
if(ptr != NULL)
{
inOrder(ptr->left());
std::cout << ptr->data();
//if(ptr->left() != NULL && ptr->right() != NULL)
std::cout << " " ;
inOrder(ptr->right());
}
Это мой заголовок
#ifndef BST_H
#define BST_H
#include "bintree.h"
#include <iostream>
template <class T>
class binary_search_tree {
public:
binary_search_tree() {
root = NULL;
}
/**
* 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);
~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; }
void inOrder(binary_tree_node<T>*);
//void inOrder(const T& item);
//void inOrder();
private:
binary_tree_node<T>* root;
};
template <class T>
std::ostream& operator<<(std::ostream& out, const binary_tree_node<T>* root);
#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
Судя по всему, я не получаю правильную переменную внутри моего inOrder в main. Я знаю, что следую правильному алгоритму, но я не уверен, что поставить для желаемого результата, который представляет собой отсортированные строки массива data []. мой код пока печатает только george, который является root, но не печатает весь список.