Среднее арифметическое бинарного дерева

Question

Не знаю, как найти среднее арифметическое элементов бинарного дерева, удается только разделить сумму элементов, но не знаю как найти количество элементов дерева.

public class BinaryTree
{
    public int Value;
    public BinaryTree Left = null;
    public BinaryTree Right = null;
    public BinaryTree(int value)
    {
        Value = value;
    }
    public void Add(int value)
    {
        if (value < Value)
        {
            if (Left == null) Left = new BinaryTree(value);
            else Left.Add(value);
        }
        else if (value > Value)
        {
            if (Right == null) Right = new BinaryTree(value);
            else Right.Add(value);
        }
    }
}
class BT
{
    // Зворотній обхід бінарного дерева
    public static void SimPrintTree(BinaryTree root)
    {
        if (root != null)
        {
            SimPrintTree(root.Left);
            SimPrintTree(root.Right);
            Console.Write(root.Value + "  ");
        }
    }


    public static void SimOutputEvenLeaves(BinaryTree root)
    {
        if (root != null)
        {
            SimOutputEvenLeaves(root.Left);
            // check for excistance of leaves:
            if (root.Left != null & root.Right != null)
            {
                if (root.Left.Value % 2 == 0 || root.Right.Value % 2 == 0)
                {
                    Console.Write($"{root.Value} ({root.Left.Value} + {root.Right.Value} = {root.Left.Value + root.Right.Value}); ");
                }
            }
            SimOutputEvenLeaves(root.Right);
        }
    }
    public static void SimPrintLeaves(BinaryTree root)
    {
        if (root != null)
        {
            SimPrintLeaves(root.Left);
            if (root.Left == null && root.Right == null)
            {
                Console.Write(root.Value + "  ");
            }
            SimPrintLeaves(root.Right);
        }
    }
    public static int addBT(BinaryTree root)
    {
        if (root == null)
        {
            return 0;
        }
        return (root.Value + addBT(root.Left) + addBT(root.Right));
    }
    static void Main()
    {
        Console.Write("Input the tree's range \n(it'll be also a root value): ");
        int rootValue = int.Parse(Console.ReadLine());
        int randomRange = 10;

        BinaryTree tree = new BinaryTree(rootValue);
        Random r = new Random();

        for (int i = 0; i < rootValue; i++)
        {
            int value = r.Next(-randomRange, randomRange);
            tree.Add(value);
        }
        Console.WriteLine("Symetric tree preview:");
        SimPrintTree(tree);
        Console.WriteLine("\nLeaves:");
        SimPrintLeaves(tree);
        Console.WriteLine("\nNodes which leaves sum is even:");
        SimOutputEvenLeaves(tree);

        addBT(tree);
        SimPrintTree(tree);
        int sum = addBT(tree);
        Console.WriteLine("Sum of all the elements is: " + (sum / (tree.Left.Value + tree.Right.Value)));
        Console.ReadLine();

    }
}

Answer 1

Давайте разобъём задачу на части.

Допустим, вы уже можете создавать бинарное дерево (я предпочитаю из массива чисел):

void Main()
{
    var arr = new object[] { 1, null, 2, 3 };
    var tree = CreateTree(arr);
}

// You can define other methods, fields, classes and namespaces here

private TreeNode CreateTree(object[] data)
{
    if (data == null || data.Length == 0)
        return null;

    TreeNode[] nodes = data.Select(x => x == null ? null : new TreeNode((int)x, null, null)).ToArray();

    int current = 0;
    bool left = true;

    for (int i = 1; i < nodes.Length; i++)
    {
        if (left)
        {
            nodes[current].left = nodes[i];
            left = false;
        }
        else
        {
            nodes[current].right = nodes[i];
            left = true;

            current++;
            while (current < nodes.Length && nodes[current] == null)
                current++;
        }
    }

    return nodes[0];
}

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

И умеете обходить дерево каким-то способом, абсолютно любым, ну чтобы попроще - рекурсивным:

public IList<int> InorderTraversal(TreeNode root)
{
    var result = new List<int>();

    if (root == null)
        return result;

    if (root.left != null)
        result.AddRange(InorderTraversal(root.left));
        
    result.Add(root.val);
    
    if (root.right != null)
        result.AddRange(InorderTraversal(root.right));

    return result;
}

То есть на выходе вы получите массив, у которого уже посчитать среднее арифметическое -- это тривиальная задача. Вот уже первое решение, самое очевидное, просто "в лоб" сведением незнакомой задачи к задаче, которую вы уже умеете решать.

Далее можно немного модифицировать алгоритм. Видели ли вы вот такую форму записи алгоритма обхода:

public IList<int> InorderTraversal(TreeNode root)
{
    var result = new List<int>();
    InorderTraversal(root, result);
    return result;
}

private void InorderTraversal(TreeNode node, List<int> result)
{
    if (node == null)
        return;

    if (node.left != null)
        InorderTraversal(node.left, result);
        
    result.Add(node.val);

    if (node.right != null)
        InorderTraversal(node.right, result);
}

Вы можете поступить по аналогии и добавить переменную, хранящую сумму элементов массива и количество:

public class Solution
{
    public double InorderTraversal(TreeNode root)
    {
        var sum = 0;
        var count = 0;
        InorderTraversal(root, ref sum, ref count);
        return (double) sum / count;
    }

    private void InorderTraversal(TreeNode node, ref int sum, ref int count)
    {
        if (node == null)
            return;

        if (node.left != null)
            InorderTraversal(node.left, ref sum, ref count);

        sum += node.val;
        count++;

        if (node.right != null)
            InorderTraversal(node.right, ref sum, ref count);
    }
}

И это второй метод, без построения вспомогательного массива.

БЛОГ НА HUSL

Среднее арифметическое бинарного дерева

Ответы (1 шт):