一般树的过帐顺序遍历

问题描述 投票:1回答:3

我目前是一名学生,他的任务涉及将二进制树方法应用于通用树方法。我唯一的问题是,我的帖子顺序遍历以下一般树是否正确?如果是这样,那么我知道我的算法正在运行,我只是无法正确处理邮政订单遍历的问题,我觉得并认为该网站可以提供帮助。

                     B
--------------------|------------------
|                   |                 |
A             ------D-----         ---I---
             |      |    |        |       |
             C      E    G        H       L
                         |
                         F

我的结果是:A C E F G D H L I B

java tree binary-tree tree-traversal postorder
3个回答
3
投票

你的回答对我来说是正确的。

这个技巧适用于广义树,而不仅仅是二元树。

http://en.wikipedia.org/wiki/Tree_traversal

来自http://www.brpreiss.com/books/opus4/html/page259.html

postorder遍历访问根最后。要对一般树进行后序遍历:

后序是否按照给定的顺序逐个遍历根的每个子树;然后访问root。


1
投票

感谢你在本文中写过的图表,但它让我感到困惑,因为它不是典型的二叉树。 (有些节点有3个孩子。)

无论如何,看起来很好。

作为维基对后序(http://en.wikipedia.org/wiki/Tree_traversal#Post-order)的定义,这是正确的。

后序

1.浏览左子树。

2.遍历正确的子树。

  1. 访问root。

0
投票

可以使用递归来完成后序打印。你可以从下面的递归函数想象自己。返回print()函数上方的两个函数后,将打印节点。尝试在纸上手动分析您的树上的树,您可以找到结果是正确的。最初可视化这样的递归函数会很困难,但你应该能够想象成为优秀的程序员,无论如何都要试一试。

void postorder(node)
{
   if(node=NULL)
      return;
   postorder(node.left);
   postorder(node.right);
   print(node);
}
© www.soinside.com 2019 - 2024. All rights reserved.