式評価(ツリーメソッド/C++言語記述)(一)

演算式(以下、式と略す)を二叉木で求め、実質的には式を二叉木に変換して後順に遍歴し、接尾辞式を得ると同時に式の値を求めることができる.変換と評価の過程もデータ構造スタックの助けを借りる必要がある.
ツリーデータ構造では、2つのクラス、ツリーノードクラス(BinaryTreeNode)、およびツリークラス(BinaryTree)を宣言する必要があります.この2つのクラスはテンプレートクラスです.

  1 #ifndef BINARYTREE_H
  2 #define BINARYTREE_H
  3 
  4 template  class BinaryTree;
  5 
  6 template 
  7 class BinaryTreeNode
  8 {
  9 public:
 10     friend class BinaryTree;
 11     T _data;
 12 
 13 private:
 14     BinaryTreeNode * _leftChild;
 15     BinaryTreeNode * _rightChild;
 16 };
 17 
 18 template 
 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 * _root;
 49 
 50     void destory()
 51     {
 52         if (_root)
 53         {
 54             destory(_root);
 55             delete _root;
 56         }
 57     }
 58 
 59     void destory(BinaryTreeNode * 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 * 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 * 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 * 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クラスで友元クラスとして宣言する必要があります.また,2つのクラス間にループ依存性があるため,BinaryTreeNodeクラスの前に前方向参照宣言を加える必要がある.BinaryTreeクラスのメソッドの大部分は二叉木の遍歴に基づいており、メソッド体は比較的短いと同時に、コンパイルエラーを防止するために、直接メソッドの実装をクラス宣言に書く.preOrder()メソッド、inOrder()メソッド、postOrder()メソッドは、BinaryTreeクラスのサブクラスで書き換える必要があるため、虚関数として定義されます.
転載先:https://www.cnblogs.com/lets-blu/p/7281917.html