{"id":103307,"date":"2020-01-08T07:00:00","date_gmt":"2020-01-08T15:00:00","guid":{"rendered":"http:\/\/devblogs.microsoft.com\/oldnewthing\/?p=103307"},"modified":"2020-01-07T20:39:09","modified_gmt":"2020-01-08T04:39:09","slug":"20200108-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20200108-00\/?p=103307","title":{"rendered":"Tree-walking algorithms: Incrementally performing a postorder walk of an N-ary tree"},"content":{"rendered":"

We continue our exploration<\/a> of algorithms for walking incrementally through an N<\/var>-ary tree by perform a postorder walk through the tree.<\/p>\n

Recall that our goal is to follow the red arrows through the tree, as if we are walking along the outside of the tree with our left hand touching it.<\/p>\n\n\n\n\n\n\n\n\n
 <\/td>\n <\/td>\n <\/td>\n\u2199\ufe0e<\/td>\nA<\/td>\n\u2196\ufe0e<\/td>\n <\/td>\n <\/td>\n<\/tr>\n
 <\/td>\n <\/td>\n\u2199\ufe0e<\/td>\n\u2571<\/td>\n\u2502<\/td>\n\u2572<\/td>\n\u2196\ufe0e<\/td>\n <\/td>\n<\/tr>\n
 <\/td>\n\u2199\ufe0e<\/td>\nB<\/td>\n\u21b7<\/td>\nC<\/td>\n\u21b7<\/td>\nD<\/td>\n\u00a0\u2191<\/td>\n<\/tr>\n
\u2199\ufe0e<\/td>\n\u2571<\/td>\n\u21b7<\/td>\n\u2572\u2196\ufe0e<\/span><\/td>\n\u2192<\/td>\n\u2934\ufe0e\u2193\ufe0e<\/td>\n\u2502<\/td>\n\u00a0\u2191<\/td>\n<\/tr>\n
\u2193\ufe0e<\/td>\nE<\/td>\n\u2191\u2193<\/td>\nF<\/td>\n\u2196\ufe0e<\/td>\n\u2193\u00a0<\/td>\nG<\/td>\n\u00a0\u2191<\/td>\n<\/tr>\n
\u2937<\/td>\n\u2192<\/td>\n\u2934\ufe0e\u2937\ufe0e<\/td>\n\u2192<\/td>\n\u2934\ufe0e<\/td>\n\u2937<\/td>\n\u2192<\/td>\n\u2934\ufe0e<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

As with the preorder walk, we have two possible stopping places. We could stop at a leaf node (a node with no children), or we could stop at a parent node. However, the actions to take are the same in both cases, since we are always on the “upward path”.<\/p>\n

We have just finished enumerating a subtree, so we need to enumerate the next subtree, or move up to the parent if there are no more subtrees.<\/p>\n

Therefore, we first try to move to the next sibling. If that works, then treat that subtree as a new root by going deep to the first leaf node.<\/p>\n

If there is no next sibling, then we have finished processing all the children of a node, so move up to the parent node and enumerate it.<\/p>\n

class PostorderWalker\r\n{\r\n  private TreeCursor cursor;\r\n\r\n  public PostorderWalker(TreeNode node)\r\n  {\r\n    cursor = new TreeCursor(node);\r\n    GoDeep();\r\n  }\r\n\r\n  public bool MoveNext()\r\n  {\r\n    if (cursor.TryMoveToNextSiblingChild()) {\r\n      GoDeep();\r\n      return true;\r\n    }\r\n\r\n    if (cursor.TryMoveToParent()) {\r\n      return true;\r\n    }\r\n    return false;\r\n  }\r\n\r\n  public TreeNode Current => cursor.Current;\r\n\r\n  private void GoDeep()\r\n  {\r\n    while (cursor.TryMoveToFirstChild()) { }\r\n  }\r\n}\r\n<\/pre>\n
Next time, we’ll look at in-order enumeration.<\/p>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
This time, we report on the way back up.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-103307","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
This time, we report on the way back up.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/103307","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=103307"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/103307\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=103307"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=103307"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=103307"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}