Рекурсивная функция для расчета высоты BST - PullRequest
Новая
       25

Рекурсивная функция для расчета высоты BST

0 голосов
/ 03 октября 2019

BST выглядит следующим образом: 

    50 (Root 1)
   / \
  40  80 (Root 2)
 / \
20 41

Как вы можете видеть, есть 2 корня, с которыми я имею дело. Я пробовал следующий код, который возвращает высоту дерева из ROOT 1. Я не совсем точно знаю, как вернуть высоту из ROOT 2.

Любая помощь о том, как решить, будет принята с благодарностью. 

// Java program to find height of tree 

// A binary tree node 
class Node  
{ 
    int data; 
    Node left, right; 

    Node(int item)  
    { 
        data = item; 
        left = right = null; 
    } 
} 

class BinaryTree  
{ 
    Node root; 

    int maxDepth(Node node)  
    { 
        if (node == null) 
            return 0; 
        else 
        { 
            /* compute the depth of each subtree */
            int lDepth = maxDepth(node.left); 
            int rDepth = maxDepth(node.right); 

            /* use the larger one */
            if (lDepth > rDepth) 
                return (lDepth + 1); 
             else 
                return (rDepth + 1); 
        } 
    } 

    /* Driver program to test above functions */
    public static void main(String[] args)  
    { 
        BinaryTree tree = new BinaryTree(); 

        tree.root = new Node(1); 
        tree.root.left = new Node(2); 
        tree.root.right = new Node(3); 
        tree.root.left.left = new Node(4); 
        tree.root.left.right = new Node(5); 

        System.out.println("Height of tree is : " +  
                                      tree.maxDepth(tree.root)); 
    }

Ответы [ 2 ]

3 голосов
/ 03 октября 2019

Ваша функция поиска максимальной глубины работает правильно. Так что исправить эту проблему довольно просто. 

System.out.println("Height of tree is : " +  
                                  tree.maxDepth(tree.root));

В приведенной выше строке выводится высота дерева, начиная с корня. Но если бы вы начинали с «root 2», как вы его называете, вам нужно изменить эту строку, чтобы она начиналась с правильного узла. 

System.out.println("Height of tree is : " +  
                                  tree.maxDepth(tree.root.right));
0 голосов
/ 04 октября 2019

Добавление элемента в класс Tree должно производиться методом вставки. И мы можем сделать класс Node закрытым, он используется только классом BinaryTree.

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

public class BinaryTree {

    private class Node {

        private int value;
        private Node left;
        private Node right;

        private Node(int value) {
            this.value = value;
        }
    }

    private Node root;

    public void insert(int item) {

        var node = new Node(item);
        if (root == null) {
            root = node;
            return;
        }

        var current = root;

        while (true) {

            if (item < current.value) {
                if (current.left == null) {
                    current.left = node;
                    break;
                }
                current = current.left;

            } else {
                if (current.right == null) {
                    current.right = node;
                    break;
                }
                current = current.right;
            }
        }
    }

    public int height() {
       return height(root);
    }

    private int height(Node root) {
        if (root == null)
            return -1;

        if (isLeaf(root))
            return 0;

        return 1 + Math.max(height(root.left), height(root.right));
    }

    private boolean isLeaf(Node node) {
        return node.left == null && node.right == null;
    }
}

И чтобы использовать его, просто добавьте несколько значений и выведите высоту. С этим классом дерева легче вставить элемент. 

        BinaryTree tree = new BinaryTree();

        tree.insert(50);
        tree.insert(40);
        tree.insert(80);
        tree.insert(20);
        tree.insert(41);

        System.out.println(tree.height());
...