问题遇到的现象和发生背景
代码是 照着<<数据结构,算法与应用c++语言描述>>(Sartaj Sahni著)敲得,运行后编译不报错,但运行后出问题,说
undefined reference to `linkedBinaryTree<int>::visit’
但我确实提供了模板特化
问题相关代码
#ifndef TEST_LINKEDBINARYTREE_H
#define TEST_LINKEDBINARYTREE_H
using namespace std;
#include <iostream>
#include "binaryTree.h"
#include "../Queue/arrayQueue.h"
#include "binaryTreeNode.h"
#include "../myExceptions.h"
#include "booster.h"
template <class E>
class linkedBinaryTree : public binaryTree<binaryTreeNode<E>>
{
public:
linkedBinaryTree() {root = NULL; treeSize = 0;}
~linkedBinaryTree() override {erase();};
bool empty() const override {return treeSize == 0;}
int size() const override {return treeSize;}
E* rootElement() const;
void makeTree(const E& element, linkedBinaryTree<E>&, linkedBinaryTree<E>&);
linkedBinaryTree<E>& removeLeftSubtree();
linkedBinaryTree<E>& removeRightSubtree();
//preOrder,inOrder,postOrder的包装形式
void preOrder(void (*theVisit) (binaryTreeNode<E>*)) override
{visit = theVisit; preOrder(root);}
void inOrder(void (*theVisit) (binaryTreeNode<E>*)) override
{visit = theVisit; inOrder(root);}
void postOrder(void (*theVisit) (binaryTreeNode<E>*)) override
{visit = theVisit; postOrder(root);}
void levelOrder(void (*) (binaryTreeNode<E>*)) override;
void preOrderOutput(){preOrder(output); cout << endl;}
void inOrderOutput(){inOrder(output); cout << endl;}
void postOrderOutput(){postOrder(output); cout << endl;}
void levelOrderOutput(){levelOrder(output); cout << endl;}
void erase()
{
postOrder(dispose);
root = nullptr;
treeSize = 0;
}
int height() const {return height(root);}
protected:
binaryTreeNode<E> *root;
int treeSize;
static void (*visit)(binaryTreeNode<E>*);//静态成员 函数指针
static int count;
static void preOrder(binaryTreeNode<E> *t);
static void inOrder(binaryTreeNode<E> *t);
static void postOrder(binaryTreeNode<E> *t);
static void countNodes(binaryTreeNode<E> *t){
visit = addToCount;
count = 0;
preOrder(t);
}
static void dispose(binaryTreeNode<E> *t) {delete t;}
static void output(binaryTreeNode<E> *t) {cout << t->element << ' ';}
static void addToCount(binaryTreeNode<E> *t) {count++;}
static int height(binaryTreeNode<E> *t);
};
//visit的模板特化
template <>
void (*linkedBinaryTree<int>::visit)(binaryTreeNode<int>*);
template <>
void (*linkedBinaryTree<booster>::visit)(binaryTreeNode<booster>*);
template <>
void (*linkedBinaryTree<pair<int,int>>::visit)(binaryTreeNode<pair<int,int>>*);
template <>
void (*linkedBinaryTree<pair<const int,char>>::visit)(binaryTreeNode<pair<const int,char>>*);
template <>
void (*linkedBinaryTree<pair<const int,int>>::visit)(binaryTreeNode<pair<const int,int>>*);
template <class E>
E* linkedBinaryTree<E>::rootElement() const
{
if (treeSize == 0)
return NULL;
else
return &root->element;
}
template <class E>
void linkedBinaryTree<E>::makeTree(const E &element, linkedBinaryTree<E>& left, linkedBinaryTree<E>& right)
{
root = new binaryTreeNode<E> (element, left.root, right.root);
treeSize = left.treeSize + right.treeSize + 1;
left.root = right.root = NULL;
left.treeSize = right.treeSize = 0;
}
template <class E>
linkedBinaryTree<E>& linkedBinaryTree<E>::removeLeftSubtree()
{
if (treeSize == 0)
throw emptyTree();
linkedBinaryTree<E> LeftSubtree;
LeftSubtree.root = root->rightChild;
count = 0;
LeftSubtree.treeSize = countNodes(LeftSubtree.root);
root->rightChild = NULL;
treeSize -= LeftSubtree.treeSize;
return LeftSubtree;
}
template <class E>
linkedBinaryTree<E>& linkedBinaryTree<E>::removeRightSubtree()
{
if (treeSize == 0)
throw emptyTree();
linkedBinaryTree<E> rightSubtree;
rightSubtree.root = root->rightChild;
count = 0;
rightSubtree.treeSize = countNodes(rightSubtree.root);
root->rightChild = NULL;
treeSize -= rightSubtree.treeSize;
return rightSubtree;
}
template <class E>
void linkedBinaryTree<E>::preOrder(binaryTreeNode<E> *t)
{
if (t != nullptr)
{
(*visit)(t);
preOrder(t->leftChild);
preOrder(t->rightChild);
}
}
template <class E>
void linkedBinaryTree<E>::inOrder(binaryTreeNode<E> *t)
{
if (t != nullptr)
{
preOrder(t->leftChild);
(*visit)(t);
preOrder(t->rightChild);
}
}
template <class E>
void linkedBinaryTree<E>::postOrder(binaryTreeNode<E> *t)
{
if (t != nullptr)
{
preOrder(t->leftChild);
preOrder(t->rightChild);
(*visit)(t);
}
}
template <class E>
void linkedBinaryTree<E>::levelOrder(void (*theVisit) (binaryTreeNode<E>*))
{
arrayQueue<binaryTreeNode<E>*> q;
binaryTreeNode<E> *t = root;
while (t != nullptr)
{
theVisit(t);
if (t->leftChild != nullptr)
q.push(t->leftChild);
if (t->rightChild != nullptr)
q.push(t->rightChild);
try {t = q.front();}
catch (queueEmpty) {return;}
q.pop();
}
}
template <class E>
int linkedBinaryTree<E>::height(binaryTreeNode<E> *t)
{
if (t == nullptr)
return 0;
int hl = height(t->leftChild);
int hr = height(t->rightChild);
if (hl > hr)
return ++hl;
else
return ++hr;
}
#endif //TEST_LINKEDBINARYTREE_H
测试代码
#include <iostream>
#include "linkedBinaryTree.h"
using namespace std;
int main()
{
linkedBinaryTree<int> a,x,y,z;
y.makeTree(1,a,a);
z.makeTree(2,a,a);
x.makeTree(3,y,z);
y.makeTree(4,x,a);
cout << "Number of nodes = ";
cout << y.size() << endl;
cout << "height = ";
cout << y.height() << endl;
cout << "Preorder sequence is ";
y.preOrderOutput();
cout << "Inorder sequence is ";
y.inOrderOutput();
cout << "Postorder sequence is ";
y.postOrderOutput();
cout << "Level order sequence is ";
y.levelOrderOutput();
return 0;
}