关于二叉树实现过程编译出错。 - 编程论坛

程序代码：

#include <iostream>
#include <string>
using namespace std;
template<typename Type>
class BinaryTree;
template<typename valType>
class BTnode
{
public:
         friend class BinaryTree <valType>;
         BTnode(const valType &val);
         const valType& value() const {return _val;}
         int occurs() const {return _cnt;}
         void preorder(BTnode *pt,ostream &os) const;
         void display_val(BTnode *pt,ostream &os);
         void lchild_leaf(BTnode *leaf,BTnode *subtree);
         void insert_value(const valType &val);
         bool find_value(const valType &val) const;
         void remove_value(const valType &val,BTnode *&prev);
private:
         valType _val;
         int _cnt;
         BTnode *_lchild;
         BTnode *_rchild;
};
template<typename elemType>
class BinaryTree
{
  private:
      BTnode<elemType> *_root;
  public:
      BinaryTree();
      BinaryTree(const BinaryTree&);
      ~BinaryTree() ;
      BinaryTree& operator=(const BinaryTree&);
      bool empty() {return _root==0;}
      void clear() {if(_root) {clear(_root);_root=0;}}
      void insert(const elemType &elem);
      void remove(const elemType &elem);
      void clear(BTnode<elemType>*pt);
      void remove_root();
      void copy(BTnode<elemType>*&tar,BTnode<elemType>*src);
      void preorder(ostream &os) const {_root->preorder(_root,os);}
      ostream& print(ostream &os ) const {return os;}
      bool find(const elemType &elem) const;
      friend ostream& operator<<(ostream&,const BinaryTree<elemType>&);
};

程序代码：

#include"binary.h"
template<typename elemType>
BinaryTree<elemType>::BinaryTree():_root(0) {}

template<typename elemType>
BinaryTree<elemType>::BinaryTree(const BinaryTree &rhs)
{copy(_root,rhs._root);}

template<typename elemType>
BinaryTree<elemType>::~BinaryTree()
{clear();}

template<typename elemType>
BinaryTree<elemType>& BinaryTree<elemType>::operator=(const BinaryTree &rhs)
{
    if(this!=&rhs)
    {  clear();
       copy(_root,rhs._root);
    }
    return *this;
}
template<typename elemType>
void BinaryTree<elemType> ::insert(const elemType &elem)
{
   if(!_root)
        root=new BTnode<elemType>(elem);
   else _root->insert_value(elem);

}
template <typename elemType>
void BinaryTree<elemType>::remove(const elemType &elem)
{
  if(_root)
  {
     if(_root->val==elem)
         remove_root();
     else
         _root->remove_value(elem,_root);

  }
}

template <typename elemType>
void BinaryTree<elemType>::remove_root()
{
if(!_root) return ;
  BTnode<elemType> *tmp=_root;//保存根节点一份
  if(_root->_rchild) //找到根节点的右子树
  {
      _root->_root->_rchild;
  //搬移左子节点到原根节点右子树的最左子树
    if(tmp->_lchild) //原根节点的左子树
    {
    BTnode<elemType> *lc=tmp->lchild;//原根节点的左子树
    BTnode<elemType> *newlc=_root->lchild;//原根节点右子树的左子树
    if(!newlc)
    //没有左子树，直接搬移
       _root->_lchild=lc;
    else //有左子树，遍历到最底部的左子树
        BTnode<elemType>::lchild_leaf(lc,newlc);


    }
   }
  else _root=_root->_lchild;//原根节点没有右子树，
  delete tmp;

}

template<typename elemType>
void
BinaryTree< elemType>::clear(BTnode< elemType>*pt)

{
  if(pt)
  {
      clear(pt->_lchild);
      clear(pt->_rchild);
      delete pt;
  }

}
template <typename elemType>
void BinaryTree<elemType>::copy( BTnode<elemType> *&tar, BTnode<elemType> *src )
{
    if ( src )
    {
         tar = new BTnode<elemType>( src->_val );
         if ( src->_lchild ) copy( tar->_lchild, src->_lchild );
         if ( src->_rchild ) copy( tar->_rchild, src->_rchild );
    }
}

template <typename elemType>
bool BinaryTree<elemType>::find(const elemType &elem) const
{
    return !_root?false:_root->find_value(elem);

}
template <typename elemType>

ostream& operator<<(ostream& os,const BinaryTree<elemType> &bt)

{
    os<<"Tree:"<<endl;
    bt.print(os);
    return os;

}

程序代码：

#include "binary.h"
template<typename valType>
BTnode<valType>::BTnode(const valType &val):_val(val)
{
  _cnt=1;
  _lchild=_rchild=0;
}

template<typename valType>
void BTnode<valType> ::lchild_leaf(BTnode *leaf,BTnode *subtree)//subtree原根节点右子数的左子树
{
  while(subtree->_lchild)
      subtree=subtree->_child;//找到根节点右子树的最左子树
  subtree->_lchild=leaf;//搬移至左子树

}

template<typename valType>//非根节点的移除
void BTnode<valType> ::remove_value(const valType &val,BTnode *&prev)
{
  if(val<_val)
  {
      if(!_lchild)
          return ;
      else _lchild->remove_value(val,_lchild);
  }
  else if(val>_val)
  {
     if(!_rchild)
         return ;
     else
          _rchild->remove_value(val,_rchild);
  }
  else
  {//找到了
     if(_rchild)
     {
        prev=_rchild;
        if(_lchild)
            if(!prev->_lchild)
                prev->_lchild;
            else BTnode<valType>::lchild_leaf(_lchild,prev->lchild);
     }
     else
         prev=_lchild;
     delete this;

  }
}

template<typename valType>
void BTnode<valType> ::preorder(BTnode *pt,ostream &os) const
{

if(pt)

{
   display_val(pt,os);
   if(pt->_lchild)  preorder(pt->_lchild,os);
   if(pt->_rchild)  preorder(pt->_rchild,os);

}

}

template<typename valType>
void BTnode<valType> ::display_val(BTnode *pt,ostream &os)
{
    os<<pt->val;
    if(pt->_cnt>1)
        os<<"("<<pt->_cnt<<")"
    else os<<" ";
}

template<typename valType>
void BTnode<valType> ::insert_value(const valType &val)
{
   if(val==_val)
   {
     _cnt++;return ;
   }
   if(val<_val)
   {
       if(!_lchild)
           _lchild=new BTnode(val);
       else _lchild->insert_value(val);
   }

   else
   {
       if(!_rchild)
           _rchild=new BTnode(val);
       else _rchild->insert_value(val);
   }

}
template <typename valType>
bool BTnode<valType>::find_value(const valType &val) const
{
   if(val==_val)
       return true;
   if(val<_val)
   {
      if(!_lchild)
          return false;
      else return _lchild->find_value(val);

   }
   else
   {

      if(!_rchild)
          return false;
      else return _rchild->find_value(val);
   }

}

程序代码：

#include"binary.h"
#include <iostream>
#include <string>
#include <fstream>
int main()
{
   ofstream log("test.txt");
   BinaryTree<string> bt;
   bt.insert("Piglet");
   bt.insert("Eeyore");
   bt.insert("Roo");
   bt.insert("Tiegger");
   bt.insert("Chirs");
   bt.insert("Pjooh");
   bt.insert("Knaga");
   cout<<"preorder traversal:\n";
   bt.preorder(log);
   bt.remove("Piglet");
   cout<<"\n Preoorder taraversal after piglet remove:\n";
    bt.preorder(log);
   bt.remove("Eeyore");
    cout<<"\n Preorder taraversal after EeyORE remove:\n";
    bt.preorder(log);
    return 0;
}

编译有错
binary.cpp
main.cpp
Linking...
main.obj : error LNK2001: unresolved external symbol "public: __thiscall BinaryTree<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > >::~BinaryTree<class std::basic_string<char,struct std::char_traits<char>,cla
ss std::allocator<char> > >(void)" (??1?$BinaryTree@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@@QAE@XZ)
main.obj : error LNK2001: unresolved external symbol "public: void __thiscall BinaryTree<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > >::remove(class std::basic_string<char,struct std::char_traits<char>,cla
ss std::allocator<char> > const &)" (?remove@?$BinaryTree@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@@QAEXABV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@Z)
main.obj : error LNK2001: unresolved external symbol "public: void __thiscall BinaryTree<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > >::insert(class std::basic_string<char,struct std::char_traits<char>,cla
ss std::allocator<char> > const &)" (?insert@?$BinaryTree@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@@QAEXABV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@Z)
main.obj : error LNK2001: unresolved external symbol "public: __thiscall BinaryTree<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > >::BinaryTree<class std::basic_string<char,struct std::char_traits<char>,clas
s std::allocator<char> > >(void)" (??0?$BinaryTree@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@@QAE@XZ)
main.obj : error LNK2001: unresolved external symbol "public: void __thiscall BTnode<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > >::preorder(class BTnode<class std::basic_string<char,struct std::char_trait
s<char>,class std::allocator<char> > > *,class std::basic_ostream<char,struct std::char_traits<char> > &)const " (?preorder@?$BTnode@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@@QBEXPAV1@AAV?$basic_ostream@DU?$char_traits@D@std@@@
std@@@Z)
Debug/第六章书本.exe : fatal error LNK1120: 5 unresolved externals
执行 link.exe 时出错.
Creating browse info file...

[ 本帖最后由换空依晨于 2014-10-21 10:58 编辑 ]