javascript - Recurse through tree to create a list of breadcrumbs - Stack Overflow

admin管理员组

文章数量:1389762

I have a tree of data and am trying to create a recursive function to add each path in the tree as an array of strings to better understand recursion. I am not sure why my method is not producing the expect

var tree = {
	"name": "home",
	"children": [
		{
			"name": "cars",
			"children": [
				{
					"name": "ford",
					"children": [
						{
							"name": "mustang"
						},
						{
							"name": "explorer"
						}
					]
				}
			]
		},
		{
			"name": "food",
			"children": [
				{
					"name": "pizza"
				}
			]
		}
	]
};

var list = [];
var path = [];

function traverse(node) {
    if (node.name) { 
        path.push(node.name) 
    }
    
    if (!node.children) { 
        if (path.length) {
            list.push(path);
        }
        return; 
    } else {
     node.children.forEach(function(item) {
       traverse(item); 
     });  
    }
}

traverse(tree);
console.log(list);

I have a tree of data and am trying to create a recursive function to add each path in the tree as an array of strings to better understand recursion. I am not sure why my method is not producing the expect

var tree = {
	"name": "home",
	"children": [
		{
			"name": "cars",
			"children": [
				{
					"name": "ford",
					"children": [
						{
							"name": "mustang"
						},
						{
							"name": "explorer"
						}
					]
				}
			]
		},
		{
			"name": "food",
			"children": [
				{
					"name": "pizza"
				}
			]
		}
	]
};

var list = [];
var path = [];

function traverse(node) {
    if (node.name) { 
        path.push(node.name) 
    }
    
    if (!node.children) { 
        if (path.length) {
            list.push(path);
        }
        return; 
    } else {
     node.children.forEach(function(item) {
       traverse(item); 
     });  
    }
}

traverse(tree);
console.log(list);

The output I am looking to create is:

[
    ["home"],
    ["home", "cars"],
    ["home", "cars", "ford"],
    ["home", "cars", "ford", "mustang"],
    ["home", "cars", "ford", "explorer"],
    ["home", "food"],
    ["home", "food", "pizza"]
]

• javascript
• recursion

Share Improve this question Follow asked Nov 5, 2015 at 17:22 MddMdd 4,4501212 gold badges4848 silver badges7171 bronze badges 1

• Well for one thing you are storing the path variable outside the recursive function and never resetting its value. – thatidiotguy Commented Nov 5, 2015 at 17:27

Add a ment  | 

2 Answers 2

Sorted by: Reset to default 5

You modify the same path array in all iterations. You should copy it instead:

var list = [];
function traverse(node, path) {
  if ( !path )
    path = [];
  if (node.name) {
    path.push(node.name)
  }
  list.push(path);
  if (node.children) {
    node.children.forEach(function(item) {
      traverse(item, path.slice());
    });
  }
}
traverse(tree, []);

I have corrected your code, this solution copies the path variable from one function call to the other:

var tree = {
  "name": "home",
  "children": [{
    "name": "cars",
    "children": [{
      "name": "ford",
      "children": [{
        "name": "mustang"
      }, {
        "name": "explorer"
      }]
    }]
  }, {
    "name": "food",
    "children": [{
      "name": "pizza"
    }]
  }]
};

var path = [];

var list = [];
function traverse(node, path) {
  if ( !path )
    path = [];
  if (node.name) {
    path.push(node.name)
  }
  list.push(path);
  if (node.children) {
    node.children.forEach(function(item) {
      traverse(item, path.slice());
    });
  }
  document.write(JSON.stringify(path )+ '<br>')
}
traverse(tree, []);

本文标签： javascriptRecurse through tree to create a list of breadcrumbsStack Overflow