-5

我的红黑树代码中有空引用异常未处理错误。我试图删除它，但我不能。错误在这一行

if (currentNode.left.color == Color.Red && currentNode.right.color == Color.Red)

请你们能解决这个错误这是我的代码

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algo_Project
{
    class Program
    {

        public enum Color
        {
            Red = 0, Black = 1
        }

        public enum direction
        {
            Left, Right
        }
        public class Node
        {
            public IComparable data;
            public Node left;
            public Node right;
            public Color color = Color.Black;

           public Node(IComparable data): this(data, null, null)
            {
            }

            public Node(IComparable data, Node left, Node right)
            {
                this.data = data;
                this.left = left;
                this.right = right;
            }

        }

        public class Tree
        {
            protected Node root;
            protected Node freshNode;
            protected Node currentNode;

            protected Tree()
            {
                freshNode = new Node(null);
                freshNode.left = freshNode.right = freshNode;
                root = new Node(null);
            }

            protected int Compare(IComparable item, Node node)
            {
                if (node != root)
                    return item.CompareTo(node.data);
                else
                    return 1;
            }

            public IComparable Search(IComparable data)
            {
                freshNode.data = data;
                currentNode = root.right;
                while (true)
                {
                    if (Compare(data, currentNode) < 0)
                        currentNode = currentNode.left;
                    else if (Compare(data, currentNode) > 0)
                        currentNode = currentNode.right;
                    else if (currentNode != freshNode)
                        return currentNode.data;
                    else
                      return null;
                }
            }

            protected void Display(Node temp)
            {
                if (temp != freshNode)
                {
                    Display(temp.left);
                    Console.WriteLine(temp.data);
                    Display(temp.right);
                }
            }
            protected void Display()
            {
                this.Display(root.right);

            }

        }

        public sealed class RedBlackTree : Tree
        {
            private Color Black = Color.Black;
            private Color Red = Color.Red;
            private Node parentNode;
            private Node grandParentNode;
            private Node tempNode;



            public void Insert(IComparable item)
            {
                currentNode = parentNode = grandParentNode = root;
                freshNode.data = item;
                int returnValue = 0;
                while (Compare(item, currentNode) != 0)
                {
                    tempNode = grandParentNode;
                    grandParentNode = parentNode;
                    parentNode = currentNode;
                    returnValue = Compare(item, currentNode);
                    if (returnValue < 0)
                        currentNode = currentNode.left;
                    else
                        currentNode = currentNode.right;
                    if (currentNode.left.color == Color.Red && currentNode.right.color == Color.Red)
                    {
                        ReArrange(item);
                    }
                }

                if (currentNode == freshNode)
                {
                    currentNode = new Node(item, freshNode, freshNode);
                    if (Compare(item, parentNode) < 0)
                        parentNode.left = currentNode;
                    else
                        parentNode.right = currentNode;
                    ReArrange(item);

                }
            }


            private void ReArrange(IComparable item)
            {
                currentNode.color = Red;
                currentNode.left.color = Color.Black;
                currentNode.right.color = Color.Black;
                if (parentNode.color == Color.Red)
                {
                    grandParentNode.color = Color.Red;
                    bool compareWithGrandParenrNode = (Compare(item, grandParentNode) < 0);
                    bool compareWithParentNode = (Compare(item, parentNode) < 0);
                    if (compareWithGrandParenrNode != compareWithParentNode)
                        parentNode = Rotate(item, grandParentNode);
                    currentNode = Rotate(item, tempNode);
                    currentNode.color = Black;
                }

                root.right.color = Color.Black;
            }

            private Node Rotate(IComparable item, Node parentNode)
            {
                int value;
                if (Compare(item, parentNode) < 0)
                {
                    value = Compare(item, parentNode.left);
                    if (value < 0)
                        parentNode.left = this.Rotate(parentNode.left, direction.Left);
                    else
                        parentNode.left = this.Rotate(parentNode.left, direction.Right);
                    return parentNode.left;
                }
                else
                {
                    value = Compare(item, parentNode.right);
                    if (value < 0)
                        parentNode.right = this.Rotate(parentNode.right, direction.Right);
                    else
                        parentNode.right = this.Rotate(parentNode.right, direction.Right);
                    return parentNode.right;
                }

            }


            private Node Rotate(Node node, direction direction)
            {
                Node tempNode;
                if (direction == direction.Left)
                {
                    tempNode = node.left;
                    node.left = tempNode.right;
                    tempNode.right = node;
                    return tempNode;
                }
                else
                {
                    tempNode = node.right;
                    node.right = tempNode.left;
                    tempNode.left = node;
                    return tempNode;

                }
            }


        }
        static void Main(string[] args)
        {
            RedBlackTree redBlackTree = new RedBlackTree();
            Random random = new Random();
            for (int i = 0; i < 100000; i++)
            {
                redBlackTree.Insert(random.Next(1, 100000));
                random.Next();
            }
            redBlackTree.Insert(1000001);
            DateTime startTime = DateTime.Now;
            int p = (int)redBlackTree.Search(1000001);
            DateTime endTime = DateTime.Now;
            TimeSpan TimeElapsed = (TimeSpan)(endTime - startTime);
            Console.WriteLine("The number " + p + "has been found in" + TimeElapsed.Milliseconds.ToString() + "milliseconds.");
            Console.ReadLine();
            Console.ReadLine();
        }
    }



}

请您告诉我有关此错误的信息我希望它修复到 2013 年 6 月 6 日星期四

4

1 回答 1

5

当您的Insert方法遇到叶子时，currentNode.left或者currentNode.right将是null。此时，您没有检查null，因此当您尝试访问color.

您需要null在插入时添加检查以处理叶子条件。

于 2013-06-03T15:51:55.990 回答