Вставка бинарного дерева - PullRequest
Новая
       43

Вставка бинарного дерева

0 голосов
/ 04 апреля 2019

Привет. Я читал вставку значения в двоичном дереве, но мне трудно понять рекурсивный обход дерева с помощью Java. Вот код: 

// Java program to insert element in binary tree 
import java.util.LinkedList; 
import java.util.Queue; 
public class GFG { 

/* A binary tree node has key, pointer to  
left child and a pointer to right child */
static class Node { 
    int key; 
    Node left, right; 

    // constructor 
    Node(int key){ 
        this.key = key; 
        left = null; 
        right = null; 
    } 
} 
static Node root; 
static Node temp = root; 

/* Inorder traversal of a binary tree*/
static void inorder(Node temp) 
{ 
    if (temp == null) 
        return; 

    inorder(temp.left); 
    System.out.print(temp.key+" "); 
    inorder(temp.right); 
} 

/*function to insert element in binary tree */
static void insert(Node temp, int key) 
{ 
    Queue<Node> q = new LinkedList<Node>(); 
    q.add(temp); 

    // Do level order traversal until we find 
    // an empty place.  
    while (!q.isEmpty()) { 
        temp = q.peek(); 
        q.remove(); 

        if (temp.left == null) { 
            temp.left = new Node(key); 
            break; 
        } else
            q.add(temp.left); 

        if (temp.right == null) { 
            temp.right = new Node(key); 
            break; 
        } else
            q.add(temp.right); 
    } 
} 

// Driver code 
public static void main(String args[]) 
{ 
    root = new Node(10); 
    root.left = new Node(11); 
    root.left.left = new Node(7); 
    root.right = new Node(9); 
    root.right.left = new Node(15); 
    root.right.right = new Node(8); 

    System.out.print( "Inorder traversal before insertion:"); 
    inorder(root); 

    int key = 12; 
    insert(root, key); 

    System.out.print("\nInorder traversal after insertion:"); 
    inorder(root); 
} 
}

Может кто-нибудь объяснить, как работает этот метод inorder ()? По моему мнению, он никогда не должен завершаться, потому что он будет продолжать передавать нулевые значения снова и снова, и этот оператор возврата внутри, если цикл будет просто цикл из цикла, а не весь метод.

1 Ответ

3 голосов
/ 04 апреля 2019

inorder вызывается рекурсивно .

При любом вызове методов мы передаем сначала левый узел дерева, а второй правый узел.Однако эти вызовы вызовут метод для левого узла или правого узла - если узел имеет значение null, он возвращается рано.Дерево не бесконечно - поэтому в какой-то момент левый и правый узлы узла должны быть равны нулю, после чего метод возвращается рано и не продолжается.Следовательно, в какой-то момент рекурсия благополучно прервана.

Также if - это не цикл - это условный оператор.Вызов return внутри if возвращает весь метод, а не просто выходит из оператора if.То, что вы, должно быть, перепутали это с перерыв .

...