Convert k-ary tree to Left Child Right Sibling (LCRS) Tree

Convert an arbitrary k-ary tree to a LCRS tree

source: https://en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree

Let us see one example. Consider the following multiway tree

                  1           
                 /|\          
                / | \         
               /  |  \        
              2   3   4       
             / \      |       
            5   6     7       
                     / \      
                    8   9     

This tree can be represented in first child-next sibling manner as follows

                  1           
                 /            
                /             
               /              
              2---3---4       
             /       /        
            5---6   7         
                   /          
                  8---9       

Now, if we look at the first child-next sibling representation of the tree closely, we will see that it forms a binary tree. To see this better, we can rotate every next-sibling edge 45 degrees clockwise. After that we get the following binary tree:

                1             
               /              
              2               
             / \              
            5   3             
             \   \            
              6   4           
                 /            
                7             
               /              
              8               
               \              
                9             

This is binary tree representation of the given (multiway) tree.

Pseudocode

Given an arbitrary k-ary tree

1. Compute the depth of each node. (init_multiwayTree.m)

2.Convert to a LCRS tree  (convert_multiwayTree_to_lcrsTree.m)

 2.1 Compute depth-index list

 2.2 Loop over depth

   if the current node's parent does not have a child:

      add the current node to the parent

   otherwise (If the parent already has a child):

      add the current node to the parent's child's sibling

main.m

ccc

% Given,

%                   1           

%                  /|\          

%                 / | \         

%                /  |  \        

%               2   3   4       

%              / \      |       

%             5   6     7       

%                      / \      

%                     8   9     

% to: 

%                 1             

%                /              

%               2               

%              / \              

%             5   3             

%              \   \            

%               6   4           

%                  /            

%                 7             

%                /              

%               8               

%                \              

%                 9             

%  

 

% Initialize basic nodes 

node(1) = struct('parent',0,'childs',[2,3,4],'lcrsChild',0,'lcrsSibling',0);

node(2) = struct('parent',1,'childs',[5,6],'lcrsChild',0,'lcrsSibling',0);

node(3) = struct('parent',1,'childs',[],'lcrsChild',0,'lcrsSibling',0);

node(4) = struct('parent',1,'childs',[7],'lcrsChild',0,'lcrsSibling',0);

node(5) = struct('parent',2,'childs',[],'lcrsChild',0,'lcrsSibling',0);

node(6) = struct('parent',2,'childs',[],'lcrsChild',0,'lcrsSibling',0);

node(7) = struct('parent',4,'childs',[8,9],'lcrsChild',0,'lcrsSibling',0);

node(8) = struct('parent',7,'childs',[],'lcrsChild',0,'lcrsSibling',0);

node(9) = struct('parent',7,'childs',[],'lcrsChild',0,'lcrsSibling',0);

 

% Initialize tree (depth,p)

node = init_multiwayTree(node);

 

% Convert to LCRS tree

node = convert_multiwayTree_to_lcrsTree(node);

 

% Print tree information

print_multiwayTree(node);

console out:

idx:[1]/[9] parent:[1] depth:[0] [LCRS] child:[2] sibling:[0] 

idx:[2]/[9] parent:[2] depth:[1] [LCRS] child:[5] sibling:[3] 

idx:[3]/[9] parent:[2] depth:[1] [LCRS] child:[0] sibling:[4] 

idx:[4]/[9] parent:[2] depth:[1] [LCRS] child:[7] sibling:[0] 

idx:[5]/[9] parent:[3] depth:[2] [LCRS] child:[0] sibling:[6] 

idx:[6]/[9] parent:[3] depth:[2] [LCRS] child:[0] sibling:[0] 

idx:[7]/[9] parent:[3] depth:[4] [LCRS] child:[8] sibling:[0] 

idx:[8]/[9] parent:[4] depth:[7] [LCRS] child:[0] sibling:[9] 

idx:[9]/[9] parent:[4] depth:[7] [LCRS] child:[0] sibling:[0]

init_multiwayTree.m

function node = init_multiwayTree(node,idx)

%

% Initialize an arbitrary multiway tree

%

% 1. Depth of each node 

% 

 

if nargin == 1

    idx = 1;

end

 

% Get current depth 

if idx == 1

    node(idx).depth = 1;

else

    parentIdx = node(idx).parent;

    node(idx).depth = node(parentIdx).depth + 1;

end

 

% Add positions

node(idx).p = zeros(1,3);

 

% Recursion

for i = node(idx).childs

    node = init_multiwayTree(node,i);

end

convert_multiwayTree_to_lcrsTree.m

function node = convert_multiwayTree_to_lcrsTree(node)

%

% Convert an arbitrary multiway tree to LCRS tree

%  (Left Child / Right Sibling)

%

 

% Initialize LCRS structure

for i = 1:length(node)

    node(i).lcrsChild = 0;

    node(i).lcrsSibling = 0;

end

 

% Compute depth-index list ('depth2idxList')

maxDepth = 0;

for i = 1:length(node) % compute max depth 

    if node(i).depth > maxDepth, maxDepth=node(i).depth; end

end

depth2idxList = cell(maxDepth,1);

for d = 1:maxDepth

    depth2idxList{d} = [];

end

for i = 1:length(node)

    d = node(i).depth;

    depth2idxList{d} = [depth2idxList{d}, i];

end

 

% Loop over depth

for d = 1:maxDepth % For each depth

    for i = depth2idxList{d} % For each index in current depth 

        if d == 1

            % Root node

        else

            % Other nodes

            % 1. Find parent's node

            parentIdx = node(i).parent;

            

            % Add current node to parent or sibling

            if node(parentIdx).lcrsChild == 0

                % If parent's child does not exist, add current node to parent

                node(parentIdx).lcrsChild = i;

            else

                % If parent already has child, add current node to parent's child's sibling

                childIdx = node(parentIdx).lcrsChild;

                node = add_sibling(node,childIdx,i); % <= Add! 

            end

        end

    end

end

 

function node = add_sibling(node,childIdx,idx)

%

% Add sibling to the node with recursion 

% 

if node(childIdx).lcrsSibling == 0

    node(childIdx).lcrsSibling = idx;

    return;

else

    % Recursive 

    node = add_sibling(node,node(childIdx).lcrsSibling,idx);

end

print_multiwayTree.m

 function print_multiwayTree(node,idx)

%

% Print an arbitrary multiway tree

%

 

USE_RECURSION = false; % Use recursion or not

 

if USE_RECURSION

    if nargin == 1

        idx = 1;

    end

    % Print out

    print_node(node,idx);

    

    % Recursion

    for i = node(idx).childs

        print_multiwayTree(node,i);

    end

else

    for idx = 1:length(node)

        print_node(node,idx);

    end

end

 

 

function print_node(node,idx)

fprintf('idx:[%d]/[%d] parent:[%d] depth:[%d] [LCRS] child:[%d] sibling:[%d] \n',...

    idx,length(node),node(idx).depth,node(idx).parent ,...

    node(idx).lcrsChild,node(idx).lcrsSibling);