При использовании этого метода вставки BST у меня есть только root в качестве вывода, почему? - PullRequest
Новая
       15

При использовании этого метода вставки BST у меня есть только root в качестве вывода, почему?

0 голосов
/ 21 июня 2019

Я пытаюсь вставить в двоичное дерево поиска, используя рекурсию, а затем распечатать его предварительно с использованием этого конкретного кода, но у меня есть только root в качестве вывода, почему? Это потому, что каждый стек времени (после каждого вызова) выскакивает таким образомудаление новых узлов? (это код Java) 

class node{
    int data;
    node left;
    node right;
    node(int key){
        data = key;
        left = right = null;
    }
}

class bst{
    node  root;
    node  temp;
    node  last;
    bst(){
        root =  null;
    }
    bst(int key){
        root = new node(key);
    }
    void Insert(node r,int value){
        temp = r;
        if(temp == null){
            if(root == null){
                root = new node(value);
                root.data = value;
                return;
            }
            temp = new node(value);
            temp.data = value;
            return;
        }
        else{
            if(value > temp.data){
                Insert(temp.right,value);
                return;
            }
            else{
                Insert(temp.left,value);
                return;
            }
        }
    }
}

class test{
        static void in_order(node root){
            if(root == null){
                return;
            }
            in_order(root.left);
            System.out.println(root.data+" ");
            in_order(root.right);
        }
    public static void main(String[] args){
        bst tree = new bst();
        tree.Insert(tree.root,45);
        tree.Insert(tree.root,39);
        tree.Insert(tree.root,12);
        tree.Insert(tree.root,59);
        test.in_order(tree.root);
    }
}

1 Ответ

0 голосов
/ 21 июня 2019

Причина, по которой вы получаете только одно целое число для выходных данных, заключается в том, что первый вызов Insert правильно добавляет элемент в дерево, но последующие вызовы не удаются, потому что вы перезаписываете элемент данных temp в null, когда вы рекурсивно вставить влево или вправо. Таким образом, вторая ветвь вашего первого оператора if никогда не будет выполнена.

Здесь вам на самом деле не нужна переменная temp. Общепринятым условием является наличие закрытой рекурсивной функции-члена, которая берет корень дерева в качестве параметра, возвращает измененное дерево и присваивает возвращаемое значение root в публичной функции-члене. 

public void Insert(int value) {
  root = Insert(root, value);
}

private node Insert(node r, int value) {
  if (r == null) {
    r = new node(value);
  }
  else if (value > r.data) {
    r.right = Insert(r.right, value);
  }
  else {
    r.left = Insert(r.left, value);
  }
  return r;
}

Это означает, что вам нужно только назвать его как tree.Insert(x).

...