C#-二叉搜索树包含/存在的方法 [英] C# - Binary Search Tree Contains/Is Present Method

问题描述

我真的很难让这个方法起作用，我想知道你是否能帮我。我一直在使用ref关键字，所以我将继续使用它。我一直在网上搜索，得到了一些帮助，但我已经尝试了我能想到的所有方法。我的Count和Height方法都起作用了，但是我真的很难让这个容器方法起作用。网络上的许多例子都显示了包含的公共和私有方法(我理解为什么)，但我相信它可以在一个方法中完成？当然，对吧？此外，请忽略RemoveItem方法，除非您希望抢先一步，这由您自行决定。我知道这很棘手，因为我在这周的早些时候已经查过了。

节点类-

    class Node<T> where T : IComparable
{
    private T data;
    public Node<T> Left, Right;

    public Node(T item)
    {
        data = item;
        Left = null;
        Right = null;
    }
    public T Data
    {
        set { data = value; }
        get { return data; }
    }

}

BinTree类-

 class BinTree<T> where T : IComparable
{
    protected Node<T> root;

    public BinTree()  //creates an empty tree
    {
        root = null;
    }
    public BinTree(Node<T> node)  //creates a tree with node as the root
    {
        root = node;
    }
   //I've deleted my preOrder, inOrder and postOrder methods just to save you some time

}

BSTree类-

 class BSTree<T> : BinTree<T> where T : IComparable
{  
    public BSTree()
    {
        root = null;
    }

    private void insertItem(T item, ref Node<T> tree)
    {
        if (tree == null)
        {
            tree = new Node<T>(item);

        }

        else if (item.CompareTo(tree.Data) < 0)
        {
            insertItem(item, ref tree.Left);
        }

        else if (item.CompareTo(tree.Data) > 0)
            insertItem(item, ref tree.Right);
    }

    public void InsertItem(T item)
    {
        insertItem(item, ref root);
    }

    public int Height(ref Node<T> tree)
    //Return the max level of the tree
    {
        if (tree == null)

            return 0;
        return (1 + Math.Max(Height(ref tree.Left), Height(ref tree.Right)));
    }


    public int Count(ref Node<T> tree)
    //Return the number of nodes in the tree
    {
        int counter = 0;

        if (tree == null)
        {
            return 0;
        }
        else if (tree.Left != null)
        {
            counter += Count(ref tree.Left);
            counter++;
        }

        if (tree.Right != null)
        {
            counter += Count(ref tree.Right);
            counter++;
        }
        return counter;
    }



    public Boolean Contains(T item, ref Node<T> tree)
    //Return true if the item is contained in the BSTree, false       //otherwise.
    {
       if (tree == null)
        {
            return false;
        }



       if (item.CompareTo(tree.Data) < 0)
        {
            return Contains(ref tree.Left);


            if (item.CompareTo(tree.Data) > 0)
            {
                return Contains(ref tree.Right);
                return true;
            }
        }
  }

    public void RemoveItem(T item) 
    {
    }

}

提前谢谢您。

推荐答案

要检查节点是否在树中，您有几个选项：

1. 您需要的节点在左子树中
2. 您需要的节点在右子树中
3. 您需要的节点就是您现在所在的位置

因此您的Contains方法应该如下所示：

public Boolean Contains(T item, ref Node<T> tree)
{
       if (tree == null)
       {
            return false;
       }

       if (tree.data == item)
       {
           return true;
       }  


       if (item.CompareTo(tree.Data) < 0)
       {
            return Contains(item, ref tree.Left);
       }
       if (item.CompareTo(tree.Data) > 0)
       {
            return Contains(item, ref tree.Right);
       }
  }

这篇关于C#-二叉搜索树包含/存在的方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！