如何简化这个二叉树遍历函数?

不。

开玩笑。我觉得它看起来很有效率。

为了可读性,我将枚举顺序值。

...
enum TOrder {ORDER_PRE, ORDER_IN, ORDER_POST};

template<typename T>
void traverse_binary_tree(BinaryTreeNode<T>* root,TOrder order = ORDER_PRE) {
...

“简单”是一个意见问题。除了一些风格上的问题(特别是使用神奇的数字而不是命名常量),考虑到具体的描述“遍历树并打印其内容,提供顺序选择”,这是最简单的方法。

但是,通过分离这两个关注点,您可以获得更大的灵活性:遍历树,并对数据执行一些操作。您可能希望以各种方式分析和操作数据,并打印数据,最好不要为每个操作重复遍历逻辑。相反,您可以添加额外的模板参数,以允许任意组合的前、后或顺序操作,按照以下步骤进行:

// PRE, IN and POST operations are unary function objects which can 
// take Node<T>* as their argument
template <typename T, typename PRE, typename IN, typename POST>
void traverse(Node<T>* root, PRE& pre, IN& in, POST& post)
{
    if (!root) return;

    pre(root); 
    traverse(root->left, pre, in, post);
    in(root);
    traverse(root->right, pre, in, post);
    post(root);
}

// This can be used as a template argument to denote "do nothing".
struct Nothing { void operator()(void*) {} } nothing;

// Usage example - print the nodes, pre-ordered
void print(Node<int>* node) {std::cout << node->data << " ";}
traverse(root, print, nothing, nothing);

// Usage example - find the sum of all the nodes
struct Accumulator
{
    Accumulator() : sum(0) {}
    void operator()(Node<int>* node) {sum += node->data;}
    int sum;
};

Accumulator a;
traverse(root, a, nothing, nothing);
std::cout << a.sum << std::endl;

这取决于您真正想用它做什么——也可能重构它以模板化顺序,或者分离三种遍历类型,您可能希望将其转换为内部迭代,允许任何东西访问树中的数据:

enum order_t { PREORDER, INORDER, POSTORDER };

template<typename T, order_t order, typename F>
void traverse_binary_tree(BinaryTreeNode<T>* root, F f)
{
    if( root == NULL ) return;

    if(order == PREORDER) f(root->data);

    traverse_binary_tree<T,order>(root->left,f);

    if(order == INORDER) f(root->data);

    traverse_binary_tree<T,order>(root->right,f);

    if(order == POSTORDER) f(root->data);
}

template<typename T, typename F>
void traverse_binary_tree(BinaryTreeNode<T>* root, F f, order_t order = PREORDER)
{
    switch (order) {
    case PREORDER:
    traverse_binary_tree<T,PREORDER>(root,f);
    break;

    case POSTORDER:
    traverse_binary_tree<T,POSTORDER>(root,f);
    break;

    case INORDER:
    traverse_binary_tree<T,INORDER>(root,f);
    break;
    }
}

(您可能还需要const f&和f&versions,而不是简单的复制pass-by-value函数参数,它允许您传入可变的函数并产生结果;只要函数没有成员变量或构造函数,by-value就可以了)

或者您可以创建代表三个遍历的迭代器,允许您使用std::copy编写输出;但是,这将是更多的代码,并且不会仅仅为了这个目的而这样做。但是,创建迭代器将允许在不发生堆栈溢出的情况下处理大型树,因为您必须在每个节点中都有一个“父”指针,或者让迭代器维护一个访问节点的显式堆栈。

虽然函数本身变得非常简单:

std::ostream_iterator<std::string>(std::cout, " ");
std::copy(d.begin(order), d.end(), out);

使用迭代器并不能简化实现,无论是在loc方面,还是实际上能够跟踪正在发生的事情:

#include<string>
#include<iostream>
#include<functional>
#include<algorithm>
#include<iterator>
#include<vector>
#include<stack>

enum order_t { PREORDER, INORDER, POSTORDER };

template <typename T>

class BinaryTreeNode {
public:
    BinaryTreeNode(const T& data) : data(data), left(0), right(0) { }
    BinaryTreeNode(const T& data, BinaryTreeNode<T>* left, BinaryTreeNode<T>* right) : data(data), left(left), right(right) { }
public:
    BinaryTreeNode<T>* left;
    BinaryTreeNode<T>* right;
    T data;

    class BinaryTreeIterator {
        BinaryTreeNode <T>* current;
        std::stack<BinaryTreeNode <T>*> stack;
        order_t order;
        bool descending;
    public:
        typedef T value_type;
        typedef std::input_iterator_tag iterator_category;
        typedef void difference_type;
        typedef BinaryTreeIterator* pointer;
        typedef BinaryTreeIterator& reference;

        BinaryTreeIterator (BinaryTreeNode <T>* current, order_t order) : current(current), order(order), descending(true)
        {
            if (order != PREORDER) 
                descend();
        }

        BinaryTreeIterator () : current(0), order(PREORDER), descending(false)
        {
        }

    private:
        void descend() {
            do {
                if (current->left) {
                    stack.push(current);
                    current = current -> left;
                    descending = true;
                } else if ((order!=INORDER) && current->right) {
                    stack.push(current);
                    current = current -> right;
                    descending = true;
                } else {
                    descending = false; 
                    break;
                }
            } while (order != PREORDER);
        }

    public:
        bool operator== (const BinaryTreeIterator& other) { 
            if (current)
                return current == other.current && order == other.order; 
            else
                return other.current == 0;
        }

        bool operator!= (const BinaryTreeIterator& other) { 
            return !((*this)==other);
        }

        const T& operator * () const {
            return current -> data;
        }

        BinaryTreeIterator& operator++ () {
            // if the stack is empty, then go to the left then right
            // if the descending flag is set, then try to descending first
            if (descending) 
                descend();

            // not descending - either there are no children, or we are already going up
            // if the stack is not empty, then this node's parent is the top of the stack
            // so go right if this is the left child, and up if this is the right child
            if (!descending) {
                do {
                    if (stack.size()) {
                        BinaryTreeNode <T>* parent = stack.top();

                        // for inorder traversal, return the parent if coming from the left
                        if ((order == INORDER) && (current == parent->left)) {
                            current = parent;
                            break;
                        }

                        // if this is the left child and there is a right child, descending into the right
                        // or if this is the parent (inorder) 
                        if ((current == parent) && (parent -> right)) {
                            current = parent->right;
                            descend();

                            // simulate return from descent into left if only the right child exists
                            if ((current->left == 0)&&(current->right))
                                stack.push(current);

                            break;
                        }

                        // if this is the left child and there is a right child, descending into the right
                        if ((current == parent->left) && (parent -> right)) {
                            descending = true;
                            current = parent->right;

                            if (order != PREORDER)
                                descend();

                            break;
                        }

                        // either has come up from the right, or there is no right, so go up
                        stack.pop();

                        current = parent;
                    } else {
                        // no more stack; quit
                        current = 0;
                        break;
                    }
                } while (order != POSTORDER);
            }

            return *this;
        }
    };

    BinaryTreeIterator begin(order_t order) { return BinaryTreeIterator(this, order); }
    BinaryTreeIterator end() { return BinaryTreeIterator(); }
};

int main () {
    typedef BinaryTreeNode<std::string> Node;

    std::ostream_iterator<std::string> out( std::cout, " " );

    Node a("a");    
    Node c("c");
    Node b("b", &a, &c);
    Node e("e");    
    Node h("h");    
    Node i("i", &h, 0);    
    Node g("g", 0, &i);
    Node f("f", &e, &g);
    Node d("d", &b, &f);

    std::copy(d.begin(INORDER), d.end(), out);
    std::cout << std::endl;

    std::copy(d.begin(PREORDER), d.end(), out);
    std::cout << std::endl;

    std::copy(d.begin(POSTORDER), d.end(), out);
    std::cout << std::endl;

    return 0;
}

我们可以“重新排序循环”

enum {post = 0x0101, in = 0x1001, pre = 0x1010};

template<typename T>
void traverse_binary_tree(BinaryTreeNode<T>* root,int order = pre)
{
    if( root == NULL ) return;

    if(order & 0x0001) traverse_binary_tree(root->left,order);
    if(order & 0x0100) traverse_binary_tree(root->right,order);

    cout << root->data << " ";

    if(order & 0x0010) traverse_binary_tree(root->left,order);
    if(order & 0x1000) traverse_binary_tree(root->right,order);

}

但这更多的是让它变得有趣而不是简单。:-)但是,代码在这里重复两次,而不是三次。

为了避免“神奇数字”,您可以这样写:

enum {
  left_before  = 1 << 0,
  left_after   = 1 << 1,
  right_before = 1 << 2,
  right_after  = 1 << 3,
};
int const pre  = left_after  | right_after ;
int const in   = left_before | right_after ;
int const post = left_before | right_before;

/* The function body is fixed in the same way */

我可能会这样做: 枚举TraversalOrder预订单、InOrder、PostOrder

template<typename T>
void traverse_binary_tree_preorder(BinaryTreeNode<T>* root)
{
    if( !root ) return;

    cout << root->data << " ";

    traverse_binary_tree_preorder(root->left,order);
    traverse_binary_tree_preorder(root->right,order);

}

template<typename T>
void traverse_binary_tree_inorder(BinaryTreeNode<T>* root)
{
    if( !root ) return;

    traverse_binary_tree_inorder(root->left,order);
    cout << root->data << " ";
    traverse_binary_tree_inorder(root->right,order);

}

template<typename T>
void traverse_binary_tree_postorder(BinaryTreeNode<T>* root)
{
    if( !root ) return;


    traverse_binary_tree_postorder(root->left,order);
    traverse_binary_tree_postorder(root->right,order);
    cout << root->data << " ";

}


template<typename T>
void traverse_binary_tree(BinaryTreeNode<T>* root,TraversalOrder order = InOrder)
{
    switch(order)
    {
        case PreOrder:
            return traverse_binary_tree_preorder(root);
        case PostOrder:
            return traverse_binary_tree_postorder(root);
        default:
            return traverse_binary_tree_inorder(root);
    }
}

每个函数都是尽可能简单的,如果在编译时知道需要哪个函数,就可以调用所需的直接遍历函数。

你可以移动 order 模板参数。

template<typename T, int order> // 0:pre, 1:in , 2:post
void traverse_binary_tree(BinaryTreeNode<T>* root)
{
    if( root == NULL ) return;    

    if(order == 0) cout << root->data << " ";    

    traverse_binary_tree<T,order> (root->left);    

    if(order == 1) cout << root->data << " ";    

    traverse_binary_tree<T,order> (root->right);    

    if(order == 2) cout << root->data << " ";    
}

每两个 if(order == 将在函数的每个实例化中编译。

@你将处于一个功能专业化的角落,见 https://stackoverflow.com/search?q=function+partial+specialization

测试顺序不高效也不优雅,您应该将遍历二进制树委托给只做一项工作的模板类。(通过专门化)该模板类还应作为成员a binarytreenode*启动递归算法。

有更好的方法写这个吗 功能?

如果它不是一个平衡的二叉树,那么它可能容易发生堆栈溢出。迭代地编写它可以避免这种情况。然而,这可能不是你想要的,因为我怀疑这是一个递归的学术练习。如果这是一个真实的项目,您可能会被问到,当有效集和关联容器已经存在时,为什么要实现二叉树。

您可以这样重写函数,使其与单入口、单出口(尝试保持您的风格)一致:

template<typename T>
void traverse_binary_tree(BinaryTreeNode<T>* root,int order = 0)// 0:pre, 1:in , 2:post
{
    if( root != NULL )
    {
        if(order == 0) cout << root->data << " ";

        traverse_binary_tree(root->left,order);

        if(order == 1) cout << root->data << " ";

        traverse_binary_tree(root->right,order);

        if(order == 2) cout << root->data << " ";
    }
}

一些人可能会发现这更好,但其他人不会(SESE由于异常处理在大多数项目中实际上无法实施)。

如果您真的想超越(仍然是为了学术目的),您可以实现树迭代器,它执行预先排序、顺序排序和后顺序遍历。这将在不使用递归的情况下遍历树,并允许您将树遍历详细信息与输出节点分离。这当然不是一个微不足道的任务,特别是在C++中,它没有语言水平相当于生成器/协同程序。

您还可以避免将幻数(0、1、2)用于顺序前遍历、顺序后遍历,而改用命名常量。

我把它写成三个独立的函数。这不是在编写代码方面的简化,而是在阅读和理解方面的简化。您不必每次都查看文档来记住 int 是哪种遍历。(当然,这可以通过使用枚举来纠正。)

在不使用任何模板magick的情况下分离if开关还有一个可忽略的速度优势。保持简单。