C++ :: How To Linearize A Complex Non-uniform Tree

I have a tree structure that works likes this.

Each node (if its a 'normal' node) can have 2, 3 or 4 children. I know how to linearize a normal quadtree though it is not memory efficient in this case as the linearization only works for full trees. I'm okay with holes though.

But my tree is slightly odd in that it has non-normal nodes. For example, two leaves will point to a 'dead' node and that dead node has 3 children. Sometimes, 3 leaves will point to a dead node and that dead node will have 2 children. Sometimes, 4 leaves will point to a dead node and that dead node will have 4 children.

So normally, a node will only have one parent and multiple children or it'll just be a leaf. But there are dead nodes that can have 2, 3, or 4 parents and will subsequently have 3, 2 or 4 children respectively.

This is for point location within a Delaunay triangulation and operates off of the idea of volume spanning.

What I abstracted in my code is a 2-to-3, 3-to-2 and 4-to-4 flip. The idea is ,we take 2 tetrahedra and replace them with 3 good tetrahedra but they span the same volume which is good for point location.

As of now, the code that I have works fine. It triangulates tetrahedra and repairs them accordingly but for certain inserts, the search algorithm takes incredibly long and I'm trying to fix that.

I figured a linear structure would be a good attempt so how to linearize a tree that behaves almost polymorphically.