创建二叉树（但不是BST）-Java 学习之路

当我创建BST时，在插入节点期间，我检查新节点的值是小于左子节点还是大于右子节点 . 我向下走，直到找到插入节点的正确位置 . 现在假设我有一个二叉树，我想创建一个树，我该怎么做？我是否需要使用BFS算法来做到这一点？

谢谢

2 回答

3

这不是插入应该如何在BST中工作，如果有一个左节点将值与它，如果不存在左节点，则在那里插入值 . 右侧也是如此，但如果比较结果大于当前节点（BST中没有重复值） .

您的问题是如何创建二进制树而不是BST，如果您想要一个简单的二进制树来构建一个完整的二叉树，那么只需从左到右逐层插入节点 . 当然BFS是逐层工作的，但它是一种搜索算法，因为你是从头开始构建它所以不需要搜索树 .

Edit ：如果你想要一个更简单的二叉树构造版本，只需在一个分支中一直向下插入2个节点而不回溯，即使你也插入了1个节点，仍然是二叉树 .

Enother Edit ：每个BST都是二叉树，每个二叉树都是树，这个参数不能被反转（例如，不是每个BT都是BST ......等） . 所以，如果你有BT，它已经是一棵树了 .

问候，

回复于 2024-05-18T20:13:29+08:00

在这里，我正在制作一个对BFS有益的 Weight-based Binary Tree ，因为它保持了树的 balancer .

我会在_2706105中实现它：

class BT_Node
{
    public int value;
    public int depth;
    public long weight;
    public BT_Node left, right;

    public BT_Node (int value, int depth)
    {
        this.depth = depth;
        this.value = value;
        this.weight = 0;
        this.left = this.right = null;
    }
}

class BT
{
    private BT_Node root;

    public long size ()
    {
        return (root!=null ? root.weight : 0);
    }

    public long size (BT_Node node)
    {
        return (node!=null ? node.weight : 0);
    }

    public void insert (int value)
    {
        int depth = 0;
        BT_Node parent = root;

        if (root == null)
        {
            root = new BT_Node (value, 0);
        }
        else
        {
            root.weight++;

            while (parent.left!=null && parent.right!=null)
            {
                if (parent.left.weight <= parent.right.weight)
                    parent=parent.left;
                else
                    parent=parent.right;

                parent.weight++;
            }

            if (parent.left == null)
                parent.left = new BT_Node (value, parent.depth+1);
            else
                parent.right = new BT_Node (value, parent.depth+1);
        }
    }
}

回复于 2024-05-18T20:13:29+08:00

创建二叉树（但不是BST）

2 回答

相关问题