java - 空指针错误。二叉搜索树程序

Question

我正在尝试编写一棵二叉树。一切工作正常，除了当我尝试删除根节点时。

返回以下错误。我不知道如何解决这个问题。请帮忙。

所有其他功能(如添加、统计、平衡等)都可以正常工作。仅当我尝试在根节点上执行删除时，程序才会返回。

Exception in thread "main" java.lang.NullPointerException
    at TreeClass$BinarySearchTree.Delete(TreeClass.java:147)
    at TreeClass$BinarySearchTree.fnHandler(TreeClass.java:292)
    at TreeClass.main(TreeClass.java:341)

但是，删除可以作用于树中的其他节点。仅遇到根节点的问题。这是我的代码

import java.util.*;

public class TreeClass 
{
    //--------------------------------------------------------------
    static Scanner scanner = new Scanner(System.in);
    static BinarySearchTree BST = new BinarySearchTree();
    //--------------------------------------------------------------
    public static class TreeNode
    {
        TreeNode    Parent;
        TreeNode    LChild;
        TreeNode    RChild;
        Integer     Data;

        public TreeNode(int cbData)
        {
            this.Data = cbData;
            this.LChild = null;
            this.RChild = null;
            this.Parent = null;
        }

        public void SetParent(TreeNode parent)
        {
            this.Parent = parent;
        }
    }

    public static class BinarySearchTree
    {
        int         size;
        TreeNode    Root;

        public BinarySearchTree()
        {
            this.size = 0;
            this.Root = null;
        }

        public void Allocate(TreeNode node, ArrayList<Integer> DataList)
        {
            if (node.LChild != null)
                Allocate(node.LChild, DataList);

            DataList.add(node.Data);

            if (node.RChild != null)
                Allocate(node.RChild, DataList);        
        }

        public void Add(int cbData)
        {
            TreeNode    temp = null;
            TreeNode    node = new TreeNode(cbData);

            if(this.size == 0)
            {
                this.Root = node;
            }
            else
            {
                temp = this.Root;

                while(temp != null)
                {               
                    if(cbData > temp.Data)
                    {
                        if(temp.RChild == null)
                        {
                            temp.RChild = node;
                            node.Parent = temp;
                            break;
                        }
                        temp = temp.RChild;
                    }
                    else if(cbData < temp.Data)
                    {
                        if(temp.LChild == null)
                        {
                            temp.LChild = node;
                            node.Parent = temp;
                            break;
                        }
                        temp = temp.LChild;
                    }
                    else 
                    {
                        //System.out.printf("[Error] %d already exists!\n", cbData);
                        return;
                    }
                }
            }

            if(size == 0)
                System.out.printf("[Success] %d has been added as root\n", node.Data);
            else
                System.out.printf("[Success] %d has been added - Parent: %d\n", node.Data, node.Parent.Data);

            ++this.size;
        }

        public void AddReBalance(int[] List, int min, int max)
        {
            if(min <= max)
            {
                int current = (max+min)/2;

                Add(List[current]);
                AddReBalance(List, min, current-1);
                AddReBalance(List, current+1, max);
            }
        }

        public void Delete(int cbData)
        {
            TreeNode    temp = null;

            if(this.size > 0)
            {
                temp = this.Root;

                while(temp != null)
                {               
                    if(cbData > temp.Data)
                        temp = temp.RChild;
                    else if(cbData < temp.Data)
                        temp = temp.LChild;
                    else 
                    {
                        System.out.printf("[Success] %d found and deleted!\n", cbData);

                        if(temp.LChild != null)
                        {
                            temp.LChild.Parent = temp.Parent;

                            if(temp == temp.Parent.RChild)
                                temp.Parent.RChild = temp.LChild;
                            else if(temp == temp.Parent.LChild)
                                temp.Parent.LChild = temp.LChild;
                        }
                        else if(temp.RChild != null)
                        {
                            temp.RChild.Parent = temp.Parent;

                            if(temp == temp.Parent.LChild)
                                temp.Parent.LChild = temp.RChild;
                            else if(temp == temp.Parent.RChild)
                                temp.Parent.RChild = temp.RChild;
                        }
                        else
                        {
                            if(temp == temp.Parent.LChild)
                                temp.Parent.LChild = null;
                            else if(temp == temp.Parent.RChild)
                                temp.Parent.RChild = null;

                            temp.Parent = null;
                        }

                        --this.size;
                        return;
                    }
                }
            }
            System.out.printf("[Error] %d not found!\n", cbData);
        }

        public int Find(int cbData)
        {
            int         Level = 0;
            TreeNode    temp = this.Root;

            while(temp != null)
            {               
                if(cbData > temp.Data)
                {
                    temp = temp.RChild;
                    ++Level;
                }
                else if(cbData < temp.Data)
                {
                    temp = temp.LChild;
                    ++Level;
                }
                else if(cbData == temp.Data)
                {
                    return ++Level;
                }
            }
            return -1;
        }

        public void Rebalance()
        {
            int[]   cbList = new int[this.size];
            ArrayList<Integer> DataList = new ArrayList();

            Allocate(this.Root, DataList);

            for(int i = 0; i < DataList.size(); ++i)
                cbList[i] = DataList.get(i);

            this.size = 0;

            if(cbList.length > 0) 
                AddReBalance(cbList, 0, cbList.length-1); 
            else
                System.out.print("[Error] You do not have any nodes to balance!\n");
        }

        public void DisplayContent(TreeNode node)
        {
            ArrayList<Integer> DataList = new ArrayList();

            Allocate(this.Root, DataList);
            System.out.printf("Tree Content: ");

            for(int i = 0; i < DataList.size(); ++i)
                System.out.printf("%d ", DataList.get(i));

            System.out.printf("\n");
        }

        public void GetPathData(TreeNode node, ArrayList<Integer> DepthList, int Level)
        {
            ++Level;

            if(node.RChild != null | node.LChild != null)
            {
                if (node.LChild != null)
                    GetPathData(node.LChild, DepthList, Level);

                if (node.RChild != null)
                    GetPathData(node.RChild, DepthList, Level);     
            }
            else
            {
                DepthList.add(Level);
                Level = 0;
            }

        }

        public void DisplayStats()
        {
            int Level = 0, Max = 0, Min = 0;
            ArrayList<Integer> DList = new ArrayList();

            GetPathData(this.Root, DList, Level);

            for(int i = 0; i < DList.size(); ++i)
            {
                int TempPath = DList.get(i);

                if(i == 0)
                {
                    Min = TempPath; 
                    Max = TempPath;
                }
                else
                {
                    if(Min > TempPath)
                        Min = TempPath;
                    if(Max < TempPath)
                        Max = TempPath;
                }
            }

            System.out.printf("Root Data: %d\nItem Count: %d\nShortest Path: %d" +
                    "\nLongest Path: %d\n\n", this.Root.Data, this.size, Min, Max);
        }

        public boolean fnHandler(int cbIn)
        {
            int cbInItem = 0;
            int cbTempRetn = 0;
            boolean retn = false;

            switch(cbIn)
            {
            case 1:
                System.out.printf("Input an integer to add: ");
                cbInItem = scanner.nextInt();
                Add(cbInItem);
                break;

            case 2:
                System.out.printf("Input an integer to delete: ");
                cbInItem = scanner.nextInt();
                Delete(cbInItem);
                break;

            case 3:
                System.out.printf("Input an integer to find:");
                cbInItem = scanner.nextInt();
                cbTempRetn = BST.Find(cbInItem);

                if(cbTempRetn == -1)
                    System.out.printf("[Error] This item was not found!\n");
                else
                    System.out.printf("[Success] Item was found on level: %d\n", cbTempRetn);

                break;

            case 4:
                BST.Rebalance();
                System.out.printf("[Success] Tree has been balanced!\n");
                break;

            case 5:
                BST.DisplayContent(BST.Root);   
                break;

            case 6:
                BST.DisplayStats();
                break;

            case 7:
                retn = true;
                System.out.printf("[Exitting...]\n");
                break;
            }

            return retn;
        }
    }

    public static void main(String[] args) 
    {
        int     cbInput = 0;
        boolean exit = false;

        while(exit == false)
        {
            System.out.printf("\n1. Add Entry - 2. Delete Item - 3. Find Item - 4. Balance Tree"
                            + "\n5. List Data - 6. Statistics  - 7. Exit\n\nInput: ");

            cbInput = scanner.nextInt();
            exit = BST.fnHandler(cbInput);
        }
    }

}

Answer 1

您遇到的问题不仅仅是空指针异常......

当您删除节点时，您尝试获取剩余的“子”节点并将它们重新附加到已删除节点的父节点:

                   if(temp.LChild != null)
                    {
                        temp.LChild.Parent = temp.Parent;

                        if(temp == temp.Parent.RChild)
                            temp.Parent.RChild = temp.LChild;
                        else if(temp == temp.Parent.LChild)
                            temp.Parent.LChild = temp.LChild;
                    }

并且，在您的情况下，temp.Parent为空(因为它是根节点)，因此您得到了NPE(诸如...之类的行，不一定是这个确切的行):

temp == temp.Parent.RChild

不幸的是，你在这里遇到了一些问题......

当您在一般情况下删除节点(即不是根节点)时，父节点可能在另一条腿上已经有子节点，因此您无法将已删除节点的两个子节点都附加到父节点......

...这比注释中的解释更复杂，但是，底线是您删除代码不仅仅是删除一个节点，它还删除该节点以及其中一个节点上的所有子节点腿。

因此，当您解决 null Parent 时，您会发现还有其他问题。