Si tratta di un albero binario bilanciato o sbilanciato?

0

Buon giorno, sono nuovo di java e nuovo in questo forum, ma richiedo un po 'di aiuto. Sto imparando java da solo e attualmente sto imparando gli alberi binari. Sono venuto un algoritmo che mi sta dando un piccolo problema. È un codice binario che inserisce fondamentalmente cinque nodi in una struttura ad albero e quindi attraversa l'albero. Il mio problema è che non capisco che tipo di struttura ad albero viene creata. È equilibrato o sbilanciato. Inoltre, come puoi dire se è l'uno o l'altro e ciò influenzerebbe il tipo di attraversamento che l'algoritmo sta conducendo. Puoi aiutare?

Ecco il codice:

import Prog1Tools.IOTools;

     class Node {
          Node left;
          Node right;
          int value;

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

     public class GeneralTreeTest {
       public static void main(String[] args) {

          // build a simple tree add 5 nodes to the tree
          Node root = new Node(5);
          System.out.println("Tree Example");
          System.out.println("Building tree with root value " + root.value);
          insert(root, 1);
          insert(root, 8);
          insert(root, 6);
          insert(root, 3);
          insert(root, 9);
          System.out.println("Traversing tree ");
          printOrder(root);

     }

     public static void insert(Node node, int value) {
          if (value < node.value) {
            if (node.left != null) {
              insert(node.left, value);
            } else {
              System.out.println(" Inserted " + value + " to left of "
                  + node.value);
              node.left = new Node(value);
            }
         } else if (value > node.value) {
            if (node.right != null) {
              insert(node.right, value);
            } else {

                 System.out.println(" Inserted " + value + " to right of "
                      + node.value);
                 node.right = new Node(value);
             }
          }
     }

     public static void printOrder(Node node) {
        if (node != null) {
           printOrder(node.left);
           System.out.println(" Traversed " + node.value);
           printOrder(node.right);
        }
     }
  }
    
posta xhenier 02.10.2016 - 02:46
fonte

1 risposta

4

Il tuo codice, come scritto, produrrà un albero simile a questo:

   5
  / \
 /   \
1     8
 \   /
  3 6
     \
      9

Un albero correttamente bilanciato assomiglia a questo:

     6
    / \
   /   \
  3     8
 / \     \
1   5     9

Quindi, no. questo non bilancia il tuo albero binario. Si tratta semplicemente di costruire un albero binario ordinato con un equilibrio che dipende totalmente dalla sequenza di inserimento.

A seconda dell'ordine delle chiamate insert() potresti facilmente finire per costruire:

1
 \
  3
   \
    5
     \
      6
       \
        8
         \
          9

Non hai codice per riequilibrare l'albero.

Ti consiglio di leggere questo:

link

    
risposta data 02.10.2016 - 06:33
fonte

Leggi altre domande sui tag