表达式求值，二叉树方法/C++语言描述

　　使用二叉树对算数表达式（以下简称为表达式）进行求值，实质上是将表达式转换为二叉树，对其进行后序遍历，得到后缀表达式的同时可以求得表达式的值。转换和求值的过程也需要借助数据结构栈的帮助。

　　二叉树数据结构需要声明2个类，二叉树节点类（BinaryTreeNode）和二叉树类（BinaryTree），这两个类都是模板类：

  1 #ifndef BINARYTREE_H
  2 #define BINARYTREE_H
  3 
  4 template <typename T> class BinaryTree;
  5 
  6 template <typename T>
  7 class BinaryTreeNode
  8 {
  9 public:
 10     friend class BinaryTree<T>;
 11     T _data;
 12 
 13 private:
 14     BinaryTreeNode<T> * _leftChild;
 15     BinaryTreeNode<T> * _rightChild;
 16 };
 17 
 18 template <typename T>
 19 class BinaryTree
 20 {
 21 public:
 22     BinaryTree()
 23     {
 24         _root = nullptr;
 25     }
 26 
 27     ~BinaryTree()
 28     {
 29         destory();
 30     }
 31 
 32     void preOrder()
 33     {
 34         preOrder(_root);
 35     }
 36 
 37     void inOrder()
 38     {
 39         inOrder(_root);
 40     }
 41 
 42     void postOrder()
 43     {
 44         postOrder(_root);
 45     }
 46 
 47 protected:
 48     BinaryTreeNode<T> * _root;
 49 
 50     void destory()
 51     {
 52         if (_root)
 53         {
 54             destory(_root);
 55             delete _root;
 56         }
 57     }
 58 
 59     void destory(BinaryTreeNode<T> * node)
 60     {
 61         if (node)
 62         {
 63             destory(node->_leftChild);
 64             destory(node->_rightChild);
 65             // visit binary tree data
 66             if (node->_leftChild)
 67             {
 68                 delete node->_leftChild;
 69             }
 70             if (node->_rightChild)
 71             {
 72                 delete node->_rightChild;
 73             }
 74         }
 75     }
 76 
 77     virtual void preOrder(BinaryTreeNode<T> * node)
 78     {
 79         if (node)
 80         {
 81             // visit binary tree data
 82             preOrder(node->_leftChild);
 83             preOrder(node->_rightChild);
 84         }
 85     }
 86 
 87     virtual void inOrder(BinaryTreeNode<T> * node)
 88     {
 89         if (node)
 90         {
 91             inOrder(node->_leftChild);
 92             // visit binary tree data
 93             inOrder(node->_rightChild);
 94         }
 95     }
 96 
 97     virtual void postOrder(BinaryTreeNode<T> * node)
 98     {
 99         if (node)
100         {
101             postOrder(node->_leftChild);
102             postOrder(node->_rightChild);
103             // visit binary tree data
104         }
105     }
106 };
107 
108 #endif // BINARYTREE_H

由于BinaryTree类需要访问BinaryTreeNode类的私有成员，因此需要在BinaryTreeNode类中将其声明为友元类；又因为两类之间存在循环依赖，所以需要在BinaryTreeNode类前加上前向引用声明。BinaryTree类的方法大部分都基于对二叉树的遍历，方法体都比较短，同时为了防止编译出错，直接将方法的实现写在类声明中；preOrder()方法、inOrder()方法和postOrder()方法在BinaryTree类的子类中可能需要进行重写，因此被定义为虚函数。