线性数组的二叉树构造函数

Question

注意：这是作业，所以请不要直接给我答案，但指点会有所帮助。

作业概览：

(Test each method to ensure that it works properly.)

Generate a binary search with 100 elements added in the correct order - add the numbers 1 through 100 to the tree in the correct order add 1, then 2, then 3, etc.

Generate a binary search with 100 elements add in revers order - add the numbers 100, 99, 98 and so on.

Generate a binary search with 100 randomly generated elements.

我之所以在问题中说线性数组是因为根必须是数组中的第一个元素，然后将其余元素相加。

我没有正确测试树是否正确制作所需的所有其他方法，我即将离开工作。但是，我在算法的开头下方发布了我认为可行的算法，只是不确定。

public BST(int[] numbers)
{
    node root;
    node currentParent; 
    node previousParent = null; 
    int i = 1; // skip the root, that will be handled manualy 

    root = new node(numbers[0]); // first element is the root
    currentParent = root;

    // handle right hand side of binary tree first
    while (i > root.getValue())
    {
        while (i > currentParent.getValue())
        {
            node newNode = new node (numbers[i]);
            currentParent.setRightChild(newNode);
            previousParent = currentParent;
            currentParent = newNode;
            i++;
        } // end inner while

        if (previousParent.leftChild == null)
        {
            node newNode = new node(numbers[i]);
            previousParent.leftChild =  newNode;
            currentParent = newNode;
            i++;
        } // end if branch
        else
        {
            System.out.println("Hmm, something seems to be wrong!");
        } // end else
    } // end right side binary tree while
} // end integer array constructor

这几乎就是整个算法，我必须再做一次，但要颠倒 < 和 > 符号（如果这是正确的）。我使用此算法是否正确？

正在按要求添加节点 class。

public class node 
{
node leftChild; // left pointer
node rightChild; // right pointer
int value; // will be the int value inside the node
boolean isLeaf; // boolean for determing if a node is a left node or not

/*
    Null constructor for the class.  Sets the pointers to null 
*/
public node ()
{
    leftChild = null;
    rightChild = null; 
} // end null constructor


/*
    Intialzing constructor that will take a single integer as input
*/
public node (int number)
{
    leftChild = null;
    rightChild = null;
    value = number; 
} // end intialzing constructor with int input


/*
    The setValue method will take the int value inputted from the array into 
    a new node 
*/
public void setValue(int number)
{
    value = number;
} // end setValue()


/*
    The getValue method will return to the user the value that is stored 
    inside a specific node.
*/
public int getValue()
{
    return value; 
} // end getValue()


/*
    The setLeftChild method will set the pointers to the nodes left child 
    which will be a value that is equal or lower to the paret node
*/
public void setLeftChild (node leftChild)
{
    this.leftChild = leftChild;
} // end setLeftChild()


/*
    The setRightChild method will be the same as setLeftChild above but will
    handle setting the nodes right child.  The right child will be a value 
    that is greater than the parent node
*/
public void setRightChild(node rightChild)
{
    this.rightChild = rightChild; 
} // end setRightChild


/*
    the getLeftChild method will return to the user/calling method what the
    left child of a given node is. 
*/
public node getLeftChild (node currentNode)
{
    return leftChild;
} // end getLeftChild()


/*
    the getRightChild method is exactly the same as the getLeftChil method 
    above, except it will return the right child instead
*/
public node getRightChild(node currentNode)
{
    return rightChild; 
} // end getRightChild()

/*
    The setLeaf method will be in charge of manipulating a boolean value and
    setting it to true if the node is a left or not
*/
public void setLeaf(boolean leaf)
{
    if (leaf == true)
    {
        isLeaf = true;
    } // end if
    else
    {
        isLeaf = false;
    } // end else
} // end setLeaf

/*
    The getLeaft method will simply return a boolean value that indicates if
    the given node is a left node or not
*/
public boolean getLeaf()
{
    return isLeaf;
} // end getLeaf()
} // end node class

Answer 1

不，对不起，这是错误的。

您正在比较索引与数据值。您应该只将相同的事物与相同的事物进行比较。假设任务是将数字 1001 到 1100 放入树中，而不是 1 到 100。这将使区分索引和数据值变得更容易（这里的区别非常微妙，因为你的索引是 0 到 99 而你的数据值 1 到 100）。
你不能假设你 "handle the right hand part first"。你必须根据给定的值来决定给定的项目是向左还是向右，以及它是小于还是大于当前节点的值。
如果您有一个无序数组，尝试先添加所有高值然后添加所有低值将不起作用。

最后一个提示：class 应该命名为 Node，而不是 node。类并且所有类型名称都应该以大写字母开头，变量、字段和方法名称应该以小写字母开头，常量应该全部大写。

线性数组的二叉树构造函数

Binary Tree constructor from linear array

java

arrays

binary-tree

作业概览：