Вопрос о реализации бинарного дерева поиска - PullRequest
Новая
       33

Вопрос о реализации бинарного дерева поиска

0 голосов
/ 02 сентября 2018

Я пытаюсь изучить основы алгоритмов данных в C #, и при реализации нижеприведенного бинарного дерева поиска добавить в процесс, я застрял при понимании следующего: при вызове метода tree1.add(20); на На первой итерации цикла while current.Data имеет значение 50, а на второй итерации цикла значение того же current.Data меняется на 40. Почему значение current.Data не застряло на значении 50 после первой итерации и каков процесс, при котором current.Data получает значение 40? 

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

namespace BinarySearchTree
{
public class Node
{
    public int Data;
    public Node LeftChild;
    public Node RightChild;
}

public class BinarySearchTree
{
    public Node root;
    public BinarySearchTree()
    {
        root = null;
    }
    public void add(int data)
    {
        Node newNode = new Node();
        newNode.Data = data;
        if (root == null)
        {
            root = newNode;
        }
        else
        {
            Node current = root;
            Node parent;
            while (true)
            {
                parent = current;
                if (data < current.Data)
                {
                    current = current.LeftChild;
                    if (current == null)
                    {
                        parent.LeftChild = newNode;
                        break;
                    }
                }
                else
                {
                    current = current.RightChild;
                    if (current == null)
                    {
                        parent.RightChild = newNode;
                        break;
                    }
                }
            }
        }
    }
}


class Program
{
    static void Main(string[] args)
    {
        BinarySearchTree tree1 = new BinarySearchTree();
        tree1.add(50);
        tree1.add(40);
        tree1.add(60);
        tree1.add(20);
        tree1.add(45);
        tree1.add(55);
        tree1.add(65);

        Console.ReadLine();
    }
}
}

1 Ответ

0 голосов
/ 02 сентября 2018

Ответ лежит здесь: 

while (true)
{
   parent = current;
   if (data < current.Data)
   {
      current = current.LeftChild; // THIS LINE
      if (current == null)
      {
         parent.LeftChild = newNode;
         break;
      }
   }

Как вы видите, ток переоценивается, и теперь он является левым «потомком» самого себя. После первых 3 add использования дерево должно выглядеть так: 

     50
    /  \
  40   60

Итак, первая итерация - ток равен 50, вторая итерация идет влево (определение BST) и становится 40. Следующий итерационный ток будет содержать NULL, (левый потомок 40) и будет помещен внутри BST.

...