이진 트리 알고리즘

Question

다섯 개의 노드를 이진 트리에 삽입 한 다음 트리를 가로 지르는 다음 알고리즘을 발견했습니다.

어떤 종류의 트리 구조가 생성되고 있습니까? 균형이 맞지 않거나 균형이 맞지 않습니까? 어떻게 알 수 있니? 알고리즘이 수행하는 순회 유형에 영향을 미칠까요?

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); 
     } 
    } 
} 

Answer 1

그것은 균형 하나와 불균형 한인가?

균형 논리가 없습니다. 예를 들어 1,2,3을 삽입하면 모든 노드가 오른쪽으로 계속 진행됩니다. 예를 들어, AVL 균형 트리에서 1은 "왼쪽으로 회전"하고 2는 루트가되어 트리의 균형을 맞 춥니 다.

당신은 하나 또는 다른

당신은 당신의 트리에서 노드 데이터 구조의 포인터를 그릴 수 있는지 여부를 어떻게 알 수 있습니다.

이것은 알고리즘이 수행하는 순회 유형에 영향을 미칩니다.

하지 않아야합니다. 현재 왼쪽, 루트, 오른쪽으로 인쇄 중입니다. 어떤 종류의 이진 트리에도 동일한 순서가 적용됩니다.