postorder遍历普通javascript

Question

我想在一项任务中寻求帮助，在这一任务中，我必须穿过一棵树，然后得到它：

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

全班：

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

我的目标：

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

示例说明(每个节点最多有两个子节点)：

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

如果有人可以帮助这一点，请使用简单的javascript，以便我能更好地理解它。

Answer 1

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

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]被认为是正确的节点。

Answer 2

这可能是我能想到的最简单的实现。只要两行代码，就没有什么解释的余地了-

​

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 3

与这类访问树算法的情况一样，您最好的选择是递归:树中的每个节点都应该在其子节点的值之后返回自己的值。当然有比我下面所写的更短、更有效的方法来完成这个任务，但是我已经构造了代码，这样就可以清楚地知道递归何时终止(当前节点没有子节点)，并且为了便于理解，将值按顺序添加到返回的数组中。

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;
  }
}