- 首先要构造一个二叉树,二叉树的构造包含两个类的定义,一个是结点类,另一个是二叉树类。
- 毫无疑问二叉树类里引用了结点类,为了让二叉树类能顺利引用并修改结点类里的数据,所以我在结点类里声明了友元类。
- 另外不要忘记我们要定义模板类,这样有利于二叉树对不同类型数据的操作。
话不多说,直接上代码👇
#include<iostream>
using namespace std;
//结点类
template<class T>
class BinaryTreeNode {
//友元类声明
template<class T>
friend class BinaryTree;
private:
T data;
BinaryTreeNode<T>* leftchild;
BinaryTreeNode<T>* rightchild;
public:
//构造函数
BinaryTreeNode() {
leftchild = NULL;
rightchild = NULL;
}
BinaryTreeNode(const T& dataValue) {
data = dataValue;
leftchild = NULL;
rightchild = NULL;
}
BinaryTreeNode(const T& dataValue, BinaryTreeNode<T>* leftchildValue, BinaryTreeNode<T>* rightchildValue) {
data = dataValue;
leftchild = leftchildValue;
rightchild = rightchildValue;
}
//析构函数
~BinaryTreeNode() {
leftchild = NULL;
rightchild = NULL;
}
//访问结点
void VisitNode() {
cout << data << " ";
}
//取左结点
BinaryTreeNode<T>* getLeft() {
return leftchild;
}
//取右结点
BinaryTreeNode<T>* getRight() {
return rightchild;
}
};
//二叉树类
template<class T>
class BinaryTree {
private:
BinaryTreeNode<T>* root;
public:
//构造函数
BinaryTree() {
root = NULL;
cout << "Now start to construct the BinaryTree" << endl;
CreateNode(root);
}
//析构函数
~BinaryTree() {
root = NULL;
}
//前序构建二叉树
void CreateNode(BinaryTreeNode<T>* &treeNode) {
cout << "Please enter a value or '#' to stop:";
T dataValue;
cin >> dataValue;
treeNode = new BinaryTreeNode<T>(dataValue);
if (treeNode->data == '#') {
delete treeNode;
treeNode = NULL;
}
else {
CreateNode(treeNode->leftchild);
CreateNode(treeNode->rightchild);
}
}
//取根节点
BinaryTreeNode<T>* getRoot() {
return root;
}
};
int main() {
BinaryTree<char> test;
}
总结:模板类是真的难用!