将排序链接列表转换为平衡的二进制搜索树

Question

我的代码可以工作，但我需要帮助修改它，使它更短和简单，如果可能的话，我的main.cpp部件。其他文件是使程序编译和计算，如果您想看到的输出。

main.cpp:

#include <stdio.h>
#include "bintree.h"
#include <string.h>
#include <list>
#include <stack>
#include <stdlib.h>
#include <iostream>

using namespace std;
using namespace main_savitch_10;

list<int>* item_list = new list<int>;
list<int>* item_list2 = new list<int>;

list<int>* create_list()
{
     for(int i = 1; i <= 9; i++)
{
     item_list -> push_front(i);
     item_list -> sort();
}
return item_list;
}

    list<int>* temp2 = new list<int>;
    template <class Item>
    binary_tree_node<int>* balanced_tree_rec(list<Item>* list,Item count)

{
    if(count <= 0)
         {return NULL;}
    if(list == NULL)
         {return NULL;}

     binary_tree_node<int>*left=balanced_tree_rec(list, count /2);
     binary_tree_node<int>* temp = new binary_tree_node<int>(list->front());
for(int i = 1; i <= count / 2; i++)
{
     temp = new binary_tree_node<int>( list->front() );
}
temp2 = list;
temp2 -> pop_front();

     binary_tree_node <int>* right = balanced_tree_rec(temp2, count - ( count / 2) -1);
     binary_tree_node<int>* root = new binary_tree_node<int>(temp -> data(), left, right);
return root;
}

template <class Item>
binary_tree_node<int>* BBST(list<Item>* list)
{
     int count = list->size();
     return balanced_tree_rec(list, count);
}

template <class Item>
void push(Item& test)
{
     item_list2 -> push_back(test);
}

template<class Item>
void print(binary_tree_node<Item>* tree)
{
     if(tree)
     {
     cout << tree -> data() << " ";
     printT(tree -> left());
     printT(tree -> right());
     }
}
int main()
{
        printf("The Balance Binary Search Tree\n");

     list<int>* a = create_list();

     binary_tree_node<int>* p = BBST(a);

     print(p, 1);

   return 0;
}

bintree.h头文件

// 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

namespace main_savitch_10
{

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.template:

// 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

namespace main_savitch_10
{
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( ));
}
}

Answer 1

缩短main.cpp

将所有模板函数移到bintree.h或bintree.template中。模板是通用的，实际上不应该在您使用它们的文件中。也许可以将main.cpp中的模板函数作为二叉树类的一部分。

使用命名空间std；

名称空间的发明是为了防止来自不同来源的函数名之间的冲突。代码包含一个特定的名称空间main_savitch_10.在实际使用的main_savitch_10 std:：中。如果在所有代码中完全指定了命名空间，那么对于必须维护此代码的任何人来说，这将不会让人感到困惑。看看这个关于StackOverflow的问题。

在您的函数balanced_tree_rec()中尤其如此，如果声明了它，它将更加可读性和可维护性。

binary_tree_node<int>* balanced_tree_rec(std::list<Item>* list,Item count)

全局变量

对全局变量的使用通常是不赞成的。它们可能有一些有效的用途，但是在模板函数中使用全局变量并不是可移植的，也是不可维护的。它有效地破坏了模板函数。

list<int>* item_list = new list<int>;
list<int>* item_list2 = new list<int>;
list<int>* temp2 = new list<int>;

模板binary_tree_node* balanced_tree_rec(列表*列表，项目计数)

    temp2 = list;
    temp2 -> pop_front();

模板空隙推送(项目和测试)

    item_list2 -> push_back(test);

使用有意义的名称

在软件开发领域，其他人经常需要维护我们编写的代码，变量名和函数名应该清楚地指出它们是什么，这些例子将是BBST()、list、p和a；

标准文件扩展名

关于Stack溢出，有几个关于模板文件的适当扩展名的讨论，您可能需要看看这些文件(约定、扩展和模板)。我个人会将它添加到bintree.h的名称空间部分，或者创建一个bintree.hpp。boost库使用hpp。我将两个文件合并为一个文件的原因是，如果没有bintree.h，模板文件本身就无法编译。

Answer 2

内存管理

您没有跟踪指向已分配内存的指针。这意味着你在漏掉记忆。通常，程序中的每个new都应该与delete配对。

看看这个循环：

binary_tree_node<int>* temp = new binary_tree_node<int>(list->front());
for (int i = 1; i <= count / 2; i++)
{
    temp = new binary_tree_node<int>(list->front());
}

您正在一次又一次地为binary_tree_node创建一个新实例。对这些创建的对象的唯一引用是每次分配给临时指针时都会被覆盖，这意味着内存丢失了，无法恢复。要实现同样的目标，只需分配一个内存，就可以这样做：

int temp_list_head = list->front();    
for (int i = 1; i <= count / 2; i++)
{
    temp_list_head = list->front();
}
binary_tree_node<int>* temp = new binary_tree_node<int>(temp_list_head);

您在代码的末尾有一个类似的问题，在您构建的树之后，您没有清理。你错过了main结尾的电话：

tree_clear(p);