[C#] Binary Search Tree(이진 탐색 트리) Add, Search, Remove

---

Add

            BinaryTree bt = new BinaryTree();

            Node root = bt.AddChild(bt.Root, 50); // Binary Search Tree(이진 탐색 트리)
            bt.AddChild(root, 30);
            bt.AddChild(root, 1);
            bt.AddChild(root, 35);
            bt.AddChild(root, 70);
            bt.AddChild(root, 60);
            bt.AddChild(root, 80);

        public Node AddChild(Node root, int data) // Binary Search Tree 이진 탐색 트리
        {
            if (root == null)
                return new Node(data);

            while (true)
            {
                if (data < root.Data)
                {
                    if (root.Left == null)
                        return root.Left = new Node(data);
                    else
                        root = root.Left;
                }

                else if (data > root.Data)
                {
                    if (root.Right == null)
                        return root.Right = new Node(data);
                    else
                        root = root.Right;
                }

                else
                    throw new InvalidOperationException("중복값이 존재합니다.");
            }
        }

---

Search

            Console.WriteLine(bt.Search(root, 35));
            Console.WriteLine(bt.Search(root, 60));
            Console.WriteLine(bt.Search(root, 100));

        public bool Search(Node root, int data)
        {
            while(true)
            {
                if (root == null)
                {
                    return false;
                }

                else if (data == root.Data)
                {
                    return true;
                }

                else if (data < root.Data)
                {
                    root = root.Left;
                }

                else if (data > root.Data)
                {
                    root = root.Right;
                }

                else throw new InvalidOperationException();
            }
        }

---

Remove 문제없이 작동하지만 코드를 더 간결화 해야함

            BinaryTree bt = new BinaryTree();
            Node root = bt.AddChild(bt.Root, 50);

            // 왼쪽
            bt.AddChild(root, 25);
            bt.AddChild(root, 10);
            bt.AddChild(root, 40);
            bt.AddChild(root, 45);
            bt.AddChild(root, 30);
            bt.AddChild(root, 35);

            // 오른쪽
            bt.AddChild(root, 75);
            bt.AddChild(root, 90);
            bt.AddChild(root, 100);
            bt.AddChild(root, 80);
            bt.AddChild(root, 85);

            bt.LevelOrder(root);
            root = bt.Delete(root, 50);
            bt.LevelOrder(root);

        public Node Delete(Node root, int data)
        {
            Node temp = root;
            Node prev = root;

            while (data != temp.Data)
            {
                if (temp == null)
                {
                    throw new InvalidOperationException();
                }

                else if (data < temp.Data)
                {
                    root = temp;
                    prev = temp;
                    temp = temp.Left;
                }

                else
                {
                    root = temp;
                    prev = temp;
                    temp = temp.Right;
                }
            }

            if (temp.Left == null && temp.Right == null) // 왼쪽 오른쪽 둘 다 비어있으면
            {
                Console.WriteLine("Delete: {0}", temp.Data);

                if (prev.Left == temp)
                {
                    prev.Left = null;
                    return Root;
                }

                else
                {
                    prev.Right = null;
                    return Root;
                }
            }

            else if (temp.Left != null && temp.Right != null) // 왼쪽 오른쪽 둘 다 값이 있으면
            {
                Node parent = temp;
                prev = temp;
                temp = temp.Right;

                while (temp.Left != null)
                {
                    prev = temp;
                    temp = temp.Left;
                }

                if (parent.Right != temp) // 바로 위 while문이 한번이라도 실행됐으면
                {
                    prev.Left = temp.Right;
                    temp.Right = parent.Right;
                }
                temp.Left = parent.Left;

                if (data < root.Data) // data가 root node보다 작으면
                {
                    root.Left = temp;
                    return Root;
                }

                else if (data > root.Data) // data가 root node보다 크면
                {
                    root.Right = temp;
                    return Root;
                }

                else // root node
                {
                    return temp;
                }
            }

            else // 왼쪽 오른쪽 둘중에 하나에만 값이 있으면
            {
                if (temp.Left != null) // 값이 왼쪽에만 있으면
                {
                    Console.WriteLine("Delete: {0}", temp.Data);

                    if (prev.Left == temp)
                    {
                        prev.Left = temp.Left;
                        return Root;
                    }

                    else
                    {
                        prev.Right = temp.Left;
                        return Root;
                    }
                }

                else // 값이 오른쪽에만 있으면
                {
                    Console.WriteLine("Delete: {0}", temp.Data);

                    if (prev.Left == temp)
                    {
                        prev.Left = temp.Right;
                        return Root;
                    }

                    else
                    {
                        prev.Right = temp.Right;
                        return Root;
                    }
                }
            }
        }