2

我正在学习遍历二叉树的不同方法。我对此有几个问题。我见过这样的中序遍历伪代码（例如）：

 InOrder (a node N)
{
   if N is not empty
   {
     InOrder (N's left child)
     visit N
     InOrder (N's right child)
   }
}

“访问”节点是什么意思？这只是意味着打印出来吗？此外，算法如何跟踪它已经访问过的节点？它是否使用在广度优先遍历中使用的队列？

谢谢

4

5 回答 5

3

“访问”意味着用它做某事。归根结底，您想对每个节点做一些事情，而不仅仅是遍历所有节点。

算法“跟踪”函数参数中调用堆栈中访问的内容。即，如果您问“信息在哪里？” ——信息就在那里。不需要额外的存储空间——这就是递归的美妙之处。

于 2013-10-31T01:51:23.747 回答
1

“访问”通常是指访问该“节点”的内存位置。打印包括访问内存中的“节点”。该特定算法不跟踪访问的节点。它利用递归调用。如果您不熟悉递归，我建议您阅读它。http://en.wikipedia.org/wiki/Recursion

于 2013-10-31T01:55:20.690 回答
1

访问一个节点就是对它应用一些动作，一个例子可以是打印它。

树遍历函数的一种这样的实现将接受一个动作，一个函数对象，应该为每个节点调用它。C 中的一个示例可能如下所示：

typedef void (*node_func)(node_t *);

void in_order (node_t *root, node_func f) {
    if (root) {
        in_order(root->left);
        f(root);              // "visit" the node
        in_order(root->right);
    }
}

也许你实现了一个打印功能：

void print_node (node_t *node) {
    printf("Node: %s", node->id); // or whatever your node looks like
}

然后你可以这样称呼它：

void print_tree(node_t *root) {
    in_order(root, &print_node);
}
于 2013-10-31T01:51:42.210 回答
0

这是一种遍历二叉树的递归方式。

“访问”节点是模棱两可的，因为这是一个伪代码，所以它可能只是意味着将它打印出来，或者执行一组特定的代码。

递归通常通过将其添加到执行堆栈来处理。非递归和递归都使用相似数量的内存。但是堆栈上的访问时间是微不足道的，因为它们是合乎逻辑的执行顺序。所以在这个特定的例子中，左孩子被递归，然后是节点，然后是右孩子。

所以在这个例子中将是：

                               A
                             /   \
                            B     C
                           / \   / \
                          D   E F   G

由于它是一个中序算法，它将被执行：访问D，访问B，访问E，访问A，访问F，访问C，访问G。

于 2013-10-31T01:55:54.800 回答
0

通过访问，我认为它只是在谈论打印它或以某种方式使用它。顺序遍历不同于广度优先，我认为观看一些顺序遍历的 youtube 视频将帮助您更好地理解而不是试图解释。

https://www.youtube.com/watch?v=9870BucMg64 这是一个快速视频，它是一个相当清楚的顺序示例。

于 2013-10-31T01:51:14.953 回答