Mixing
How can i make tree to 2D arrays
I am trying to make tree data structure to 2D array.
I am trying to do it with for loop like this.
childs() function return child nodes array.
void makeArray(a 1_level_a)
{
for(2_level_a : 1_level_a.childs())
{
for(3_level_a : 2_level_a.childs())
{
}
}
}
How can i do it? any suggestion?
algorithm tree
asked Nov 22 '18 at 3:12
Knowledge DrillingKnowledge Drilling
3441414
add a comment |
I am trying to make tree data structure to 2D array.
I am trying to do it with for loop like this.
childs() function return child nodes array.
void makeArray(a 1_level_a)
{
for(2_level_a : 1_level_a.childs())
{
for(3_level_a : 2_level_a.childs())
{
}
}
}
How can i do it? any suggestion?
algorithm tree
asked Nov 22 '18 at 3:12
Knowledge DrillingKnowledge Drilling
3441414
add a comment |
I am trying to make tree data structure to 2D array.
I am trying to do it with for loop like this.
childs() function return child nodes array.
void makeArray(a 1_level_a)
{
for(2_level_a : 1_level_a.childs())
{
for(3_level_a : 2_level_a.childs())
{
}
}
}
How can i do it? any suggestion?
algorithm tree
asked Nov 22 '18 at 3:12
Knowledge DrillingKnowledge Drilling
3441414
I am trying to make tree data structure to 2D array.
I am trying to do it with for loop like this.
childs() function return child nodes array.
void makeArray(a 1_level_a)
{
for(2_level_a : 1_level_a.childs())
{
for(3_level_a : 2_level_a.childs())
{
}
}
}
How can i do it? any suggestion?
algorithm tree
algorithm tree
asked Nov 22 '18 at 3:12
Knowledge DrillingKnowledge Drilling
3441414
asked Nov 22 '18 at 3:12
Knowledge DrillingKnowledge Drilling
3441414
edited Nov 22 '18 at 3:21
Knowledge Drilling
asked Nov 22 '18 at 3:12
Knowledge DrillingKnowledge Drilling
3441414
asked Nov 22 '18 at 3:12
Knowledge DrillingKnowledge Drilling
3441414
asked Nov 22 '18 at 3:12
Knowledge DrillingKnowledge Drilling
3441414
3441414
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
This is a ready-to-run solution that modifies the standard BFS a little and has been tested with multiple levels. The algorithm shifts the previous rows every time multiple children are added from the current node. Also, it keeps track of the total shift when iterating through a particular level to know where to insert blank cells which bubble up from the children. Finally it propagates down placeholder blank nodes for the case when it hits a leaf before the final level of the tree. When our queue is filled only with these dummy nodes we know we can stop.
class Node:
def __init__(self, val):
self.val = val
self.children =
def add_children(self, children):
self.children = children
a = Node("a")
a1 = Node("a1")
a2 = Node("a2")
a3 = Node("a3")
a11 = Node("a11")
a12 = Node("a12")
a31 = Node("a31")
a.add_children([a1, a2, a3])
a2.add_children([a11, a12])
a3.add_children([b1, b2, b3])
a12.add_children([b4])
b2.add_children([b5, b6])
arr = [[a.val]]
queue = [a]
to_process = 1
processed = 0
shifted = 0
while not all(e.val == "" for e in queue):
node = queue[0]
processed+=1
children = node.children if len(node.children) > 0 else [Node("")]
if(to_process==processed):
arr.append(list(map(lambda x: x.val, children)))
to_process = len(queue)
queue+=children
processed = 0
shifted = 0
else:
arr[-1] += list(map(lambda x: x.val, children))
queue += children
queue = queue[1:]
for i in range(0, len(arr)-1):
arr[i] = arr[i][0:shifted+1] + [""] * (len(children)-1) + arr[i][shifted+1:]
shifted += len(children)
print("arr: " + str(arr[:-1]))
answered Nov 22 '18 at 6:08
Lucas Kot-ZaniewskiLucas Kot-Zaniewski
1,077911
add a comment |
You can write the array row-per-row. The following code assumes that trees only have depth 3:
array[0][0] = 1_level_a;
int last_index = 0;
for (2_level_a : 1_level_a.childs()) {
array[1][last_index] = 2_level_a;
for (3_level_a : 2_level_a.childs()) {
array[2][last_index] = 3_level_a;
last_index++;
}
if (2_level_a.childs().size() == 0) {
last_index++;
}
}
If you need to handle trees of larger depth, you can use recursion:
int writeTree(node, depth, last_index) {
array[depth][last_index] = node;
for (child : node.childs()) {
last_index = writeTree(child, depth + 1, last_index);
}
if (node.childs().size() == 0) {
last_index++;
}
return last_index;
}
writeTree(1_level_a, 0, 0);
Note that this is the same as the above algorithm, but the above algorithm assumes nodes of depth 3 have no children.
answered Nov 22 '18 at 4:43
Carl Joshua QuinesCarl Joshua Quines
334
I really like the recursive approach for this actually... good job. Starting with fixed size output array made for a more concise solution.
– Lucas Kot-Zaniewski
Nov 22 '18 at 7:08
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53423338%2fhow-can-i-make-tree-to-2d-arrays%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
This is a ready-to-run solution that modifies the standard BFS a little and has been tested with multiple levels. The algorithm shifts the previous rows every time multiple children are added from the current node. Also, it keeps track of the total shift when iterating through a particular level to know where to insert blank cells which bubble up from the children. Finally it propagates down placeholder blank nodes for the case when it hits a leaf before the final level of the tree. When our queue is filled only with these dummy nodes we know we can stop.
class Node:
def __init__(self, val):
self.val = val
self.children =
def add_children(self, children):
self.children = children
a = Node("a")
a1 = Node("a1")
a2 = Node("a2")
a3 = Node("a3")
a11 = Node("a11")
a12 = Node("a12")
a31 = Node("a31")
a.add_children([a1, a2, a3])
a2.add_children([a11, a12])
a3.add_children([b1, b2, b3])
a12.add_children([b4])
b2.add_children([b5, b6])
arr = [[a.val]]
queue = [a]
to_process = 1
processed = 0
shifted = 0
while not all(e.val == "" for e in queue):
node = queue[0]
processed+=1
children = node.children if len(node.children) > 0 else [Node("")]
if(to_process==processed):
arr.append(list(map(lambda x: x.val, children)))
to_process = len(queue)
queue+=children
processed = 0
shifted = 0
else:
arr[-1] += list(map(lambda x: x.val, children))
queue += children
queue = queue[1:]
for i in range(0, len(arr)-1):
arr[i] = arr[i][0:shifted+1] + [""] * (len(children)-1) + arr[i][shifted+1:]
shifted += len(children)
print("arr: " + str(arr[:-1]))
answered Nov 22 '18 at 6:08
Lucas Kot-ZaniewskiLucas Kot-Zaniewski
1,077911
add a comment |
This is a ready-to-run solution that modifies the standard BFS a little and has been tested with multiple levels. The algorithm shifts the previous rows every time multiple children are added from the current node. Also, it keeps track of the total shift when iterating through a particular level to know where to insert blank cells which bubble up from the children. Finally it propagates down placeholder blank nodes for the case when it hits a leaf before the final level of the tree. When our queue is filled only with these dummy nodes we know we can stop.
class Node:
def __init__(self, val):
self.val = val
self.children =
def add_children(self, children):
self.children = children
a = Node("a")
a1 = Node("a1")
a2 = Node("a2")
a3 = Node("a3")
a11 = Node("a11")
a12 = Node("a12")
a31 = Node("a31")
a.add_children([a1, a2, a3])
a2.add_children([a11, a12])
a3.add_children([b1, b2, b3])
a12.add_children([b4])
b2.add_children([b5, b6])
arr = [[a.val]]
queue = [a]
to_process = 1
processed = 0
shifted = 0
while not all(e.val == "" for e in queue):
node = queue[0]
processed+=1
children = node.children if len(node.children) > 0 else [Node("")]
if(to_process==processed):
arr.append(list(map(lambda x: x.val, children)))
to_process = len(queue)
queue+=children
processed = 0
shifted = 0
else:
arr[-1] += list(map(lambda x: x.val, children))
queue += children
queue = queue[1:]
for i in range(0, len(arr)-1):
arr[i] = arr[i][0:shifted+1] + [""] * (len(children)-1) + arr[i][shifted+1:]
shifted += len(children)
print("arr: " + str(arr[:-1]))
answered Nov 22 '18 at 6:08
Lucas Kot-ZaniewskiLucas Kot-Zaniewski
1,077911
add a comment |
This is a ready-to-run solution that modifies the standard BFS a little and has been tested with multiple levels. The algorithm shifts the previous rows every time multiple children are added from the current node. Also, it keeps track of the total shift when iterating through a particular level to know where to insert blank cells which bubble up from the children. Finally it propagates down placeholder blank nodes for the case when it hits a leaf before the final level of the tree. When our queue is filled only with these dummy nodes we know we can stop.
class Node:
def __init__(self, val):
self.val = val
self.children =
def add_children(self, children):
self.children = children
a = Node("a")
a1 = Node("a1")
a2 = Node("a2")
a3 = Node("a3")
a11 = Node("a11")
a12 = Node("a12")
a31 = Node("a31")
a.add_children([a1, a2, a3])
a2.add_children([a11, a12])
a3.add_children([b1, b2, b3])
a12.add_children([b4])
b2.add_children([b5, b6])
arr = [[a.val]]
queue = [a]
to_process = 1
processed = 0
shifted = 0
while not all(e.val == "" for e in queue):
node = queue[0]
processed+=1
children = node.children if len(node.children) > 0 else [Node("")]
if(to_process==processed):
arr.append(list(map(lambda x: x.val, children)))
to_process = len(queue)
queue+=children
processed = 0
shifted = 0
else:
arr[-1] += list(map(lambda x: x.val, children))
queue += children
queue = queue[1:]
for i in range(0, len(arr)-1):
arr[i] = arr[i][0:shifted+1] + [""] * (len(children)-1) + arr[i][shifted+1:]
shifted += len(children)
print("arr: " + str(arr[:-1]))
answered Nov 22 '18 at 6:08
Lucas Kot-ZaniewskiLucas Kot-Zaniewski
1,077911
This is a ready-to-run solution that modifies the standard BFS a little and has been tested with multiple levels. The algorithm shifts the previous rows every time multiple children are added from the current node. Also, it keeps track of the total shift when iterating through a particular level to know where to insert blank cells which bubble up from the children. Finally it propagates down placeholder blank nodes for the case when it hits a leaf before the final level of the tree. When our queue is filled only with these dummy nodes we know we can stop.
class Node:
def __init__(self, val):
self.val = val
self.children =
def add_children(self, children):
self.children = children
a = Node("a")
a1 = Node("a1")
a2 = Node("a2")
a3 = Node("a3")
a11 = Node("a11")
a12 = Node("a12")
a31 = Node("a31")
a.add_children([a1, a2, a3])
a2.add_children([a11, a12])
a3.add_children([b1, b2, b3])
a12.add_children([b4])
b2.add_children([b5, b6])
arr = [[a.val]]
queue = [a]
to_process = 1
processed = 0
shifted = 0
while not all(e.val == "" for e in queue):
node = queue[0]
processed+=1
children = node.children if len(node.children) > 0 else [Node("")]
if(to_process==processed):
arr.append(list(map(lambda x: x.val, children)))
to_process = len(queue)
queue+=children
processed = 0
shifted = 0
else:
arr[-1] += list(map(lambda x: x.val, children))
queue += children
queue = queue[1:]
for i in range(0, len(arr)-1):
arr[i] = arr[i][0:shifted+1] + [""] * (len(children)-1) + arr[i][shifted+1:]
shifted += len(children)
print("arr: " + str(arr[:-1]))
answered Nov 22 '18 at 6:08
Lucas Kot-ZaniewskiLucas Kot-Zaniewski
1,077911
edited Nov 22 '18 at 6:28
answered Nov 22 '18 at 6:08
Lucas Kot-ZaniewskiLucas Kot-Zaniewski
1,077911
answered Nov 22 '18 at 6:08
Lucas Kot-ZaniewskiLucas Kot-Zaniewski
1,077911
answered Nov 22 '18 at 6:08
Lucas Kot-ZaniewskiLucas Kot-Zaniewski
1,077911
1,077911
add a comment |
add a comment |
You can write the array row-per-row. The following code assumes that trees only have depth 3:
array[0][0] = 1_level_a;
int last_index = 0;
for (2_level_a : 1_level_a.childs()) {
array[1][last_index] = 2_level_a;
for (3_level_a : 2_level_a.childs()) {
array[2][last_index] = 3_level_a;
last_index++;
}
if (2_level_a.childs().size() == 0) {
last_index++;
}
}
If you need to handle trees of larger depth, you can use recursion:
int writeTree(node, depth, last_index) {
array[depth][last_index] = node;
for (child : node.childs()) {
last_index = writeTree(child, depth + 1, last_index);
}
if (node.childs().size() == 0) {
last_index++;
}
return last_index;
}
writeTree(1_level_a, 0, 0);
Note that this is the same as the above algorithm, but the above algorithm assumes nodes of depth 3 have no children.
answered Nov 22 '18 at 4:43
Carl Joshua QuinesCarl Joshua Quines
334
I really like the recursive approach for this actually... good job. Starting with fixed size output array made for a more concise solution.
– Lucas Kot-Zaniewski
Nov 22 '18 at 7:08
add a comment |
You can write the array row-per-row. The following code assumes that trees only have depth 3:
array[0][0] = 1_level_a;
int last_index = 0;
for (2_level_a : 1_level_a.childs()) {
array[1][last_index] = 2_level_a;
for (3_level_a : 2_level_a.childs()) {
array[2][last_index] = 3_level_a;
last_index++;
}
if (2_level_a.childs().size() == 0) {
last_index++;
}
}
If you need to handle trees of larger depth, you can use recursion:
int writeTree(node, depth, last_index) {
array[depth][last_index] = node;
for (child : node.childs()) {
last_index = writeTree(child, depth + 1, last_index);
}
if (node.childs().size() == 0) {
last_index++;
}
return last_index;
}
writeTree(1_level_a, 0, 0);
Note that this is the same as the above algorithm, but the above algorithm assumes nodes of depth 3 have no children.
answered Nov 22 '18 at 4:43
Carl Joshua QuinesCarl Joshua Quines
334
I really like the recursive approach for this actually... good job. Starting with fixed size output array made for a more concise solution.
– Lucas Kot-Zaniewski
Nov 22 '18 at 7:08
add a comment |
You can write the array row-per-row. The following code assumes that trees only have depth 3:
array[0][0] = 1_level_a;
int last_index = 0;
for (2_level_a : 1_level_a.childs()) {
array[1][last_index] = 2_level_a;
for (3_level_a : 2_level_a.childs()) {
array[2][last_index] = 3_level_a;
last_index++;
}
if (2_level_a.childs().size() == 0) {
last_index++;
}
}
If you need to handle trees of larger depth, you can use recursion:
int writeTree(node, depth, last_index) {
array[depth][last_index] = node;
for (child : node.childs()) {
last_index = writeTree(child, depth + 1, last_index);
}
if (node.childs().size() == 0) {
last_index++;
}
return last_index;
}
writeTree(1_level_a, 0, 0);
Note that this is the same as the above algorithm, but the above algorithm assumes nodes of depth 3 have no children.
answered Nov 22 '18 at 4:43
Carl Joshua QuinesCarl Joshua Quines
334
You can write the array row-per-row. The following code assumes that trees only have depth 3:
array[0][0] = 1_level_a;
int last_index = 0;
for (2_level_a : 1_level_a.childs()) {
array[1][last_index] = 2_level_a;
for (3_level_a : 2_level_a.childs()) {
array[2][last_index] = 3_level_a;
last_index++;
}
if (2_level_a.childs().size() == 0) {
last_index++;
}
}
If you need to handle trees of larger depth, you can use recursion:
int writeTree(node, depth, last_index) {
array[depth][last_index] = node;
for (child : node.childs()) {
last_index = writeTree(child, depth + 1, last_index);
}
if (node.childs().size() == 0) {
last_index++;
}
return last_index;
}
writeTree(1_level_a, 0, 0);
Note that this is the same as the above algorithm, but the above algorithm assumes nodes of depth 3 have no children.
answered Nov 22 '18 at 4:43
Carl Joshua QuinesCarl Joshua Quines
334
answered Nov 22 '18 at 4:43
Carl Joshua QuinesCarl Joshua Quines
334
answered Nov 22 '18 at 4:43
Carl Joshua QuinesCarl Joshua Quines
334
answered Nov 22 '18 at 4:43
Carl Joshua QuinesCarl Joshua Quines
334
334
I really like the recursive approach for this actually... good job. Starting with fixed size output array made for a more concise solution.
– Lucas Kot-Zaniewski
Nov 22 '18 at 7:08
add a comment |
I really like the recursive approach for this actually... good job. Starting with fixed size output array made for a more concise solution.
– Lucas Kot-Zaniewski
Nov 22 '18 at 7:08
I really like the recursive approach for this actually... good job. Starting with fixed size output array made for a more concise solution.
– Lucas Kot-Zaniewski
Nov 22 '18 at 7:08
I really like the recursive approach for this actually... good job. Starting with fixed size output array made for a more concise solution.
– Lucas Kot-Zaniewski
Nov 22 '18 at 7:08
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53423338%2fhow-can-i-make-tree-to-2d-arrays%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
