All geek questions in one place

How can I simplify this binary tree traversal function?

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

    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 << " ";

}

Is there a better way to write this function?

+3
source share
9 answers

No.

jokes. I think it looks pretty effective.

I would list the order values ​​for readability.

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

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

"Simple" is a matter of opinion. Besides some stylistic questions (in particular, using magic numbers rather than nominal constants), it is about as simple as you can get, given the speculation "cross the tree and print its contents, providing a choice of order."

, : . , , . , , :

// 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;
+4

, , - , , , , - :

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;
    }
}

( F & F &, , , , ; - )

, , std:: copy; . , "" node, .

:

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 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;
}
+3

" "

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 */
+2

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 == .

+1

, , - :   enum TraversalOrder {PreOrder, 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);
    }
}

, , , , , , .

+1

@Vi, , . https://stackoverflow.com/search?q=function+partial+specialization

, traverse_binary_tree , . ( ) BinaryTreeNode * .

0

?

, . . , , , , , . , , , , , .

, ( ):

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 - ).

( ), , , . . , , , ++, / .

(0, 1, 2) , .

0

. , . , , int - - . ( , .)

if - . .

0

Source: https://habr.com/ru/post/1752615/

More articles:


All Articles