邮购遍历普通 javascript

Question

我想在我必须穿过一棵树并得到结果的任务中寻求帮助：

 [ 4, 2, 5, 7, 6, 3, 1 ]

class:

class Traversal {
  postOrderTraversal(tree) {
    // ...code here
  }
}

我的 object :

const tree = {
  value: 1,
  children: [
    {
      value: 2,
      children: [
        { 
          value: 4,
          children: [] 
        }
      ],
    },
    {
      value: 3,
      children: [
        {
          value: 5,
          children: [],
        },
        {
          value: 6,
          children: [
            {
              value: 7,
              children: [],
            },
          ],
        },
      ],
    },
  ],
};

示例说明（我们每个节点最多有两个children）：

                          +----------------+
                          |     value:   1 |
                          +----------------+
                            /            \
                           /              \
            +----------------+        +----------------+
            |     value:   2 |        |     value:   3 |
            +----------------+        +----------------+
               /                         /           \
              /                         /             \
 +----------------+       +----------------+       +----------------+
 |     value:   4 |       |     value:   5 |       |     value:   6 |
 +----------------+       +----------------+       +----------------+
                                                        /
                                                       /
                                         +----------------+
                                         |     value:   7 |
                                         +----------------+

如果有人可以帮助解决这个问题，请使用简单的 javascript 以便我更好地理解它。

Answer 1

这可能是我能想到的最简单的实现。仅给出两行代码，几乎没有解释的余地-

function *postorder(t) {
  for (child of t.children) yield *postorder(child)
  yield t.value
}

const mytree = {value:1,children:[{value:2,children:[{value:4,children:[]}]},{value:3,children:[{value:5,children:[]},{value:6,children:[{value:7,children:[]}]}]}]}

console.log(Array.from(postorder(mytree)))

[4,2,5,7,6,3,1]

与类混淆遍历虽然可能，但对您没有任何好处。 postorder保持不变-

function *postorder(t) {
  for (child of t.children) yield *postorder(child)
  yield t.value
}

class Traversal {
  postorder(t) { return Array.from(postorder(t)) }
}

const mytree = {value:1,children:[{value:2,children:[{value:4,children:[]}]},{value:3,children:[{value:5,children:[]},{value:6,children:[{value:7,children:[]}]}]}]}

const q = new Traversal()

console.log(q.postorder(mytree))

与preorder比较。实现这种遍历唯一需要做的改变就是调换两行的顺序 -

function *preorder(t) {
  yield t.value
  for (child of t.children) yield *preorder(child)
}

const mytree = {value:1,children:[{value:2,children:[{value:4,children:[]}]},{value:3,children:[{value:5,children:[]},{value:6,children:[{value:7,children:[]}]}]}]}

console.log(Array.from(preorder(mytree)))

[1,2,4,3,5,6,7]

Answer 2

与这些树访问算法的情况一样，最好的选择在于递归：树中的每个节点都应该 return 在其子节点的值之后有自己的值。肯定有比我在下面写的更短和更有效的方法来做到这一点，但我以这样一种方式构建代码，使得递归何时终止（当前节点没有子节点）以及值的顺序很清楚被添加到 returned 数组以便于理解。

function postOrderTraversal(node) {
  if (node.children.length === 0) {
    return [node.value];
  } else {
    var arr = [];
    for (var i = 0; i < node.children.length; i++) {
      var childValues = postOrderTraversal(node.children[i]);
      arr = arr.concat(childValues);
    }
    arr.push(node.value);
    return arr;
  }
}

Answer 3

我认为使用递归很好地演示了 post 顺序是如何工作的。我发现这是一个相对简单的解决方案。

class Traversal {
    postOrderTraversal(tree, arr=[]) {
        if(tree) {
            this.postOrderTraversal(tree.children[0], arr);
            this.postOrderTraversal(tree.children[1], arr);
            arr.push(tree.value);
        }

        return arr;
    }
}

由于你的数据集是一棵树，我假设children[0]被认为是左节点，children[1]被认为是右节点。

邮购遍历普通 javascript

postorder traversal plain javascript

javascript

javascript-objects

tree-traversal

postorder