二叉树遍历函数的两种实现方法的比较

　　考虑下面一个二叉树的实现：

 1 enum Operator {PLUS = 1, MINUS = 2, MULTIPLY = 3, DIVIDE = 4};
 2 
 3 class BinTreeNode
 4 {
 5 public:
 6     virtual ~BinTreeNode() {};
 7     virtual bool IsLeaf() = 0;
 8 };
 9 
10 class LeafNode : public BinTreeNode
11 {
12 private:
13     double operand;
14 public:
15     LeafNode(const double &op) : operand(op) {}
16     bool IsLeaf() const { return true; }
17     double GetOperand() const { return operand; }
18 };
19 
20 class IntlNode : public BinTreeNode
21 {
22 public:
23     IntlNode(BinTreeNode *l, BinTreeNode *r, Operator _op) : lc(l), rc(r), op(_op) {}
24     bool IsLeaf() { return false; }
25     BinTreeNode* GetLeftChild() const { return lc; }
26     BinTreeNode* GetRightChild() const { return rc; }
27     Operator GetOperator() const { return op; }
28 private:
29     BinTreeNode *lc;
30     BinTreeNode *rc;
31     Operator op;
32 };

　　要对该二叉树实现前序遍历，有如下两种实现方法：

　　方法一：

 1 void Traverse(BinTreeNode* root)
 2 {
 3     if (root == nullptr)
 4     {
 5         return;
 6     }
 7     if (root->IsLeaf()) //结点为叶子结点
 8     {
 9         std::cout << "Leaf node: " << static_cast<LeafNode*>(root)->GetOperand() << std::endl;
10     }
11     else //内部结点
12     {
13         std::cout << "Internal node: " << static_cast<IntlNode*>(root)->GetOperator() << std::endl;
14         Traverse(static_cast<IntlNode*>(root)->GetLeftChild());
15         Traverse(static_cast<IntlNode*>(root)->GetRightChild());
16     }
17 }

　　方法二：

　　首先在基类中将遍历函数声明为纯虚函数

1 class BinTreeNode
2 {
3 public:
4     virtual ~BinTreeNode() {};
5     virtual bool IsLeaf() = 0;
6     virtual void Traverse() = 0;
7 };

　　随后定义如下函数：

 1 void LeafNode::Traverse() const
 2 {
 3     std::cout << "Leaf node: " << operand << std::endl;
 4 }
 5 
 6 void IntlNode::Traverse() const
 7 {
 8     std::cout << "Internal node: " << op << std::endl;
 9     if (lc != nullptr)
10     {
11         GetLeftChild()->Traverse();
12     }
13     if (rc != nullptr)
14     {
15         GetRightChild()->Traverse();
16     }
17 }
18 
19 void Traverse(BinTreeNode *root)
20 {
21     if (root != nullptr)
22     {
23         root->Traverse();
24     }
25 }

　　对比：

　　从代码中可以看出，方法一不要求结点类支持Traverse()函数，但缺点在于定义在类外的Traverse()函数需要对结点类很熟悉，知道其实现细节，且添加新子类时需要修改Traverse()的代码；

　　而方法二要求对树实现遍历的操作要在结点类中实现，也因此，定义在类外的Traverse()函数不需要了解结点类的实现细节，遍历的处理工作由子类自行解决，且函数不需要枚举所有结点子类，直接就能进行合适的操作。

　　通常情况下，若有意把结点和树分开，需要隐藏结点类的内部细节，那应该选择使用方法二，反之则方法一更合适。

二叉树遍历函数的两种实现方法的比较

推荐阅读