nasıl çıktı 7 olmalıdır Burada İkili Ağacı

Question

import java.util.*; 

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

class BinaryTree 
{ 
    public static Node root; 
    BinaryTree() 
    { 
     root = null; 
    } 

    public int largestBST(Node root) 
    { 
       MinMax m = largest(root); 
      return m.size; 
    } 

    public MinMax largest(Node root) 
    { 
     if(root == null) 
     { 
      return new MinMax(); 
     } 

     MinMax leftMinMax = largest(root.left); 
     MinMax rightMinMax = largest(root.right); 

     MinMax m = new MinMax(); 

     if(leftMinMax.isBST == false || rightMinMax.isBST == false || (leftMinMax.max > root.data) || (rightMinMax.min <= root.data)) 
     { 
      m.isBST = false; 
      m.size = Math.max(leftMinMax.size , rightMinMax.size); 
     } 

     m.isBST = true; 
     m.size = leftMinMax.size + rightMinMax.size + 1; 

     m.min = root.left != null ? leftMinMax.min : root.data;//if left node is null take node as min or min of left 

     m.max = root.right != null ? rightMinMax.max : root.data;//if right node is null take node as max or max of right 

     return m; 
    } 

    class MinMax 
    { 
     int max,min; 
     boolean isBST; 
     int size; 
     MinMax() 
     { 
      max = Integer.MIN_VALUE; 
      min = Integer.MAX_VALUE; 
      isBST = false; 
      size = 0; 
     } 
    } 

    public static void main(String args[]) 
    { 
     BinaryTree bt = new BinaryTree(); 
     bt.root = new Node(25); 
     bt.root.left = new Node(18); 
     bt.root.right = new Node(50); 
     bt.root.left.left = new Node(19); 
     bt.root.left.right = new Node(20); 
     bt.root.right.left = new Node(35); 
     bt.root.right.right = new Node(60); 
     bt.root.right.left.right = new Node(40); 
     bt.root.right.left.left = new Node(20); 
     bt.root.right.right.left = new Node(55); 
     bt.root.right.right.right = new Node(70); 

     int size = bt.largestBST(root); 

     System.out.println("The size of largest BST is " + size); 
    } 
} 

en büyük BST boyutunu bulmak için ama bunun yerine ağaç düğümlerin sayısını gösteriyor yani 11. koduyla nesi var

? Sonra yapacağız böyle largestBST(Node root) yeniden yazma, ağacın maksimum derinliği bulmak isterseniz

Answer 1

:

public int largestBST(Node root) 
{ 
    if (root == null) { 
     return 0; 
    } 

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

Ne oluyor burada biz 1 + max(left subtree depth, right subtree depth) dönmek olmasıdır. Düğüm mevcut değilse, yinelemeyi durdurmak için 0 değerini döndürürüz. Bu 4 döndürecektir. ,

public int largestBST(Node root) 
{ 
    if (root == null) { 
     return 0; 
    } 

    return Math.max(countNodes(root.left), countNodes(root.right)); 
} 

public int countNodes(Node root) 
{ 
    if (root == null) { 
     return 0; 
    } 

    return 1 + countNodes(root.left) + countNodes(root.right); 
} 

Gördüğünüz gibi: büyük tarafından, ne olursa olsun derinliği, verilen kökünden başlayarak en düğümlerle alt ağacı kastediyorsan

, o zaman şu olsun bu çözüm değiştirebilir Şimdi özyineleme countNodes() yönteminde gerçekleşir ve largestBST() sadece maks ve sağ dallardan döndürür. Yineleme, önceki ile aynı prensibi izler. Bir düğüm yoksa bir 0 döndürülür ve var olan her düğüm için 1 eklenir. Sonuç şimdi 7 olacaktır.