如何在构建二叉树时添加新节点

Question

我正在使用另一个名为 RedBlackTree 的 BinaryTree class 版本。我正在尝试使用此添加方法构建树。

 public void Add(T val)
    {
        RedBlackNode<T> newNode = _rootNode;

        while(newNode != null)
        {
            if(val.CompareTo(newNode.Data) < 0)
            {
                newNode = newNode.LeftChild;
            }
            else if(val.CompareTo(newNode.Data) >= 0)
            {
                newNode = newNode.RightChild;
            }
        }
        newNode.Data = val;      //nullReferenceException thrown here  <---
        newNode.IsBlack = false;
        FixColors(newNode);
    }

_rootNode 是一个私有字段，给出了树的根。根据特定说明，它被初始化为 null。此 Add 方法是从另一个 class 中从一个正在读取文件信息的方法中调用的。在第一次迭代中，抛出 nullReferenceException，我假设是因为我试图更改的节点为空。我不知道我还应该如何更改这些节点的数据值。如有必要，我将 post 将代码添加到程序的其余部分。

Answer 1

嗯，当 newNode 不为空时，while 循环不会退出。这意味着一旦循环退出，newNode is 将为 null。我想你想要的是在 RightChild 或 LeftChild 节点为空的情况下创建一个新节点，并将 newNode 设置为该节点。

此外，正如 Partha 的回答所指出的，您需要初始化 _rootNode 值（如果尚未设置）。

我不太清楚节点的父节点属性是如何设置的，所以我假设父节点是作为子节点的构造函数参数注入的：

public void Add(T val)
{
    RedBlackNode<T> parent = _rootNode;
    RedBlackNode<T> target = null;

    while(target == null)
    {
        if(val.CompareTo(parent.Data) < 0)
        {
            if (parent.LeftChild == null) 
                target = parent.LeftChild = new RedBlackNode<T>(parent);
            else
                parent = parent.LeftChild;
        }
        else if(val.CompareTo(newNode.Data) >= 0)
        {
            if (parent.RightChild == null) 
                target = parent.RightChild = new RedBlackNode<T>(parent);
            else
                parent = parent.RightChild;
        }
    }
    target.Data = val;
    target.IsBlack = false;
    FixColors(newNode);
}

Answer 2

您需要先创建节点，然后才能访问其他字段。因此，如果 _rootNode 为空，则使用 new 关键字创建。

public void Add(T val)
{
      if(_rootNode == null)
      {
           RedBlackNode<T> newNode = new RedBlackNode<T>();
           newNode.Data = val;
           newNode.IsBlack = false;
           _rootNode = newNode;
           return;
      }
      //Followed by your logic
}

如何在构建二叉树时添加新节点

How to add new node when building Binary Tree

c#

binary-tree

nullreferenceexception