Schreiben Sie eine Funktion, die die Anzahl der Blätter für einen bestimmten Baum zählt.

Question

Ein Baum ist eine abstrakte Datenstruktur, die aus Knoten besteht. Jeder Knoten hat nur einen übergeordneten Knoten und null oder mehr untergeordnete Knoten. Jeder Baum hat einen speziellen Knoten namens root, der keinen übergeordneten Knoten hat. Ein Knoten wird Blatt genannt, wenn er keine untergeordneten Knoten hat.
Ein Baum kann durch ein Array P dargestellt werden, wobei P [i] das Elternelement von Knoten i ist. Für den Wurzelknoten r ist P [r] gleich -1.

Schreiben Sie eine Funktion, die die Anzahl der Blätter für einen bestimmten Baum zählt.

Zum Beispiel hat der Baum, der durch das Array {1,3,1, -1,3} repräsentiert wird, 5 Knoten, 0 bis 4, wovon 3 Knoten Blätter sind (0,2 und 4, da alle anderen haben) mindestens einen Kindknoten).

using System; 

public class TreeArray { 
    public static int CountLeaves(params int[] tree) { 
     throw new NotImplementedException("Waiting to be implemented"); 
    } 
    public static void main(string[] args) { 
     Console.WriteLine(TreeArray.CountLeaves(1,3,1,-1,3)); 
    } 
} 

Lösung, die ich versuchte:

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 
using System.Diagnostics; 
using System.Collections; 

namespace Test 
{ 
    class CreateTreeFromParentArray 
    { 
    public static int INVALID_INDEX = -1; 
    public class TreeNode 
    { 
     internal object data; 
     public TreeNode left; 
     public TreeNode right; 
     public TreeNode(object data) 
     { 
      this.data = data; 
     } 
    } 
    public TreeNode root; 
    //Main Method 
    static void Main(string[] args) 
    { 
     CreateTreeFromParentArray solution = new 
     CreateTreeFromParentArray(); 

     int[] tree = { 1, 3, 1, -1, 3 }; 
     int LeaveCount = solution.CountLeaves(tree); //Count Leaf Leaves 

     Console.WriteLine("Leaf Node Count:" + LeaveCount); 
     Console.ReadKey(); 
    } 

    //Method for Counting Leaf Nodes 
    public int CountLeaves(params int[] tree) 
    { 
     CreateTreeFromParentArray solution = new 
    CreateTreeFromParentArray(); 
     TreeNode root = solution.constructTreeBottomUp(tree); //Created Tree 
     with given Array 

     if (root == null) { return 0; } 

     Stack<TreeNode> stack = new Stack<TreeNode>(); 
     TreeNode node = new TreeNode(root); 
     int count = 0; 

     while (!(root == null)) 
     { 
      if (root.left != null) stack.Push(root.left); 
      if (root.right != null) stack.Push(root.right); 

      if (root.left == null && root.right == null) 
      { 
       count++; 
      } 
      if (stack.Count == 0) 
      { 
       break; 
      } 
      else 
      { 
       root = stack.Pop(); 
      } 
     } 
     return count; 
    } 
    public TreeNode constructTreeTopDown(int[] parent) 
    { 
     int rootIndex = INVALID_INDEX; 
     for (int i = 0; i < parent.Length; i++) 
     { 
      if (parent[i] == -1) 
      { 
       rootIndex = i; 
       break; 
      } 
     } 
     if (rootIndex != INVALID_INDEX) 
     { 
      this.root = new TreeNode(rootIndex); 
     } 
     constructTreeTopDownRec(root, rootIndex, parent); 

     return root; 
    } 
    public TreeNode constructTreeBottomUp(int[] parent) 
    { 
     TreeNode[] constructed = new TreeNode[parent.Length]; 

     for (int i = 0; i < constructed.Length; i++) 
     { 
      constructNode(i, constructed, parent); 
     } 
     return root; 
    } 
    public void constructNode(int i, TreeNode[] constructed, int[] parent) 
    { 
     if (constructed[i] != null) 
     { 
      return; 
     } 
     if (parent[i] == -1) 
     { 
      constructed[i] = new TreeNode(i); 
      root = constructed[i]; 
      return; 
     } 

     if (constructed[parent[i]] == null) 
     { 
      constructNode(parent[i], constructed, parent); 
     } 

     constructed[i] = new TreeNode(i); 

     if (constructed[parent[i]] != null) 
     { 
      if (constructed[parent[i]].left == null) 
      { 
       constructed[parent[i]].left = constructed[i]; 
      } 
      else 
      { 
       constructed[parent[i]].right = constructed[i]; 
      } 
     } 
    } 
    public void constructTreeTopDownRec(TreeNode currentNode, int currentNodeValue, int[] parent) 
    { 
     int indexFirstChild = -1, indexSecondChild = -1; 
     for (int i = 0; i < parent.Length; i++) 
     { 
      if (currentNodeValue == parent[i]) 
      { 
       if (indexFirstChild == -1) 
       { 
        indexFirstChild = i; 
       } 
       else 
       { 
        indexSecondChild = i; 
        break; 
       } 
      } 
     } 

     if (indexFirstChild == -1) 
     { 
      return; 
     } 

     currentNode.left = new TreeNode(indexFirstChild); 
     constructTreeTopDownRec(currentNode.left, indexFirstChild, parent); 

     if (indexSecondChild != -1) 
     { 
      currentNode.right = new TreeNode(indexSecondChild); 
      constructTreeTopDownRec(currentNode.right, indexSecondChild, parent); 
     } 
    } 
} 
} 

aber das stimmt nicht

Answer 1

nur verfolgen, welche Indizes sind keine Blätter und das erste Mal, wenn Sie einen Index im Baum sehen, es zählt wie kein Blatt. Dann ist die Anzahl der Blätter nur die Anzahl der Knoten im Baum minus der Anzahl der Nicht-Blätter.

bool[] seen = new bool[tree.Length]; 
int notLeaves = 0; 
for(int i=0; i < tree.Length; i++){ 
    if(tree[i] == -1) { 
     continue; 
    } 
    if(!seen[tree[i]]){ 
     seen[tree[i]] = true; 
     notLeaves++; 
    } 
} 

return tree.Length - notLeaves; 

oder Linq mit

int leaves = tree.Length - tree.Where(n => n != -1).Distinct().Count();