Создание бинарного дерева поиска в Java.Но вывод нулевой

Question

Я пытаюсь создать элементарное двоичное дерево поиска в Java с помощью метода вставки и обхода.Узлы имеют две локальные переменные, строку и int, значение String используется для сортировки узлов.

Каждый BST имеет указатель локальной переменной на корневой узел, и узлы вставляются путем перемещения от узла.Кажется, есть проблема в создании корневого узла, так как мой вывод последовательно выдает ноль вместо.

THE CAT HAT

class BST
{
    public Node root = null;

    private class Node 
    {
        private String key;
        private int value;
        private Node left;
        private Node right;

        public Node ()
        {

        }

        public Node (String key, int value)
        {
            this.key = key;
            this.value = value;
        }

        public String toString ()
        {
            return ("The key is: "+ this.key +" "+ this.value);
        }
    }

    BST ()
    {
    }


    public void put (String key, int value)
    {
        put (root, key, value);
    }

    private void put (Node x, String key, int value)
    {
        Node newNode = new Node(key, value);

        if (x == null)
        {
            x = newNode;
            System.out.println("new node added");
            System.out.println(x);
        }

        int cmp = key.compareTo(x.key);

        if (cmp < 0)
            put(x.left, key, value);
        else if (cmp > 0)
            put(x.right, key, value);
        else
            x.value = value;

    }

    public void inorder (Node x)
    {
        if (x != null) 
        {
            inorder (x.left);
            System.out.println(x.key);
            inorder (x.right); 
        }

    }

    public static void main (String [] args)
    {
        BST bst = new BST();
        bst.put(bst.root,"THE", 1);
        bst.put(bst.root,"CAT", 2);
        bst.put("HAT", 1);
        bst.inorder(bst.root);

    }
}

Answer 1

Бинарное дерево поиска - это структура данных на основе узлов, основная идея бинарного дерева поиска состоит в том, чтобы хранить данные в отсортированном порядке, чтобы мы могли искать данные немного быстрее. Есть три вида узлов, которые играютключевая роль в этом дереве (родительский узел, левый дочерний узел и правый дочерний узел). Значение левого дочернего узла всегда меньше значения родительского узла, равно как и значение правого дочернего узла всегда большезначение родительского узла.Каждый родительский узел может иметь ссылку на один или два дочерних узла, но не более двух дочерних узлов.

Пожалуйста, найдите исходный код из моего технического блога - http://www.algonuts.info/create-a-binary-search-tree-in-java.html

package info.algonuts;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;

class BinaryTreeNode {
    int nodeValue;
    BinaryTreeNode leftChildNode;
    BinaryTreeNode rightChildNode;

    public BinaryTreeNode(int nodeValue) {
        this.nodeValue = nodeValue;
        this.leftChildNode = null;
        this.rightChildNode = null;
    }

    public void preorder() {
        System.out.print(this.nodeValue+" ");
        if(this.leftChildNode != null)   {  
            this.leftChildNode.preorder();  
        }
        if(this.rightChildNode != null) {   
            this.rightChildNode.preorder();
        }
    }

    public void inorder() {
        if(this.leftChildNode != null) {    
            this.leftChildNode.inorder();   
        }
        System.out.print(this.nodeValue+" ");
        if(this.rightChildNode != null) {   
            this.rightChildNode.inorder();  
        }
    }

    public void postorder() {
        if(this.leftChildNode != null) { 
            this.leftChildNode.postorder();
        }
        if(this.rightChildNode != null) { 
            this.rightChildNode.postorder();
        }
        System.out.print(this.nodeValue+" ");
    }
}

class  BinaryTreeCompute {
    private static BinaryTreeNode temp;
    private static BinaryTreeNode newNode;
    private static BinaryTreeNode headNode;

    public static void setNodeValue(int nodeValue) {
        newNode = new BinaryTreeNode(nodeValue);
        temp = headNode;
        if(temp != null) 
        {   mapping();  }
        else 
        {   headNode = newNode; }
    }

    private static void mapping() {
        if(newNode.nodeValue < temp.nodeValue) {    //Check value of new Node is smaller than Parent Node
            if(temp.leftChildNode == null) 
            {   temp.leftChildNode = newNode;   }   //Assign new Node to leftChildNode of Parent Node
            else
            {
                temp = temp.leftChildNode;          //Parent Node is already having leftChildNode,so temp object reference variable is now pointing leftChildNode as Parent Node
                mapping();
            }
        }
        else
        {
            if(temp.rightChildNode == null) 
            {   temp.rightChildNode = newNode;  }   //Assign new Node to rightChildNode of Parent Node
            else
            {
                temp = temp.rightChildNode;         //Parent Node is already having rightChildNode,so temp object reference variable is now pointing rightChildNode as Parent Node
                mapping();
            }
        }
    }

    public static void preorder() {
        if(headNode != null) {  
            System.out.println("Preorder Traversal:");
            headNode.preorder();    
            System.out.println("\n");
        }
    }

    public static void inorder() {
        if(headNode != null) {
            System.out.println("Inorder Traversal:");
            headNode.inorder();
            System.out.println("\n");
        }
    }

    public static void postorder() {
        if(headNode != null) {
            System.out.println("Postorder Traversal:");
            headNode.postorder();   
            System.out.println("\n");
        }
    }
}

public class BinaryTree {
    //Entry Point
    public static void main(String[] args) {
        ArrayList <Integer> intList = new ArrayList <Integer>(Arrays.asList(50,2,5,78,90,20,4,6,98));   
        Iterator<Integer> ptr  = intList.iterator();
        while(ptr.hasNext()) 
        {   BinaryTreeCompute.setNodeValue(ptr.next()); }

        BinaryTreeCompute.preorder();
        BinaryTreeCompute.inorder();
        BinaryTreeCompute.postorder();

    }
}

Answer 2

Добавление к ответу @ Maurice,

Ваш код имеет несколько проблем:

1. Вы ожидаете, что JAVA будет передан по ссылке, когда он передается по значению.Вместо этого вы должны использовать код, указанный Морисом.
2. Вы сравниваете «ключи», когда вы должны сравнивать значения.

Я предлагаю использовать следующий измененный код:

public class BST
{
    public Node root = null;

    private class Node
    {
        private String key;
        private int value;
        private Node left;
        private Node right;

        public Node ()
        {

        }

        public Node (String key, int value)
        {
            this.key = key;
            this.value = value;
        }

        public String toString ()
        {
            return ("The key is: "+ this.key +" "+ this.value);
        }
    }

    BST ()
    {
    }


    public void put (String key, int value)
    {
        root = putInTree (root, key, value);
    }

    private Node putInTree (Node x, String key, int value)
    {
        Node newNode = new Node(key, value);

        if (x == null)
        {
            x = newNode;
            System.out.println("new node added");
            System.out.println(x);
            return newNode;
        }

        //int cmp = key.compareTo(x.key);

        if (value < x.value)
            x.left = putInTree(x.left, key, value);
        else /*if (value >= x.value)*/
            x.right = putInTree(x.right, key, value);
        /*else
            x.value = value;*/

        return x;
    }

    public void inorder (Node x)
    {
        if (x != null)
        {
            inorder (x.left);
            System.out.println(x.key);
            inorder (x.right);
        }

    }

    public static void main (String[] args)
    {
        BST bst = new BST();

        bst.put("THE", 1);
        bst.put("CAT", 2);
        bst.put("HAT", 1);
        bst.inorder(bst.root);

    }
}

Answer 3

См. Ссылку ниже, хорошее объяснение BST http://www.java2novice.com/java-interview-programs/implement-binary-search-tree-bst/

Answer 4

Параметры передаются по значению.Используйте возвращаемое значение метода, чтобы изменить что-то:

public void put (String key, int value)
{
    root = put (root, key, value);
}

private Node put (Node x, String key, int value)
{
    Node newNode = new Node(key, value);

    if (x == null)
    {
        System.out.println("new node added");
        System.out.println(x);
        return newNode;
    }

    int cmp = key.compareTo(x.key);

    if (cmp < 0)
        x.left = put(x.left, key, value);
    else if (cmp > 0)
        x.right = put(x.right, key, value);
    else
        x.value = value;

    return x;
}