Рекурсивно создавать двоичное дерево на определенной глубине

Question

Я хочу создать двоичное дерево с определенной глубиной. Мой код до сих пор создает бинарные деревья до определенной максимальной глубины, но также создает деревья с более низкой максимальной глубиной. Я проиллюстрирую свою проблему ниже.

Мой код до сих пор (метод называется create):

public class BT<E>{ 
    E value; 
    BT<E> left, right; 

    public BT(E value) 
    { 
     this.value=value; 
    } 

    public BT (E value, BT left, BT right) 
    { 
     this.value = value; 
     this.left = left; 
     this.right = right; 
    } 

    private static final String[] random = {"a","b","c","d"}; 
    public static BT create(int depth) { 
     if (depth > 1 && random.nextBoolean())//if not at the maximum depth 
     //choose randomly a,b,c,d - nextBoolean ensures it is not balanced all the time 
     { 
     String random = OPERATORS[random.nextInt(OPERATORS.length)]; 
     return new BT(operator, create(depth-1), create(depth-1));//recursively create tree 
     } 
     else {//when node is a leaf node, make it X 
     String t = "x"; 
     return new BT(t); 
     } 
    } 
} 

Проблема: Если я ввода 3 в глубину она должна создавать деревья, как это ТОЛЬКО:

(c)    (d)   (a) 
(b) (a)   (b)  (d) (c) 
(x)(x)(x)(x)  (x) (x)    (x) 

Мой код в настоящее время создает деревья, как указано выше, но также включает в себя такие деревья, как:

(x)  (c)   (d) 
      (x)  (x) (x) 

Очевидно, что это не глубина 3. Я не хочу этого. I только хочу первый без этих исключений.

Может ли кто-нибудь взглянуть на мой код и рассказать мне, что я делаю неправильно и как его исправить.

Answer 1

Самый простой способ - создать функцию-оболочку, которая вызывает вашу функцию дерева создания.

Функция создаст случайную свободу, используя вашу функцию, проверит, имеет ли она необходимую глубину X. Если это так, она вернется; если нет, то это будет вызывать функцию снова до тех пор, пока не найдет дерево с правильной глубиной

Answer 2

Проблема заключается в том:

random.nextBoolean()

в этой строке:

if (depth > 1 && random.nextBoolean()) 

You намереваясь создать несбалансированные деревья с этим утверждением, но это также имеет очень высокую вероятность создания деревьев без каких-либо ветвей максимальной глубины. Все, что вам нужно, это для false, которое должно быть возвращено несколько раз подряд в начале рекурсии, и у вас есть нежелательный результат. Учитывая, что есть 50% шанс для этого, это произойдет больше, чем вы думаете! До гарантия по крайней мере одна ветка с максимальной глубиной вам потребуется немного больше обработки.

Одно из предложений может заключаться в том, чтобы заранее определить одну или несколько ветвей в вашем дереве, которые достигнут максимальной глубины, и оставить остальных на случай. Как вы используете бинарное дерево это может быть сделано с булевыми:

int depth = 3; 
boolean[] branch = new boolean[depth]; 
for (int i = 0; i < branch.length; i++) { 
    branch[i] = random.nextBoolean(); 
} 

После того как вы это, сгенерировать дерево, как вы делаете сейчас. После завершения перейдите через свое дерево, поскольку логическое [] диктует, используя true для left и false для права. Если вы обнаружите, что ребенок отсутствует для определенного логического значения, и вы не достигли максимальной глубины, создайте этого ребенка и продолжайте. Это не особенно привлекательный способ сделать это, но это дешево и быстро.

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

Answer 3

Как уже упоминалось проблема в этой строке:

if (depth > 1 && random.nextBoolean()) 

То, что вы должны сделать, это:

• Контролировать порядок оценки:

  Учитывать return new BT(operator, create(depth-1), create(depth-1));

  Левое дерево всегда будет оцениваться первым, а затем правое дерево.

• Пусть деревья создают листья, если один из них достиг желаемой глубины:

  Я создал логическую переменную finished для этой цели

Итак, сначала мы создадим путь с желаемая глубина. Затем мы разрешим другим путям создать Дерево или Лист.

private boolean finished; 

    public BT<E> create(int depth){ 
     if(depth<=0) { // One tree is at desired depth 
      finished = true; 
      return new BT<E>(null); 
     } 
     if(finished) // Let the other trees set a Leaf. 
      if(random.nextBoolean()) 
       return new BT<E>(null); 

     BT<E> temp = create(depth-1); // Control evaluation 
     if (random.nextBoolean()) // evaluate left and right evenly distributed 
      return new BT<E>(null, temp, create(depth-1)); 
     else return new BT<E>(null, create(depth-1), temp); 

Обратите внимание, что созданное дерево будет скорее быть редким, чем плотная, из-за

if(finished) 
    if(random.nextBoolean()) 
     return new BT<E>(null); 

Вы можете захотеть сделать случайную величину в зависимости от числа путей тока.