使用 VB.NET 实现的简单二叉树

• 下载源代码 - 5.59 Kb

引言

二叉树是编程世界中最重要的数据结构之一。其基本定义可以如下给出（正如 Tenenbaum 的一本数据结构书中提到的）。“二叉树是一个有限元素的集合，它要么为空，要么被划分为三个不相交的子集。第一个子集包含一个称为树根的单一元素。另外两个子集本身是二叉树，分别称为原树的左子树和右子树。左子树或右子树可以为空，二叉树中的每个元素都称为节点。” 这个定义本身是递归的，可能听起来很晦涩。这个图表会让它更清楚。

对基本二叉树的定义存在无数的变体，每种变体都有各种应用。例如，堆是二叉树的一种实现。文件系统和数据库的各种底层数据结构都是堆。这个列表还在继续...

实现二叉树

在本文中，我们将看到一个非常简单的二叉树实现。在实现方面，二叉树是一种节点链表。那么，让我们看看如何定义一个节点。

    Class TreeNode
        Public Value As Object
        Public LeftNode As TreeNode
        Public RightNode As TreeNode
    End Class

在这里，我有一个名为 TreeNode 的类，其中包含 LeftNode 和 RightNode 成员，分别指向左子树和右子树，以及 Value 成员，其类型为 Object （可以保存任何内容）。我真的很希望用一个结构来表示节点而不是类（就像在 C 语言时代那样），但在 VB.NET 中，一个结构不能包含其自身类型的成员。

创建树本身也很简单。首先，创建根节点，然后创建右子树和左子树。在我们的例子中，我们创建了一个由随机生成的整数组成的简单树。让我们看看这是如何完成的。

我们将 Tree 表示为一个类，它公开了几个操作它的方法。请注意，树的根是私有的，操作树的唯一方法是通过 Tree 类公开的方法。

Public Class Tree
    Private _root As TreeNode
    
    ..
    ..
End Class
        

要创建新树，我们在类构造函数中创建一个新节点并将其标记为根。

Sub New(ByVal rootValue As Object)
   _root = GetNode(rootValue)
End Sub

Private Function GetNode(ByVal value As Object) As TreeNode
    Dim node As New TreeNode()
    node.Value = value
    Return node
End Function
        

向树中添加节点

向树中添加节点需要更复杂一些的操作，因为在有根节点的情况下，一个节点只能在一个位置上。我们需要从根节点开始，并将根节点的值与新节点的数值进行比较。如果新节点的值较小，则它属于左子树；如果较大，则它属于右子树。这些比较会一直进行到树的底部，此时无法继续进行。此时，将进行最后一次比较，并将节点添加到最终节点的左子树或右子树中。在我的实现中，我不支持重复节点。如果在添加节点的过程中，其值等于正在比较的节点的值，则不将其添加到树中。这是代码片段

Public Sub AddtoTree(ByVal value As Object)
    Dim currentNode As TreeNode = _root
    Dim nextNode As TreeNode = _root

    While currentNode.Value <> value And Not nextNode Is Nothing
        currentNode = nextNode
        If nextNode.Value < value Then
            nextNode = nextNode.RightNode
        Else
            nextNode = nextNode.LeftNode
        End If
    End While
    If currentNode.Value = value Then
        Console.WriteLine("Duplicate value (" & _
             value & "). Node was not inserted")
    ElseIf currentNode.Value < value Then
        currentNode.RightNode = GetNode(value)
    Else
        currentNode.LeftNode = GetNode(value)
    End If
End Sub
        

请注意，在上面的示例中，我直接对节点值本身进行比较。这是基于所有节点代表简单整数的假设。理想情况下，每个节点应该有一个 Key ，并且比较应该在该字段上进行。在实现方面，这个 Key 对象应该实现 IComparable 接口，以便树可以包含任何类型的对象（比较将是透明的）。

遍历树

遍历树涉及访问树中的所有节点。您可以通过三种方式实现此目的

• 后序遍历
• 前序遍历
• 中序遍历

这些方法中的每一种都非常有用，并且都有其自身的应用。在我们的示例中，我们将考虑中序遍历。如下所述，这是一个递归过程

1. 遍历左子树
2. 访问根节点
3. 遍历右子树

此遍历的意义在于，我们以排序的方式访问所有节点。因此，在我们的情况下，通过简单的中序遍历，我们将获得排序的整数列表！

Private Sub inOrderTraverse(ByVal node As TreeNode)
    If Not node Is Nothing Then
        inOrderTraverse(node.LeftNode)
        Console.WriteLine(node.Value)
        inOrderTraverse(node.RightNode)
    End If
End Sub
            

这是一个示例输出

结论

在本文中，我们了解了如何使用 VB.NET 轻松实现简单的二叉树。来自 C 语言世界的开发者会注意到这里没有使用 malloc、sizeof 和 free 。这是因为我将内存分配和垃圾回收的任务留给了 .NET 运行时（这是最好的部分）。

我将本文保持得非常简单，没有考虑更复杂的操作，例如删除和枚举。此外，二叉树本身就为算法和实现开辟了无数的途径。我真的很想在不久的将来写很多关于这些算法的文章！