使用二叉树对算数表达式（以下简称为表达式）进行求值，实质上是将表达式转换为二叉树，对其进行后序遍历，得到后缀表达式的同时可以求得表达式的值。转换和求值的过程也需要借助数据结构栈的帮助。
二叉树数据结构需要声明2个类，二叉树节点类（BinaryTreeNode）和二叉树类（BinaryTree），这两个类都是模板类：
#ifndef BINARYTREE_H
#define BINARYTREE_H template <typename T> class BinaryTree; template <typename T>
class BinaryTreeNode
{
public:
friend class BinaryTree<T>;
T _data; private:
BinaryTreeNode<T> * _leftChild;
BinaryTreeNode<T> * _rightChild;
}; template <typename T>
class BinaryTree
{
public:
BinaryTree()
{
_root = nullptr;
} ~BinaryTree()
{
destory();
} void preOrder()
{
preOrder(_root);
} void inOrder()
{
inOrder(_root);
} void postOrder()
{
postOrder(_root);
} protected:
BinaryTreeNode<T> * _root; void destory()
{
if (_root)
{
destory(_root);
delete _root;
}
} void destory(BinaryTreeNode<T> * node)
{
if (node)
{
destory(node->_leftChild);
destory(node->_rightChild);
// visit binary tree data
if (node->_leftChild)
{
delete node->_leftChild;
}
if (node->_rightChild)
{
delete node->_rightChild;
}
}
} virtual void preOrder(BinaryTreeNode<T> * node)
{
if (node)
{
// visit binary tree data
preOrder(node->_leftChild);
preOrder(node->_rightChild);
}
} virtual void inOrder(BinaryTreeNode<T> * node)
{
if (node)
{
inOrder(node->_leftChild);
// visit binary tree data
inOrder(node->_rightChild);
}
} virtual void postOrder(BinaryTreeNode<T> * node)
{
if (node)
{
postOrder(node->_leftChild);
postOrder(node->_rightChild);
// visit binary tree data
}
}
}; #endif // BINARYTREE_H
由于BinaryTree类需要访问BinaryTreeNode类的私有成员，因此需要在BinaryTreeNode类中将其声明为友元类；又因为两类之间存在循环依赖，所以需要在BinaryTreeNode类前加上前向引用声明。BinaryTree类的方法大部分都基于对二叉树的遍历，方法体都比较短，同时为了防止编译出错，直接将方法的实现写在类声明中；preOrder()方法、inOrder()方法和postOrder()方法在BinaryTree类的子类中可能需要进行重写，因此被定义为虚函数。