C#-二叉搜索树包含/存在的方法

人气:980 发布:2022-10-16 标签: c# binary-search-tree

问题描述

我真的很难让这个方法起作用,我想知道你是否能帮我。我一直在使用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) 
    {
    }

}

提前谢谢您。

推荐答案

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

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

因此您的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);
       }
  }

670