代码之家  ›  专栏  ›  技术社区  ›  GurdeepS

关于二叉搜索树的问题

  •  0
  • GurdeepS  · 技术社区  · 14 年前

    http://netrsc.blogspot.com/2010/04/net-c-binary-tree.html

    我是不是认为 while (!Found)

    protected void Insert(T item)
    {
        TreeNode<T> TempNode = Root;
        bool Found=false;
        while (!Found)
        {
            int ComparedValue = TempNode.Value.CompareTo(item);
            if(ComparedValue<0)
            {
                if(TempNode.Left==null)
                {
                    TempNode.Left=new TreeNode<T>(item,TempNode);
                    ++NumberOfNodes;
                    return;
                }
                else
                {
                    TempNode=TempNode.Left;
                }
            }
            else if(ComparedValue>0)
            {
                if(TempNode.Right==null)
                {
                    TempNode.Right=new TreeNode<T>(item,TempNode);
                    ++NumberOfNodes;
                    return;
                }
                else
                {
                    TempNode=TempNode.Right;
                }
            }
            else
            {
                TempNode=TempNode.Right;
            }
        }
    }
    

    另外,对于查找和遍历方法,这些方法是如何工作的?如果遍历方法只从左分支返回,Find中的循环是否会再次执行?它怎么知道去执行正确的分支呢?

    protected IEnumerable<TreeNode<T>> Traversal(TreeNode<T> Node)
    {
        if (Node.Left != null)
        {
            foreach (TreeNode<T> LeftNode in Traversal(Node.Left))
                yield return LeftNode;
        }
        yield return Node;
        if (Node.Right != null)
        {
            foreach (TreeNode<T> RightNode in Traversal(Node.Right))
                yield return RightNode;
        }
    }
    

    谢谢

    2 回复  |  直到 14 年前
        1
  •  0
  •   voodoogiant    14 年前

    迭代树的一个例子是 Find 命令,它调用 Traversal 功能。

    foreach (TreeNode<T> Item in Traversal(Root))
    

    这个 穿越 函数将以从左到右的深度优先迭代返回树中的项。如果你看看 穿越 代码中,它在左侧递归调用自己,然后在右侧递归调用自己。

    返回iterable对象中的整个树,其中的项是从左到右按深度排序的。这个 查找 穿越 返回项的有序iterable, 查找 浏览列表寻找匹配项。 查找

        2
  •  0
  •   Jeff Mercado    14 年前

    不一定。它将只遍历应该添加插入节点的路径上的节点。有一些 return Found 变量到 true

    遍历方法返回左子树和右子树的节点。你应该注意它的用途 yield return 而不是平原 . 使用它会创建一个枚举器,其中生成的每个项都是在遍历时该枚举器将返回的内容。当它到达一个 生利 陈述。当从调用代码迭代到下一个值时,在该点继续执行,可能返回更多的值。

    Find将获取遍历的结果,如果在其中一个节点中找到,则返回存储的值。