C#节点指针问题

Question

我在使用 C# 设置子节点时遇到了一些问题。我正在尝试构建一个节点树，其中每个节点都包含一个 int 值，并且最多可以有多个等于它的值的子节点。

当我在一个节点中迭代寻找空(null)子节点以便我可以将一个新节点添加到该位置时，我的问题出现了。我可以找到并返回空节点，但是当我为它设置新节点时，它会失去与父节点的连接。

因此，如果我添加 1 个节点，那么它会链接到我的头节点，但如果我尝试添加第二个节点，它不会成为头节点的子节点。我正在尝试使用单元测试来构建它，所以这里的测试代码显示头部确实没有显示新节点，因为它是子节点(也通过 visual studios 调试器确认):

  [TestMethod]
  public void addSecondNodeAsFirstChildToHead()
  {
     //arange
     Problem3 p3 = new Problem3();
     p3.addNode(2, p3._head);
     Node expected = null;
     Node expected2 = p3._head.children[0];
     int count = 2;

     //act
     Node actual = p3.addNode(1, p3._head);
     Node expected3 = p3._head.children[0];

     //assert
     Assert.AreNotEqual(expected, actual, "Node not added"); //pass
     Assert.AreNotEqual(expected2, actual, "Node not added as first child"); //pass
     Assert.AreEqual(expected3, actual, "Node not added as first child"); //FAILS HERE
     Assert.AreEqual(count, p3.nodeCount, "Not added"); //pass
  }

这是我的代码。

public class Node
   {
      public Node[] children;
      public int data;

      public Node(int value)
      {
         data = value;
         children = new Node[value];

         for(int i = 0; i < value; i++)
         {
            children[i] = null;
         }
      }
   }

   public class Problem3
   {
      public Node _head;
      public int nodeCount;

      public Problem3()
      {
         _head = null;
         nodeCount = 0;
      }

      public Node addNode(int value, Node currentNode)
      {
         if(value < 1)
         {
            return null;
         }

         Node temp = new Node(value);

         //check head
         if (_head == null)
         {
            _head = temp;
            nodeCount++;
            return _head;
         }

         //start at Current Node
         if (currentNode == null)
         {
            currentNode = temp;
            nodeCount++;
            return currentNode;
         }

         //find first empty child
         Node emptyChild = findEmptyChild(currentNode);
         emptyChild = temp;
         nodeCount++;
         return emptyChild;
      }

      public Node findEmptyChild(Node currentNode)
      {
         Node emptyChild = null;
         //find first empty child of current node
         for (int i = 0; i < currentNode.children.Length; i++)
         {
            if (currentNode.children[i] == null)
            {
               return currentNode.children[i];
            }
         }
         //move to first child and check it's children for an empty
         //**this causes values to always accumulate on left side of the tree
         emptyChild = findEmptyChild(currentNode.children[0]);
         return emptyChild;
      }

我觉得问题在于我正在尝试像在 C++ 中那样将节点视为指针，但它并没有像我预期的那样工作。

Answer 1

函数不可能返回指向尚不存在的对象的句柄(或指针)。要么在函数内部初始化不存在的值，要么提供足够的变量以便在函数外部对其进行初始化。

一个解决方案是重命名函数 findEmptyChild类似于 initializeEmptyChild(Node currentNode, Node newNode) , 再加一个 Node它的参数(调用它时将是 temp 值)，并在 return 之前的循环中您初始化以前为空的 Node , currentNode.children[i] = newNode .

另一种解决方案是不只返回一个 Node但是有两个值，一个父节点和一个找到空子节点的索引，Tuple<Node, int> findEmptyChild(Node currentNode) ，并在循环中代替 return currentNode.children[i]你做return new Tuple<Node, int>(currentNode, i) .调用该函数时，您会将代码更改为

var parentAndIndex = findEmptyChild(currentNode);
parentAndIndex.Item1.children[parentAndIndex.Item2] = temp;