我很新的节目,而我用C ++语言工作。 这是我的功课,并使用二叉搜索树。 我所要做的是创建一个名为find_node功能,后来再调用名为delete_node功能。 这是老师给作为find_node功能的提示。
从教授提示:
添加void find_node( const T &val )
方法对类节点,以查找包含val中的节点; 如果你没有找到,没有什么,如果你找到了,p是节点*指向它做,通过调用delete p delete_node( Node< T > *&p )
void delete_node( Node< T > *&p )
方法,从二进制树中删除节点p
文件由教授给出
btree.h
#include <iostream>
#include "node.h"
//using namespace std;
template < typename elemType >
class BinaryTree {
public:
BinaryTree( );
~BinaryTree( );
void insert( const elemType & );
void remove( const elemType & );
void inorder( );
bool empty( );
void clear( );
private:
Node< elemType > *_root;
BinaryTree( const BinaryTree & );
BinaryTree &operator =( const BinaryTree & );
void clear( Node< elemType > * );
};
template < typename elemType >
inline BinaryTree< elemType >::BinaryTree( ) : _root(0)
{
cout << "BinaryTree::BinaryTree() "
<< "default constructor\n";
}
template < typename elemType >
inline BinaryTree< elemType >::~BinaryTree( )
{
cout << "BinaryTree::~BinaryTree() destructor\n";
clear( );
}
template < typename elemType >
inline void BinaryTree< elemType >::clear( )
{
if( _root )
{
clear( _root );
_root = 0;
}
}
template < typename elemType >
inline void BinaryTree< elemType >::clear( Node< elemType > *pt )
{
if( pt ) {
cout << "clear( ) left of " << pt->value( ) << '\n';
clear( pt->left( ) );
cout << "clear( ) right of " << pt->value( ) << '\n';
clear( pt->right( ) );
delete pt;
}
}
template < typename elemType >
inline void BinaryTree< elemType >::insert( const elemType &e )
{
if( !_root )
{
_root = new Node< elemType >( e );
}
else
{
_root->insert_value( e );
}
}
template < typename elemType >
inline void BinaryTree< elemType >::remove( const elemType &e )
{
_root->find_node( _root, e );
}
template < typename elemType>
inline void BinaryTree< elemType >::inorder( )
{
_root->inorder( _root );
cout << '\n';
}
由教授给出的,但该文件我已经到了2种方法从提示添加到
node.h
#ifndef NODE_H
#define NODE_H
#include <string>
using namespace std;
template< typename T >
class Node
{
public:
Node( const T &);
T value( ) const;
T value( const T & );
void insert_value( const T & );
void inorder( const Node * );
void find_node( const T &val, const T* root );
//bool find_node( const T &val, Node < T > *node) const;
void delete_node( Node< T > *&p );
Node * left ( ) const;
Node * left ( Node * );
Node * right( ) const;
Node * right( Node * );
private:
T _value;
Node * _left;
Node * _right;
Node< T > * root; //point to root node
Node::Node( const Node & );
Node &operator =( const Node & );
};
template< typename T >
inline Node< T >::Node( const T &rhs )
{
_value = rhs; // assign rhs to _value
_left = _right = 0; // node is not part of a tree yet
}
template< typename T >
inline T Node< T >::value( ) const
{
return _value;
}
template< typename T >
inline T Node< T >::value( const T &rhs )
{
_value = rhs; // new value for _value
return _value;
}
template< typename T >
inline Node< T > *Node< T >::left( ) const
{
return _left;
}
template< typename T >
inline Node< T > *Node< T >::left( Node< T > *rhs )
{
_left = rhs;
return _left;
}
template< typename T >
inline Node< T > *Node< T >::right( ) const
{
return _right;
}
template< typename T >
inline Node< T > *Node< T >::right( Node< T > *rhs )
{
_right = rhs;
return _right;
}
template< typename T >
inline void Node< T >::insert_value( const T &val )
{
if( val == _value )
{
return; // value already in the tree
}
if( val < _value ) // val should appear at the left
{
if( ! _left ) // no left subtree ?
{ // add new node here
_left = new Node( val );
}
else // try the subtree
{
_left->insert_value( val );
}
}
else // val should appear at the right
{
if( ! _right ) // no right subtree ?
{ // add new node here
_right = new Node( val );
}
else // try the subtree
{
_right->insert_value( val );
}
}
}
template< typename T >
inline void Node< T >::inorder( const Node< T > *pt )
{
if( pt )
{
inorder( pt->_left );
cout << std::hex << pt->_left << std::dec << '\t';
cout << std::hex << pt << std::dec << '\t';
cout << std::hex << pt->_right << std::dec << '\t';
cout << pt->_value << '\n';
inorder( pt->_right );
}
}
template <typename T>
Node<T> const * find_node(const T &val)
{
Node<T> const * curr = root;
while( curr != 0 )
{
if (val == curr -> _value) {
break;
}
else if (val < curr -> _value) {
curr = curr -> _left;
|
else {
curr = curr -> _right;
}
}
return curr;
}
}
template <typename T >
inline void find_node( const T & val, const T * root ) {
Node<T> const * ptrFoundNode = find_node_pointer( val, root );
if( ptrFoundNode ) {
delete_node( ptrFoundNode, root );
}
}
template< typename T >
inline void Node< T >::delete_node(Node < T > *&p)
{
Node<T> *curr, *prev, *temp;
if (p == NULL) return;
if (p->_left == NULL && p->_right == NULL) {
// no children - easy
// *** if allowing counted duplicates:
// *** if (p->getCount() > 1) (*p)--;
// *** else {
temp = p;
p = NULL;
delete temp;
}
else if (p->_left == NULL) {
// only a right child - still easy
// *** if allowing counted duplicates:
// *** if (p->getCount() > 1) (*p)--;
// *** else {
temp = p;
p = temp->_right;
delete temp;
}
else if (p->_right == NULL) {
// only a left child - still easy
// *** if allowing counted duplicates:
// *** if (p->getCount() > 1) (*p)--;
// *** else {
temp = p;
p = temp->_left;
delete temp;
}
else {
// two children - this is the hard case
// use successor: once right, then as far left as possible
// *** if allowing counted duplicates:
// *** if (p->getCount() > 1) (*p)--;
// *** else {
curr = p->_right;
prev = NULL;
while (curr->_left != NULL) {
prev = curr;
curr = curr->left;
}
p->data = curr->data;
if (prev == NULL) p->_right = curr->_right;
else prev->_left = curr->_right;
delete curr;
}
}
#endif