在执行树修改时更新子节点时如何更新根节点?
How is the Root Node being updated when child nodes are the ones updated when performing Tree modifications?
Tree 的父节点如何使用我们执行的子更新进行更新?特别是当你进行 BFS 或 DFS 搜索时,在节点上执行检查,然后更新该节点。是什么导致内存或编程语言知道“哦,嘿,我也必须对 Root 节点进行此更新!”
在我的示例中,我使用的是 Trie(不是很重要,但我只是将其称为树)。我在下面有这个 BFS 搜索,它搜索一堆节点并将更新为特定的单词值。我的评论就是我的问题所在。该子节点当前存储在“双端队列”中。程序怎么知道我的意思是更新 Root 中的值,而不仅仅是传递给变量“deque”的值?
对我来说,我认为应该发生的事情是 Root 不应该被更新,唯一被更新的是变量“deque”,然后在它完成之后,所有东西都会被垃圾收集并且 Root 保持不变.相反,当“deque”更新时,Root 也会更新。也许我在我的数据结构课程中错过了这一点,但它已经困扰我一段时间了,我一直无法找到解释这一点的资源。
private static void BFS_UpdateAllWords(Node Root, string testword, string updatevalue)
{
Queue<Node> bfs_queue = new Queue<Node>();
bfs_queue.Enqueue(Root);
while (bfs_queue.Count > 0)
{
var deque = bfs_queue.Dequeue();
foreach (string childKey in deque.Children.Keys)
{ // Update all child nodes at the key
if (deque.Children[childKey].Word.Equals(testword))
{
// This part right here for any time of Tree traversal
deque.Children[childKey].WordType = updatevalue;
}
bfs_queue.Enqueue(deque.Children[childKey]);
}
}
}
我认为您遇到的大致是按值传递与按引用传递问题。当一个函数按值传递时,该函数的参数被复制,这样函数就有了自己不同的版本,调用者将看不到函数对参数所做的更改。但是,如果一个函数是通过引用传递的,则不会进行任何复制,并且如果该函数对参数进行了更改,则调用者将看到所做的更改。
C# 和 Java 在这里有点滑稽,因为它们总是按值传递(除非您明确告诉 C# 否则),但它们也“按值传递引用”。也就是说,当您向函数传递引用类型(如对象或 class)时,函数接收的是对其引用的副本(而不是底层对象的深层副本)。这意味着底层对象仍然可以在函数内部更改,因为该函数有自己的引用。
这样做的结果是,当您向 Enqueue 方法传递一个引用类型时,就像您的 Node 对象一样,存储在队列中的只是对位于队列外部的相同底层对象的引用(的副本) .也就是说,队列中的元素不是树节点的深层副本:它们是对相同底层 Node 对象的引用。因此,当您将 Deque() 放入“deque”变量时,您只是创建了另一个别名,该别名引用某个节点,否则您可能已经能够直接从 Root 节点进行遍历。这样,当您修改“双端队列”节点的属性时,您是在直接修改某个 Node 对象的属性,因为它存在于 Root 节点下的树中——不是该对象的副本,它在内存中有自己的地址,而是相同的底层对象。
这就是为什么当 deque 被垃圾收集时,更改仍然存在:deque 只包含对已存在于根树中的节点的引用的副本。您的程序无需弄清楚就可以知道通过双端队列所做的更改也会影响根树中的节点。因为 deque 包含对这些相同底层节点的引用,通过它所做的更改已经直接修改了这些节点,因此在 deque 超出范围后,更改自然会持续存在。
Tree 的父节点如何使用我们执行的子更新进行更新?特别是当你进行 BFS 或 DFS 搜索时,在节点上执行检查,然后更新该节点。是什么导致内存或编程语言知道“哦,嘿,我也必须对 Root 节点进行此更新!”
在我的示例中,我使用的是 Trie(不是很重要,但我只是将其称为树)。我在下面有这个 BFS 搜索,它搜索一堆节点并将更新为特定的单词值。我的评论就是我的问题所在。该子节点当前存储在“双端队列”中。程序怎么知道我的意思是更新 Root 中的值,而不仅仅是传递给变量“deque”的值?
对我来说,我认为应该发生的事情是 Root 不应该被更新,唯一被更新的是变量“deque”,然后在它完成之后,所有东西都会被垃圾收集并且 Root 保持不变.相反,当“deque”更新时,Root 也会更新。也许我在我的数据结构课程中错过了这一点,但它已经困扰我一段时间了,我一直无法找到解释这一点的资源。
private static void BFS_UpdateAllWords(Node Root, string testword, string updatevalue)
{
Queue<Node> bfs_queue = new Queue<Node>();
bfs_queue.Enqueue(Root);
while (bfs_queue.Count > 0)
{
var deque = bfs_queue.Dequeue();
foreach (string childKey in deque.Children.Keys)
{ // Update all child nodes at the key
if (deque.Children[childKey].Word.Equals(testword))
{
// This part right here for any time of Tree traversal
deque.Children[childKey].WordType = updatevalue;
}
bfs_queue.Enqueue(deque.Children[childKey]);
}
}
}
我认为您遇到的大致是按值传递与按引用传递问题。当一个函数按值传递时,该函数的参数被复制,这样函数就有了自己不同的版本,调用者将看不到函数对参数所做的更改。但是,如果一个函数是通过引用传递的,则不会进行任何复制,并且如果该函数对参数进行了更改,则调用者将看到所做的更改。
C# 和 Java 在这里有点滑稽,因为它们总是按值传递(除非您明确告诉 C# 否则),但它们也“按值传递引用”。也就是说,当您向函数传递引用类型(如对象或 class)时,函数接收的是对其引用的副本(而不是底层对象的深层副本)。这意味着底层对象仍然可以在函数内部更改,因为该函数有自己的引用。
这样做的结果是,当您向 Enqueue 方法传递一个引用类型时,就像您的 Node 对象一样,存储在队列中的只是对位于队列外部的相同底层对象的引用(的副本) .也就是说,队列中的元素不是树节点的深层副本:它们是对相同底层 Node 对象的引用。因此,当您将 Deque() 放入“deque”变量时,您只是创建了另一个别名,该别名引用某个节点,否则您可能已经能够直接从 Root 节点进行遍历。这样,当您修改“双端队列”节点的属性时,您是在直接修改某个 Node 对象的属性,因为它存在于 Root 节点下的树中——不是该对象的副本,它在内存中有自己的地址,而是相同的底层对象。
这就是为什么当 deque 被垃圾收集时,更改仍然存在:deque 只包含对已存在于根树中的节点的引用的副本。您的程序无需弄清楚就可以知道通过双端队列所做的更改也会影响根树中的节点。因为 deque 包含对这些相同底层节点的引用,通过它所做的更改已经直接修改了这些节点,因此在 deque 超出范围后,更改自然会持续存在。