java - 遍历二叉树时出现空指针

Question

我正在做一项作业，其中我应该创建一个二叉树并从其抽象父类(super class)(AbstractBinaryTree.java)定义给定的函数。在使用名为 getNumbers() 的函数时，该函数基本上会遍历整个树，同时将每个节点的值添加到它返回的数组列表中。我的 if 语句之一中似乎有一个空指针。

AbstractBinaryTree.java

import java.util.ArrayList;

public abstract class AbstractBinaryTree
{
    protected Node  root;
    protected int   sizeOfTree;

    public AbstractBinaryTree()
    {
        root = null;
        sizeOfTree = 0;
    }

    public int size(){ return sizeOfTree; }

    /** compute the depth of a node */
    public abstract int depth(Node node);

    /** Check if a number is in the tree or not */
    public abstract boolean find(Integer i);

    /** Create a list of all the numbers in the tree. */
    /*  If a number appears N times in the tree then this */
    /*  number should appear N times in the returned list */
    public abstract ArrayList<Integer> getNumbers();


    /** Adds a leaf to the tree with number specifed by input.  */
    public abstract void addLeaf(Integer i);

    /** Removes "some" leaf from the tree.       */
    /*  If the tree is empty should return null  */
    public abstract Node removeLeaf();



    // these methods are only needed if you wish
    // use the TreeGUI visualization program
    public int getheight(Node n){
        if( n == null) return 0;
        return 1 +  Math.max(
        getheight(n.getLeft()) ,  getheight(n.getRight())
        );
    }

    public int height(){ return getheight(root); }



}

Node.java 文件。

public class Node{
    protected Integer data;
    protected Node left;
    protected Node right;

    public Node(Integer data)
    {
        this.data = data;
        this.left = this.right = null;
    }

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

    public Integer getData(){ return this.data; }
    public Node    getLeft(){ return this.left; }
    public Node    getRight(){ return this.right; }

    public void setLeft(Node left){ this.left = left; }
    public void setRight(Node right){ this.right = right; }
    public void setData(Integer data){ this.data = data; }
}

二叉树.java

import java.util.ArrayList;
import java.util.*;
// Student Name:     Adrian Robertson
// Student Number:   101020295
//
// References:       Collier,  R.  "Lectures  Notes  for  COMP1406C-        Introduction  to  Computer  Science  II"  [PDF  documents]. Retrieved from cuLearn: https://www.carleton.ca/culearn/(Winter2016).//
// References:         http://codereview.stackexchange.com/questions/13255/deleting-a-node-from-a-binary-search-tree
//                       http://www.algolist.net/Data_structures/Binary_search_tree/Removal
//                    http://www.geeksforgeeks.org/inorder-tree-traversal- without-recursion-and-without-stack/
public class BinaryTree extends AbstractBinaryTree
{
    protected Node root = new Node(12);

    public static BinaryTree create()
    {
        BinaryTree tempTree = new BinaryTree();
        //creating all the nodes
        Node temp10 = new Node(10);
        Node temp40 = new Node(40);
        Node temp30 = new Node(30);
        Node temp29 = new Node(29);
        Node temp51 = new Node(51);
        Node temp61 = new Node(61);
        Node temp72 = new Node(72);
        Node temp31 = new Node(31);
        Node temp32 = new Node(32);
        Node temp42 = new Node(42);
        Node temp34 = new Node(34);
        Node temp2 = new Node(2);
        Node temp61x2 = new Node(61);
        Node temp66 = new Node(66);
        Node temp3 = new Node(3);
        Node temp73 = new Node(73);
        Node temp74 = new Node(74);
        Node temp5 = new Node(5);
        //setting up the tree
        if (tempTree.root.getData() == null)
        {
            tempTree.root.setData(12);
            tempTree.root.setLeft(temp10);
            tempTree.root.setRight(temp40);
        }
        temp10.setLeft(temp30);
        temp30.setRight(temp29);
        temp29.setRight(temp51);
        temp51.setLeft(temp61);
        temp51.setRight(temp72);
        temp40.setLeft(temp31);
        temp31.setLeft(temp42);
        temp31.setRight(temp34);
        temp34.setLeft(temp61x2);
        temp61x2.setLeft(temp66);
        temp61x2.setRight(temp73);
        temp40.setRight(temp32);
        temp32.setRight(temp2);
        temp2.setLeft(temp3);
        temp3.setRight(temp74);
        temp74.setLeft(temp5);
        return tempTree;
    }
    public int depth(Node node)
    {
        Node current = this.root;
        int counter = 1;
        while(node != current)
        {
            if (node.getData() > current.getData())
            current = current.getRight();
            if (node.getData() < current.getData())
            current = current.getLeft();
        }
        return counter;
    }
    public boolean find(Integer i)
    {
        boolean found = false;
        Node current = this.root;
        if (i == current.getData())
        found = true;
        while (i != current.getData())
        {
            if (i > current.getData())
            current = current.getRight();
            if (i < current.getData())
            current = current.getLeft();
            if (i == current.getData())
            found = true;
        }
        return found;
    }

    public ArrayList<Integer> getNumbers()
    {
        ArrayList<Integer> temp = new ArrayList<Integer>();
        Node current = this.root;
        Node Pre = new Node(null);
        while (current.getData() != null )
        {
            if (current.getLeft().getData() == null) 
            {
                temp.add(current.getData());
                current = current.getRight();
            }
            else
            {
                /* Find the inorder predecessor of current */
                Pre = current.getLeft();
                while(Pre.getRight() != null && Pre.getRight() != current)
                Pre = Pre.getRight();

                /* Make current as right child of its inorder predecessor */
                if (Pre.getRight() == null)
                {
                    Pre.setRight(current);
                    current = current.getLeft();

                }
                /* Revert the changes made in if part to restore the original tree i.e., fix the right child of predecssor */
                else
                {
                    Pre.setRight(null);
                    temp.add(current.getData());
                    current = current.getRight();
                }/* End of if condition Pre.right == NULL */
            }/* End of if condition current.left == NULL*/

        }/*End of while */
        Collections.sort(temp);
        return temp;

    }
    public void addLeaf(Integer i)
    {
        insert(this.root, i);

    }
    public static void insert(Node node, int value) //insert a node Based on provided argument where node is the root of tree
    {
        if (node == null)
        {
            Node first = new Node(value);
            node = first;
        }
        else if (value < node.getData())
        {
            if (node.left != null)
            {
                insert(node.left, value);
            }
            else
            {
                System.out.println(" > Inserted " + value + " to left  of node " + node.getData());
                Node newNode = new Node(value);
                node.left = newNode;
            }
        }
        else if (value > node.getData())
        {
            if (node.right != null)
            {
                insert(node.right, value);
            }
            else
            {
                System.out.println(" > Inserted " + value + " to right of node " + node.getData());
                Node newNode = new Node(value);
                node.right = newNode;
            }
        }
    }
    public Node removeLeaf()
    {
        Node tempA = new Node(61);  //create a new node with that value
        deleteNodeBST(this.root, 61); //delete the node containing that leaf value
        return tempA; //return the copy of that node
    }
    //delete given node with given value
    public boolean deleteNodeBST(Node node, int data) {
        ArrayList<Integer> temp = this.getNumbers();
        if (node == null) {
            return false;
        }
        if (node.getData() == data) {

            if ((node.getLeft() == null) && (node.getRight() == null)) {
                // leaf node
                node = null;
                return true;
            }

            if ((node.getLeft() != null) && (node.getRight() != null)) {
                // node with two children
                node.setData(temp.get(0));
                return true;
            }

            // either left child or right child
            if (node.getLeft() != null) {
                this.root.setLeft(node.getLeft());
                node = null;
                return true;
            }

            if (node.getRight() != null) {
                this.root.setRight(node.getRight());
                node = null;
                return true;
            }
        }
        this.root = node;
        if (node.getData() > data) {
            return deleteNodeBST(node.getLeft(), data);
            } else {
            return deleteNodeBST(node.getRight(), data);
        }
    }
    public static void main(String args[])
    {
        BinaryTree myTree = new BinaryTree();
        myTree.create();
        System.out.println(myTree.getNumbers());
    }
}

create 函数创建一个二叉树并返回该二叉树。这是我应该根据分配指南创建的预定义二叉树。我知道树值没有像正确的二叉树那样正确组织。这是导致遍历时出现空指针的原因吗？因为遍历是为正确的二叉树而设计的。

Answer 1

在 BinaryTree 类中，只有在没有数据时才初始化根节点的左侧和右侧。但是根节点是用数据创建的...

您应该反转以下条件:

//setting up the tree
if (tempTree.root.getData() == null)

并在 getNumbers() 中添加一个测试:

 if (current.getLeft() == null || current.getLeft().getData() == null)