关于二叉树实现过程编译出错。
程序代码：#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 编辑 ]
