java – 从特定叶子开始的自下而上树遍历

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java – 从特定叶子开始的自下而上树遍历，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1111字，纯文字阅读大概需要2分钟。

内容图文

我正在寻找一种从下到上遍历树的方法,以便我可以从我选择的特定叶子开始,然后继续到根.

预期输出：在链接sample tree中的样本树图像(取自here)中,如果我指定从Y开始,算法将返回YXZWVUT.

对此我有任何帮助,我将不胜感激.

解决方法:

如果我正确地理解了这个问题,那就是问题陈述

遍历n-ary树,从叶节点开始直到根节点,这样在遍历所有子节点之前不会遍历任何节点.遍历的第一个节点将始终是叶节点,遍历的最后一个节点将始终是根节点.

这可以通过使用两个递归函数来解决,TraverseUp()是调用自身的主函数和另一个调用自身的递归函数PostOrderTraversal().数组A需要通过引用传递,并包含最终遍历的列表.这是一些伪代码：

TraverseUp(Array *A, Node *n) {
  // Add n to A to maintain bottom up nature
  if (!n) return;
  A.add(n)

  // Go to parent
  Node *p = n.parent();
  if (!p) return;

  // For each child of p other than n, do a post order traversal
  foreach(Node *c in p.children) {
    if (c == n) continue;
    PostOrderTraversal(A, c);
  }
  // When done with adding all p's children, continue traversing up
  TraverseUp(A, p);
}

// Standard implementation of post order traversal
PostOrderTraversal(Array *A, Node *n) {
  if (!n) return;
  foreach(Node *c in n.children) {
    PostOrderTraversal(A, c);
    A.add(c);
  }
}

内容总结

以上是互联网集市为您收集整理的java – 从特定叶子开始的自下而上树遍历全部内容，希望文章能够帮你解决java – 从特定叶子开始的自下而上树遍历所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端