1

Тема: Бінарне дерево

Потрібна допомога з бінарним деревом. Я код для реалізації дерева знайшов в інтернеті і дописав ще свою функцію valCount яка має шукати к-сть входжень певного елемента в дереві. Але я зіткнувся з тим що в дерево не можна записати значення-дублікати(тобто дерево без повторів). Я пробував розібратися з функцією вставки Add елемента  в дерево але все марно. Допоможіть будь-ласка переробити дерево щоб в нього можна було записувати однакові елементи.

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

namespace Laba_7
{
    class Proga1
    {        
        // Розташування вузла відносно предка        
        public enum Side
        {
            Left,
            Right
        }       
        // Вузол бінарного дерева
        public class BinaryTreeNode<T> where T : IComparable
        {            
            public BinaryTreeNode(T data)
            {
                Data = data;
            }           
            public T Data { get; set; }
            public BinaryTreeNode<T> LeftNode { get; set; }            
            public BinaryTreeNode<T> RightNode { get; set; }           
            public BinaryTreeNode<T> ParentNode { get; set; }            
            // Розташування вузла відносно його предка          
            public Side? NodeSide =>
                ParentNode == null
                ? (Side?)null
                : ParentNode.LeftNode == this
                    ? Side.Left
                    : Side.Right;
            // Перетворення екземпляра класу в рядок        
            public override string ToString() => Data.ToString();
            public int ToInt()
            {
                return int.Parse(ToString());
            }
        }
        public class BinaryTree<T> where T : IComparable
        {            
            /// Корінь бінарного дерева            
            public BinaryTreeNode<T> RootNode { get; set; }
            public BinaryTreeNode<T> Add(BinaryTreeNode<T> node, BinaryTreeNode<T> currentNode = null)
            {
                if (RootNode == null)
                {
                    node.ParentNode = null;
                    return RootNode = node;
                }
                currentNode = currentNode ?? RootNode;
                node.ParentNode = currentNode;
                int result;
                return (result = node.Data.CompareTo(currentNode.Data)) == 0
                    ? currentNode
                    : result < 0
                        ? currentNode.LeftNode == null
                            ? (currentNode.LeftNode = node)
                            : Add(node, currentNode.LeftNode)
                        : currentNode.RightNode == null
                            ? (currentNode.RightNode = node)
                            : Add(node, currentNode.RightNode);
            }
            public BinaryTreeNode<T> Add(T data)
            {
                return Add(new BinaryTreeNode<T>(data));
            }
            public BinaryTreeNode<T> FindNode(T data, BinaryTreeNode<T> startWithNode = null)
            {
                startWithNode = startWithNode ?? RootNode;
                int result;
                return (result = data.CompareTo(startWithNode.Data)) == 0
                    ? startWithNode
                    : result < 0
                        ? startWithNode.LeftNode == null
                            ? null
                            : FindNode(data, startWithNode.LeftNode)
                        : startWithNode.RightNode == null
                            ? null
                            : FindNode(data, startWithNode.RightNode);
            }
            public void Remove(BinaryTreeNode<T> node)
            {
                if (node == null)
                {
                    return;
                }

                var currentNodeSide = node.NodeSide;
                //якщо у вузла немає підвузлів, можна його видалить
                if (node.LeftNode == null && node.RightNode == null)
                {
                    if (currentNodeSide == Side.Left)
                    {
                        node.ParentNode.LeftNode = null;
                    }
                    else
                    {
                        node.ParentNode.RightNode = null;
                    }
                }
                //якщо немає лівого, то правий ставим на місце видаляємого 
                else if (node.LeftNode == null)
                {
                    if (currentNodeSide == Side.Left)
                    {
                        node.ParentNode.LeftNode = node.RightNode;
                    }
                    else
                    {
                        node.ParentNode.RightNode = node.RightNode;
                    }

                    node.RightNode.ParentNode = node.ParentNode;
                }
                //якщо немає правого, то лівий ставимо на місце видаляємого
                else if (node.RightNode == null)
                {
                    if (currentNodeSide == Side.Left)
                    {
                        node.ParentNode.LeftNode = node.LeftNode;
                    }
                    else
                    {
                        node.ParentNode.RightNode = node.LeftNode;
                    }

                    node.LeftNode.ParentNode = node.ParentNode;
                }
                //якщо обидва дочірніх наявні, 
                //то правий стає на місце видаляємого,
                //а лівий вставляється в правий
                else
                {
                    switch (currentNodeSide)
                    {
                        case Side.Left:
                            node.ParentNode.LeftNode = node.RightNode;
                            node.RightNode.ParentNode = node.ParentNode;
                            Add(node.LeftNode, node.RightNode);
                            break;
                        case Side.Right:
                            node.ParentNode.RightNode = node.RightNode;
                            node.RightNode.ParentNode = node.ParentNode;
                            Add(node.LeftNode, node.RightNode);
                            break;
                        default:
                            var bufLeft = node.LeftNode;
                            var bufRightLeft = node.RightNode.LeftNode;
                            var bufRightRight = node.RightNode.RightNode;
                            node.Data = node.RightNode.Data;
                            node.RightNode = bufRightRight;
                            node.LeftNode = bufRightLeft;
                            Add(bufLeft, node);
                            break;
                    }
                }
            }
            public void Remove(T data)
            {
                var foundNode = FindNode(data);
                Remove(foundNode);
            }
            public void PrintTree()
            {
                PrintTree(RootNode);
            }
            private void PrintTree(BinaryTreeNode<T> startNode, string indent = "", Side? side = null)
            {
                if (startNode != null)
                {
                    var nodeSide = side == null ? "+" : side == Side.Left ? "L" : "R";
                    Console.WriteLine($"{indent} [{nodeSide}]- {startNode.Data}");
                    indent += new string(' ', 3);
                    //рекурсивний виклик для лівої і правої гілки
                    PrintTree(startNode.LeftNode, indent, Side.Left);
                    PrintTree(startNode.RightNode, indent, Side.Right);
                }
            }
            public int valCount(int val)
            {
                if (RootNode != null)
                {
                    return valCount(val, RootNode, 0);
                }
                return 0;
            }
            private int valCount(int val, BinaryTreeNode<T> startNode, int count)
            {
                if (startNode != null)
                {
                    if (startNode.ToInt() == val)
                    {
                        count++;
                    }
                    count = valCount(val, startNode.LeftNode, count);
                    count = valCount(val, startNode.RightNode, count);
                }
                return count;
            }
        }
        static void Main(string[] args)
        {
            var binaryTree = new BinaryTree<int>();           
            Random rng = new Random();
            for(int i = 0; i < 10; i++)
            {
                binaryTree.Add(rng.Next(20));
            }
            binaryTree.PrintTree();

            //Console.WriteLine(new string('-', 40));
            //binaryTree.Remove(3);
            //binaryTree.PrintTree();

            //Console.WriteLine(new string('-', 40));
            //binaryTree.Remove(8);
            //binaryTree.PrintTree();
            for (int i = 0; i < 20; i++)
            {
                int result = binaryTree.valCount(i);
                Console.WriteLine("Value = " + i + " Result = " + result);
            }    
            Console.ReadLine();
        }
    }
}

2 Востаннє редагувалося ch0r_t (05.05.2021 19:55:27)

Re: Бінарне дерево

Ймовірно ви погано шукали, ось:
https://www.geeksforgeeks.org/how-to-ha … arch-tree/
Там є приклад і для C#.

"A Better Solution is to augment every tree node to store count together with regular fields like key, left and right pointers.
Insertion of keys 12, 10, 20, 9, 11, 10, 12, 12 in an empty Binary Search Tree would create following..."

Подякували: Mirek70981