基础扩展 | 25. 建立二叉树（使用链式存储实现）

我们详细讲解了遍历二叉树的概念和算法。

有了这些基础后，我们再来看生成二叉树的另一种实现方法，使用链式存储生成二叉树。要生成的二叉树如下图1所示。

图1

由于二叉树每个结点最多有两个子结点（孩子），因此可以使用包含两个指针域和一个数据域的结点结构，如下图2所示。

图2

每个结点的左指针指向其左子树结点，右指针指向其右子树结点，若其没有子结点，则为#，这样可以建立一个二叉链表，如下图3所示。

图3

下面，我们使用前序遍历来生成这棵二叉树。

BinaryTreeItem类

在VBE中，插入一个类模块，修改其名称为BinaryTreeItem，输入代码：

Public Value As Variant

Public LeftChild As BinaryTreeItem

Public RightChild As BinaryTreeItem

代码声明了代码结点数据及其左右指针的变量。

BinaryTree类

在VBE中，再插入一个类模块，修改其名称为BinaryTree，输入代码：

'头结点及结点个数

Public HeadNode As BinaryTreeItem

Public iLength As Integer

'初始化

Private Sub Class_Initialize()

initBinaryTree

End Sub

'初始化树

Sub initBinaryTree()

Set HeadNode = Nothing

iLength = 0

End Sub

'使用前序遍历生成二叉树

Function CreateBinaryTree(PreOrder1() As String * 1, i As Integer,length As Integer)

Dim NewNode As BinaryTreeItem

Dim ch As String * 1

Set NewNode = Nothing

If i <= length Then

ch = PreOrder1(i)

i = i + 1

If (ch <>"#") Then

Set NewNode = New BinaryTreeItem

NewNode.Value =ch

Set NewNode.LeftChild = CreateBinaryTree(PreOrder1, i, length)

Set NewNode.RightChild = CreateBinaryTree(PreOrder1, i, length)

End If

End If

Set CreateBinaryTree =NewNode

End Function

'前序遍历

Sub PreOrder(Node As BinaryTreeItem)

If (Not Node Is Nothing)Then

Debug.Print Node.Value

Call PreOrder(Node.LeftChild)

Call PreOrder(Node.RightChild)

End If

End Sub

代码中，CreateBinaryTree函数使用前序遍历来生成二叉树，返回所生成二叉树的根结点。在代码中，PreOrder过程用来打印生成的二叉树。

测试

使用下面的代码传递要生成的二叉树的结点数据，生成二叉树并以前序遍历方式打印二叉树的结点。

Sub test()

Dim btTree As BinaryTree

Dim str1() As String * 1

Dim i As Integer

Dim j As Integer

Dim iLen As Integer

Dim str2 As String

str2 ="ABDHIEJ#CFG"

iLen = Len(str2)

Set btTree = New BinaryTree

ReDim str1(1 To iLen) As String * 1

For i = 1 To iLen

str1(i) = Mid$(str2,i, 1)

Next i

btTree.initBinaryTree

Set btTree.HeadNode =btTree.CreateBinaryTree(str1, 1, UBound(str1) - LBound(str1) + 1)

Call btTree.PreOrder(btTree.HeadNode)

End Sub

运行test过程，在立即窗口中的结果如下图4所示。

图4

BinaryTree类模块代码的图片版如下：