在Java中构建二叉树[已关闭]

data-structures java binary-tree implementation

2022-09-03 13:04:23

我正在构建一个二叉树。让我知道这是否是正确的方法。如果没有，请告诉我怎么做？？我找不到一个正确的链接，其中构建了一个通用的二叉树。BST编码的任何地方。

这是我想做的二叉树。我应该能够完成所有的树遍历。简单的东西。

public class Binarytreenode
{
    public Binarytreenode left;
    public Binarytreenode right;
    public int data;

    public Binarytreenode(int data)
    {
        this.data=data;
    }

    public void printNode()
    {
        System.out.println(data);
    }

    public static void main(String ar[])
    {
        Binarytreenode root = new Binarytreenode(3);
        Binarytreenode n1 = new Binarytreenode(1);
        Binarytreenode n2 = new Binarytreenode(4);
        Binarytreenode n3 = new Binarytreenode(2);
        Binarytreenode n4 = new Binarytreenode(5);

        root.left = n1;
        root.right = n2;
        root.right.left = n3;
        root.right.right = n4;
    }
}

答案 1

我想这就是你正在寻找的：

public class Binarytree
{
    private static Node root;

    public Binarytree(int data)
    {
        root = new Node(data);
    }

    public void add(Node parent, Node child, String orientation)
    {
        if (orientation.equals("left"))
        {
           parent.setLeft(child);
        }
        else
        {
            parent.setRight(child);
        }
    }

    public static void main(String args[])
    {
        Node n1 = new Node(1);
        Node n2 = new Node(4);
        Node n3 = new Node(2);
        Node n4 = new Node(5);

        Binarytree tree = new Binarytree(3); //  3
        tree.add(root, n1, "left"); //         1/ \
        tree.add(root, n2, "right"); //            4
        tree.add(n2, n3, "left"); //             2/ \
        tree.add(n2, n4, "right"); //                5
    }
}

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

    Node (int key) {
        this.key = key;
        right = null;
        left = null;
    }

    public void setKey(int key) {
        this.key = key;
    }

    public int getKey() {
        return key;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getLeft() {
        return left;
    }

    public void setRight(Node right ) {
        this.right = right;
    }

    public Node getRight() {
        return right;
    }

}

答案 2

二叉树背后的想法是它被排序。任何大于当前值的值都位于右侧节点中，每个较小的值都位于左侧节点中。这意味着你不应该在主程序中做树构建。相反，每个节点都应该有一个“插入”方法，该方法确定新节点是应该转到当前节点的左侧还是右侧。当您有一个新节点时，创建该节点，然后调用。root.insert(newNode)

然后，insert-method将像这样工作（因为这显然是一个学生作业，你应该从中学习，你只能从我这里得到伪代码，没有完整的解决方案）：

When value is smaller than own value:
     When there already is a left-node:
         call left-node.insert(new-node)
     When there isn't a left-node yet:
         the left-node is now the new-node
When value is larger than own value:
     When there already is a right-node:
         call right-node.insert(new-node)
     When there isn't a right-node yet:
         the right-node is now the new-node
When value is equal to own value:
     Duplicate value. Either ignore the value or throw an exception.

查找对象是否已在树中的工作方式相同：

When requested value is equal to the value of this node
     return this node
When the requested value is smaller
     When a left node exists
         call left.find(value)         
     When no left node exists
          value doesn't exist in this tree
When the requested value is larger
     When a right node exists
         call right.find(value)         
     When no right node exists
          value doesn't exist in this tree

如果您实际上并不想了解二叉树的工作原理并仅使用它们，只需使用TreeSet，这是一个已经工作的二叉树实现。