时间戳

首页 > 解决方案 > 我应该怎么做才能通过将深度作为java中的输入来创建二叉树？

java - 我应该怎么做才能通过将深度作为java中的输入来创建二叉树？

问题描述

就我而言，我想通过将深度作为输入来创建一棵二叉树。

例如，如果我执行tree.create(3)，当最左边的深度为 3 时，会生成一棵二叉树，这意味着树中有 2^3 - 1 个节点，并且它们的值都是将为 0。相应地，索引将为 0 - 6。

class Tree<T> {

    int depth;
    int index;
    T value;

    public Tree(int index,T value) {
        this.index = index;
        this.value = value;
    }

    public static <K> Tree<K> create(int depth){
        if(depth >= 1) {

            //return a tree with the inputting depth, 
            //but I don't know how to do in this step

            return new Tree(...?)
        }
    } 
}

我应该使用哪一部分知识来在 Java 中实现这一点？谢谢！

标签： javadata-structures

解决方案

通常在使用二叉树数据结构时，您需要编写递归方法。编写递归方法时，需要编写终止递归的条件。在您的情况下，如果我们达到所需的深度，递归将结束。为了确定我们是否达到了期望的深度，我们需要知道期望的深度是多少以及当前的深度是多少。我将假设二叉树中根节点的深度为零。这意味着对于 3 的最大深度（如您问题中的示例），最深的级别将是 2 级。如果我们没有达到所需的深度，那么我需要添加一个左右子节点，然后在每个子节点上调用相同的方法，并确保子节点的深度比父节点的深度大一。

  • 一个节点（可能）添加子节点
  • 当前深度
  • 最大深度

请注意，我不需要处理每个节点包含的值（或数据），因为您在问题中声明每个节点都将具有相同的值。因此，我可以简单地将值从父节点复制到它的每个子节点。

这是一个完整的例子。请注意，当我对其进行测试时，大于 25 的深度会导致 an，OutOfMemoryError因为可以进行多少递归方法调用是有限制的。

import java.util.ArrayList;
import java.util.List;

public class BinTree<T> {
    BinTreeNode<T>  root;

    public static <T> BinTree<T> create(int depth, T val) {
        if (depth > 0) {
            BinTree<T> theTree = new BinTree<>();
            theTree.root = new BinTreeNode<>(val);
            theTree.addLevel(theTree.root, 0, depth);
            return theTree;
        }
        else {
            throw new IllegalArgumentException("Invalid depth: " + depth);
        }
    }

    public void getAllElements(BinTreeNode<T> aNode, List<T> list) {
        if (aNode == null) {
            return;
        }
        else {
            getAllElements(aNode.left, list);
            list.add(aNode.genericObject);
            getAllElements(aNode.right, list);
        }
    }

    private void addLevel(BinTreeNode<T> theNode, int level, int deepest) {
        if (level == deepest - 1) {
            return;
        }
        theNode.left = new BinTreeNode<>(theNode.genericObject);
        theNode.right = new BinTreeNode<>(theNode.genericObject);
        addLevel(theNode.left, level + 1, deepest);
        addLevel(theNode.right, level + 1, deepest);
    }

    public static void main(String[] args) {
        BinTree<String> aTree = BinTree.create(3, "George"); // max depth = 25
        List<String> list = new ArrayList<>();
        aTree.getAllElements(aTree.root, list);
        System.out.println(list.size());
    }
}

class BinTreeNode<T> {
    BinTreeNode<T> left, right;
    T genericObject;

    public BinTreeNode(T obj) {
        genericObject = obj;
    }
}

请注意，我添加了方法getAllElements作为测试，以查看是否创建了正确数量的节点。

推荐阅读