CODEWITHSUNDEEP
c++binary-treesmart-pointerstraversal
Kfir Ettinger
Kfir Ettinger

Reputation: 632

Tree Traversals with smart pointers

I have implemented a simple binary tree class in C++. have using smart pointers objects to hold the pointers to each node (shared for children and weak for parent).

I was trying to implement a nested class for custom iterator (in-order, pre-order and post-order), but I couldn't figure out how to implement efficiently the .next() method. how can I get current position in traversal without holding the entire tree in a priority queue.

the tree nodes are a struct -

struct node : std::enable_shared_from_this
{
    T _val;
    std::weak_ptr<node> _parent;
    std::shared_ptr<node> _leftChild;
    std::shared_ptr<node> _rightChild;

    // CONSTRUCTORS
    node(T val): _val(val){}
    node(T val, weak_ptr<node> parent): _val(val), _parent(parent){}
};

Upvotes: 1

Views: 347

Answers (1)

Caleth
Caleth

Reputation: 63019

You need to know which child each node is, and from that you can derive the next node from the structure. You can do that with pointer equality

struct iter_base {
    std::shared_ptr<node> current;
    bool isRoot() const { return !current->_parent.lock(); }
    bool isLeft() const { auto parent = current->_parent.lock(); return parent && (current == parent->_leftChild); }
    bool isRight() const { auto parent = current->_parent.lock(); return parent && (current == parent->_rightChild); }
};

E.g. for inorder:

  • If you have a right child, follow that node's left descendants until there are no more, the last one is the next node.
  • Otherwise, if you are a left child, the next node is your parent.
  • Otherwise, if you are a right child, follow parent pointers until you find one that is a left child, and the next node is the parent of that left child. You've reached the end if you get to the root doing this.

Upvotes: 4

Related Questions