基础扩展 | 20. 建立二叉树
学习Excel技术，关注微信公众号：
excelperfect
先看看下图1所示的一棵完全二叉树，图中标出了结点的内容、结点编号以及上下层子树之间的关系。
图1
可以看出，如果我们将根结点编号为1，下面各层依次从左至右顺序编号2、3、4、5、…等。这样，这棵二叉树的编号特征为：
- 第i个结点的左子树的编号为2*i
- 第i个结点的右子树的编号为2*i+1
我们使用数组来存储二叉树，如下图2所示。
图2
每个结点的数据结构如下图3所示。
图3
这样，不仅保存了结点数据，也建立了该结点与其左子树和右子树之间的联系。根据上文得出的二叉树的编号特征，可以得到每个结点的数据结构表如下图4所示。
图4
下面，我们来建立这棵二叉树。
声明常量，设定结点的数量：
Const MAXSIZE = 100
自定义类型来实现结点数据结构，Value存储结点数据，LeftChild存储该结点左子树编号，RightChild存储该结点右子树编号：
Type BinaryTreeNode
Value As String
LeftChild As Integer
RightChild As Integer
End Type
自定义类型实现二叉树数据结构，Node是结点数组，Root指定根结点编号：
Type BinaryTree
Node(MAXSIZE) As BinaryTreeNode
Root As Integer
End Type
声明代表二叉树的变量：
Public btTree As BinaryTree
根据图1，我们要建立的二叉树结点数组如下图5所示。
图5
声明并创建数组：
Dim arr As Variant
arr = Array("", "A", "B","C", "D", "E", "F", "G","H", "I", "J", "")
由于Array函数创建的数组下标从0开始，而我们创建的二叉树结点编号从1开始，因此将数组的第1项即下标为0的元素为空。
设置二叉树的根结点编号为1，即数据A所在的结点：
btTree.Root = 1
将数据赋值给各结点：
For i = 1 To UBound(arr)
btTree.Node(i).Value =arr(i)
Next i
确定各结点左子树和右子树：
For i = 1 To UBound(arr)
If btTree.Node(i).Value <> ""Then
If btTree.Node(2 * i).Value <>"" Then
btTree.Node(i).LeftChild = 2 * i
End If
If btTree.Node(2 * i + 1).Value <>"" Then
btTree.Node(i).RightChild = 2 * i + 1
End If
End If
Next i
创建二叉树的完整代码如下：
Const MAXSIZE = 100
Type BinaryTreeNode
Value As String
LeftChild As Integer
RightChild As Integer
End Type
Type BinaryTree
Node(MAXSIZE) As BinaryTreeNode
Root As Integer
End Type
Public btTree As BinaryTree
Sub CreatBinaryTree()
Dim arr As Variant
Dim i As Long
arr = Array("","A", "B", "C", "D", "E","F", "G", "H", "I", "J","")
btTree.Root = 1
For i = 1 To UBound(arr)
btTree.Node(i).Value= arr(i)
Next i
For i = 1 To UBound(arr)
IfbtTree.Node(i).Value <> "" Then
If btTree.Node(2* i).Value <> "" Then
btTree.Node(i).LeftChild = 2 * i
End If
If btTree.Node(2* i + 1).Value <> "" Then
btTree.Node(i).RightChild = 2 * i + 1
End If
End If
Next i
End Sub
代码的图片版如下：
上面讲解的是完全二叉树的创建，对于一般的二叉树，只需要将其按照完全二叉树编号，把不存在的结点设置为空。如下图6所示，其中浅色的结点不存在。
图6
此二叉树的结点数组如下图7所示。
图7
将上文代码中的数组使用图7所示的数组代替后，即可创建图6所示的二叉树。
可以看出，对于完全二叉树来说，使用这种顺序存储结构是比较合适的，然而对于一般的二叉树，则会有对存储空间的浪费，特别是对左右斜树来说，会造成极大的浪费。此时，可以使用链表结构来存储，我们会在后面的文章中再进行讲解。