Действителен Generi c Двоичное дерево поиска с рекурсией - PullRequest
Новая
       42

Действителен Generi c Двоичное дерево поиска с рекурсией

5 голосов
/ 14 февраля 2020

Чтобы проверить достоверность Двоичного дерева поиска , я использую метод. Но метод всегда возвращает false при проверке с действительным Двоичным деревом поиска .

Демонстрационная версия здесь

код 

public class Program
{
    public static void Main()
    {
        BinarySearchTree<int> tree = new BinarySearchTree<int>();
        tree.Insert(2);
        tree.Insert(1);
        tree.Insert(3);
        Console.WriteLine(tree.IsValidBinarySearchTreeRecursive(tree.root).ToString()); // this is supposed to return true when tested against the simple tree above
    }
}

public class Node<T> where T : IComparable
{
    public Node<T> left;
    public Node<T> right;
    public T data;

    public Node(T data)
    {
        this.left = null;
        this.right = null;
        this.data = data;
    }
}

public class BinarySearchTree<T> where T : IComparable
{
    public Node<T> root;

    public BinarySearchTree()
    {
        this.root = null;
    }

    public bool Insert(T data)
    {
        Node<T> before = null;
        Node<T> after = this.root;

        while(after != null)
        {
            before = after;

            if(data.CompareTo(after.data) < 0)
                after = after.left;
            else if(data.CompareTo(after.data) > 0)
                after = after.right;
            else
                return false;
        }

        Node<T> newNode = new Node<T>(data);

        if (this.root == null)
        {
            this.root = newNode;
        }
        else
        {
            if(data.CompareTo(before.data) < 0)
                before.left = newNode;
            else
                before.right = newNode;
        }

        return true;
    }

    private bool _HelperForIsValidBinarySearchTreeRecursive(Node<T> node, T lower, T upper)
    {
        if (node == null)
            return true;

        T val = node.data;

        Type nodeType = typeof(T);

        if(nodeType.IsNumeric())
        {
            if(val.CompareTo(lower) <= 0)
                return false;
            if(val.CompareTo(upper) >= 0)
                return false;
        }
        else
        {
            if(lower != null && val.CompareTo(lower) <= 0)
                return false;
            if(upper != null && val.CompareTo(upper) >= 0)
                return false;
        }

        if(!_HelperForIsValidBinarySearchTreeRecursive(node.right, val, upper))
            return false;
        if(!_HelperForIsValidBinarySearchTreeRecursive(node.left, lower, val))
            return false;

        return true;
    }
    public bool IsValidBinarySearchTreeRecursive(Node<T> root)
    {
        Type nodeType = typeof(T);

        if(nodeType.IsNumeric())
            return _HelperForIsValidBinarySearchTreeRecursive(root, root.data, root.data);

        return _HelperForIsValidBinarySearchTreeRecursive(root, default(T), default(T));
    }
}

public static class StaticUtilities
{
    private static readonly HashSet<Type> NumericTypes = new HashSet<Type>
    {
        typeof(int),  typeof(double),  typeof(decimal),
        typeof(long), typeof(short),   typeof(sbyte),
        typeof(byte), typeof(ulong),   typeof(ushort),  
        typeof(uint), typeof(float)
    };
    public static bool IsNumeric(this Type myType)
    {
        return NumericTypes.Contains(Nullable.GetUnderlyingType(myType) ?? myType);
    }
}

1 Ответ

0 голосов
/ 14 февраля 2020

Ваша проблема здесь: 

if(val.CompareTo(lower) <= 0)
  return false; // you are always hitting this line
if(val.CompareTo(upper) >= 0)
  return false;

Поскольку ваш T val = node.data;, а ваш нижний и даже верхний - node.data с вашего первого звонка.

Так что, скорее всего, линия к исправить это 

return _HelperForIsValidBinarySearchTreeRecursive(root, root.data, root.data);

, так как я предполагаю, что ваше первоначальное намерение состояло в том, чтобы сравнить левое и правое с root?

Исходя из этого: https://www.geeksforgeeks.org/a-program-to-check-if-a-binary-tree-is-bst-or-not/

для вашего подхода к нумерации c ваше решение должно быть таким: 

/* false if this node violates the min/max constraints */
if (node.data < min || node.data > max) 
{ 
    return false; 
}

Таким образом, ваш код становится: 

if(val.CompareTo(lower) < 0)
  return false; // you are always hitting this line
if(val.CompareTo(upper) > 0)
  return false;

Затем вы столкнетесь с следующим препятствием вниз по линия. Мое предложение для решения было бы изменить это: 

private bool _HelperForIsValidBinarySearchTreeRecursive(Node<T> node, T lower, T upper)

На 

private bool _HelperForIsValidBinarySearchTreeRecursive(Node<T> node, Node<T> leftNode<T> right)

и позвонить так: 

_HelperForIsValidBinarySearchTreeRecursive(root, root.Left, root.Right)
...