Enginius/Matlab

# 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

% 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

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;

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;

end

end

end

end

%

% Add sibling to the node with recursion

%

return;

else

% Recursive

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

#### 'Enginius > Matlab' 카테고리의 다른 글

 Compute the distance from the cube and a point  (0) 2018.12.29 2018.09.07 2018.08.26 2018.06.30 2017.07.14 2017.03.01
• 강남 2018.09.16 21:12

잘보고 가요!!!

• hbnaramal 2020.11.19 23:52

유용한 내용 매우 잘 배우고 가여