C语言中文网教程离线版下载（PDF下载）

首页 > Go语言教程 > Go语言接口阅读：402

Go语言二叉树数据结构的应用

< 上一页示例：实现有限状态机（FSM） Go语言包（package）下一页 >

树型结构（Tree）是一种重要的非线性数据结构，它为计算机应用中出现的具有层次关系的数据提供了一种有效的表示方法，比如文件目录结构、源程序语法结构等。

树的定义和基本术语

树是 n(n>=0) 个节点的有限集合 T。在任意一棵非空树中满足如下两个条件：

有且仅有一个根节点（Root）。
当 n>1 时，其余节点可分为 m(m>=0) 个互不相交的有限集合 T1，T2，……，Tm，其中每一个集合本身又都是一棵树，并且称为根的子树（Subtree），如下图所示。

图：树型结构

由上图可知，树的定义是递归的，树是一种递归数据结构。树的这种定义为树的递归处理带来了很大方便，本节举例中几乎所有对树的处理都采用了递归算法。

在了解树型结构时，还有几个基本概念非常重要，必须要掌握：

节点的度：树中每个节点具有的子树数，或后继节点数称为该节点的度。
树的度：树中所有节点的度的最大值称为树的度。
分支节点：度大于 0 的节点称为分支节点或非终端节点。
叶子节点：度为 0 的节点称为叶子节点或终端节点。
儿子节点：一个节点的后继称为该节点的儿子节点。
父亲节点：一个节点称为其后继节点的父亲节点。
子孙节点：一个节点的所有子树中的节点称为该节点的子孙节点。
祖先节点：从根节点到达一个节点的路径上，通过的所有节点称为该节点的祖先节点。
兄弟节点：具有同一父亲的节点相互称为兄弟节点。
节点的层数：树是一种层次结构，根节点为第一层，其儿子节点为第二层，以此类推可以得到每个节点的层数。
树的深度：树中节点的最大层数称为树的深度或高度。
森林：0 个或多个不相交的树的集合称为森林。

二叉树简介

二叉树（Binary Tree）是一种特殊的树型结构，二叉树中每个节点至多有两棵子树，称为左子树、右子树。即二叉树中不存在度大于 2 的节点，且两棵子树有左右之分，次序不能任意颠倒。

除了这些基本特征外，还有如下一些特殊的二叉树。

满二叉树：在一棵二叉树中，若第 i 层的节点数为 2i-1 时，则称此层的节点数是满的，当二叉树中的每一层都是满的，则称此二叉树为满二叉树。
完全二叉树：在一棵二叉树中，除最后一层外，若其余各层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干个节点，则此二叉树被称为完全二叉树。

二叉树的链接存储结构

二叉树的存储方法有顺序存储、链接存储和线索树存储等几种存储方法，顺序存储是使用数组来完成，而链接存储和线索树存储都使用了链表来完成。本节在二叉树的应用举例中使用了链接存储法。为什么不使用线索树呢？原因前面讲了，树型结构的主要特征是递归，所以对树的所有操作都使用递归算法来实现，而线索树恰恰是使用非递归算法来加速遍历速度。

节点定义

在二叉树的链接存储结构中，通常采用的方法是：每个节点设置三个域，即值域、左指针域和右指针域，其结构如下图所示。

图：二叉树链接存储结构

其中 Data 表示值域，用于存储放入节点中的数据元素，Left 和 Right 分别表示左指针域和右指针域，用以分别存储左孩子和右孩子节点的指针地址。

链接存储的指针类型和节点定义如下：

type Node struct {
    Left *Node
    Data interface{}
    Right *Node
}

这里的 Data 字段可以是任意基本数据类型，如 int、float、string 等。链表所有节点的 Data 字段类型一致，比如同为 int 型或同为 string 型。在本节的应用举例中，二叉树节点的 Data 字段将被设置成空接口 interface{}，这样二叉树的叶子节点将能够存储不同类型的数据，比如一个节点为 int 型，其他节点可以为 string 型等。

接口定义

二叉树的应用处理功能主要包括：二叉树新节点的创建、初始化；二叉树的输出、度的计算、叶子节点统计等基本操作；二叉树的前序、中序、后序遍历等。针对这些功能本例共定义了三个接口：Initer、Operater 和 Order。

1) Initer 接口。当为二叉树创建了一个新节点时，Initer 接口提供了方法 SetData() 可以对节点的 Data 字段进行初始化。

Initer 接口定义如下：

type Initer interface {
SetData (data interface{})
}

2) Operater 接口。当已经生成了一个二叉树时，可以使用 Operater 接口提供的三个方法：PrintBT()、Depth() 和 LeafCount()，对二叉树进行输出、深度计算和叶子统计等基本操作。

Operater 接口定义如下：

type Operater interface {
    PrintBT()
    Depth() int
    LeafCount() int
}

3) Order 接口。对二叉树的遍历是一个重要的功能，这些功能在接口 Order 中实现，接口 Order 中共定义了三个方法：PreOrder()、InOrder() 和 PostOrder()，分别可以实现前序遍历、中序遍历和后序遍历。

Order 接口的定义如下：

type Order interface {
    PreOrder()
    InOrder()
    PostOrder()
}

可以看到，在定义接口时，接口中的方法只需声明原型，而并不需在此实现。这些方法的实现可以在其他 Go 包文件中实现，或者直接由其他用户提供。

接口的意义也在于此，即同一个接口可以有不同的实现方法，甚至由不同的人去完成。所以，Go语言是软件工程类的高级程序设计语言。

方法的实现

通过接口的概念知道接口是方法的组合，而在定义接口时不必马上实现方法，方法可由设计者自己或交由其他人另外单独设计。本例三个接口中共有 7 个方法，在此分别介绍它们的实现算法。

1) SetData 方法。SetData() 通过空接口 interface{}，可以将任意类型数据赋值给二叉树节点 Node 的 Data 字段，实现二叉树对任意数据类型的存储。

SetData 方法的定义如下：

func (n *Node) SetData(data interface{}) {
n.Data = data
}

2) PrintBT 方法。PrintBT() 调用底层函数 PrintBT()，输出一个给定二叉树的嵌套括号表示。

PrintBT 方法的定义如下：

func (n *Node) PrintBT() {
PrintBT(n)
}

3) Depth 方法。Depth() 调用底层函数 Depth()，返回二叉树的深度。

Depth 方法的定义如下：

func (n *Node) Depth() int {
return Depth(n)
}

4) LeafCount 方法。LeafCount() 调用底层函数 LeafCount()，返回二叉树的叶子节点数。

LeafCount 方法的定义如下：

func (n *Node) LeafCount() int {
return LeafCount(n)
}

5) PreOrder 方法。PreOrder() 调用底层函数 PreOrder() 对二叉树进行前序遍历。

PreOrder 方法的定义如下：

func (n *Node) PreOrder() {
PreOrder(n)
}

6) InOrder 方法。InOrder() 调用底层函数 InOrder() 对二叉树进行中序遍历。

InOrder 方法的定义如下：

func (n *Node) InOrder() {
InOrder(n)
}

7) PostOrder 方法。PostOrder() 调用底层函数 PostOrder() 对二叉树进行后序遍历。

PostOrder 方法的定义如下：

func (n *Node) PostOrder() {
PostOrder(n)
}

底层函数设计

在面向对象程序设计中，上层方法的功能实现还要依赖底层函数，本例中大部分方法也是这样，现将所有底层函数一一列举如下。

1) NewNode 函数。NewNode() 按照链接存储方式生成一个新的二叉树节点，参数 left 指向左指针域，参数 right 指向右指针域。

NewNode 函数的定义如下：

func NewNode(left, right *Node) *Node {
return &Node{left, nil, right}
}

2) PrintBT 函数。PrintBT() 用于输出一个给定二叉树的嵌套括号表示，采用递归算法：首先输出根节点，然后再依次输出左子树和右子树，在输出左子树前打印输出左括号“(”，在输出右子树后打印输出右括号“)”；另外，依次输出的左、右子树要至少有一个不为空，若都为空就不必输出了。

PrintBT 函数的定义如下：

func PrintBT(n *Node) {
    if n != nil {
        fmt.Printf("%v", n.Data)
        if n.Left != nil || n.Right != nil {
            fmt.Printf("(")
            PrintBT(n.Left)
            if n.Right != nil {
                fmt.Printf(",")
            }
            PrintBT(n.Right)
            fmt.Printf(")")
        }
    }
}

3) Depth 函数。Depth() 用于计算二叉树的深度，采用递归算法：若一棵二叉树为空，则其深度为 0；否则，其深度等于左子树或右子树的最大深度加 1。

Depth 函数的定义如下：

func Depth(n *Node) int {
    var depleft, depright int
    if n == nil {
        return 0
    } else {
        depleft = Depth(n.Left)
        depright = Depth(n.Right)
        if depleft > depright {
            return depleft + 1
        } else {
            return depright + 1
        }
    }
}

4) LeafCount 函数。LeafCount() 用于统计二叉树叶子节点数，采用递归算法：若一棵二叉树为空，则其叶子节点数为 0；若一棵二叉树的左、右子树均为空，则其叶子节点数为 1；否则叶子数等于左子树与右子树叶子总数之和。

LeafCount 函数的定义如下：

func LeafCount(n *Node) int {
    if n == nil {
        return 0
    } else if (n.Left == nil) && (n.Right == nil) {
        return 1
    } else {
        return (LeafCount(n.Left) + LeafCount(n.Right))
    }
}

5) PreOrder 函数。PreOrder() 可以对二叉树进行前序遍历，采用递归算法：按照先访问根节点，再访问左子树，最后访问右子树的次序访问二叉树中的所有节点，且每个节点仅访问一次。

PreOrder 函数的定义如下：

func PreOrder(n *Node) {
    if n != nil {
        fmt.Printf("%v", n.Data)
        PreOrder(n.Left)
        PreOrder(n.Right)
    }
}

6) InOrder 函数。InOrder() 可以对二叉树进行中序遍历，采用递归算法：按照先访问左子树，再访问根节点，最后访问右子树的次序访问二叉树中的所有节点，且每个节点仅访问一次。

InOrder 函数的定义如下：

func InOrder(n *Node) {
    if n != nil {
        PreOrder(n.Left)
        fmt.Printf("%v", n.Data)
        PreOrder(n.Right)
    }
}

7) PostOrder 函数。PostOrder() 可以对二叉树进行后序遍历，采用递归算法：按照先访问左子树，再访问右子树，最后访问根节点的次序访问二叉树中的所有节点，且每个节点仅访问一次。

PostOrder 函数的定义如下：

func PostOrder(n *Node) {
    PreOrder(n.Left)
    PreOrder(n.Right)
    fmt.Printf("%v", n.Data)
}

二叉树基本应用测试

前面介绍了二叉树链接存储结构，以及节点定义、接口定义、方法实现和底层函数设计，并在包 btree 中实现。接下来将利用这些知识实现几个二叉树的基本应用，包括二叉树的创建、基本操作和遍历。

二叉树创建

二叉树的创建过程一般如下：

首先调用 NewNode() 函数创建根节点，再调用 SetData() 方法初始化根节点。
使用同样的方法创建左子树和右子树，并将左、右子树链接到根节点上。
如果左、右子树有叶子节点，则插入叶子节点并和左、右子树建立链接。

【示例 1】二叉树的建立，本例将演示如何使用 Initer 接口实现根节点的初始化。

// 二叉树的建立
package main

import(
    "fmt"
    "btree"
)

func main() {
    //创建根节点
    root := NewNode(nil, nil)
    var it Initer
    it = root
    it.SetData("root node")
    //创建左子树
    a := NewNode(nil, nil)
    a.SetData("left node")
    al := NewNode(nil, nil)     //左叶子节点
    al.SetData(100)
    ar := NewNode(nil, nil)     //右叶子节点
    ar.SetData(3.14)
    a.Left = al
    a.Right = ar
    //创建右子树
    b := NewNode(nil, nil)
    b.SetData("right node")
    root.Left = a
    root.Right = b
    root.PrintBT()
}

编译并运行该程序，输出结果为：

root node (left node ( 100,3.14 ),right node)

通过输出结果可以看出，在示例中首先创建了根节点 root node，然后创建左子树 left node 和右子树 right node。左子树有两个叶子节点，左叶子的值为 int 型 "100"，右叶子的值为 float 型 "3.14"。即该二叉树可以存储不同类型的值，这些都是由空接口 interface{} 实现的。

二叉树基本操作

对一个已存在的二叉树的基本操作包括二叉树的输出、深度计算、叶子数统计等，在下面将演示如何使用 Operater 接口实现这些基本操作。

【示例 2】二叉树的基本操作。

// 二叉树的基本操作
package main

import(
    "fmt"
    "btree"
)

func main() {
    //创建二叉树
    root := NewNode(nil, nil)
    root.SetData("root node")
    a := NewNode(nil, nil)
    a.SetData("left node")
    al := NewNode(nil, nil)
    al.SetData(100)
    ar := NewNode(nil, nil)
    ar.SetData(3.14)
    a.Left = al
    a.Right = ar
    b := NewNode(nil, nil)
    b.SetData("right node")
    root.Left = a
    root.Right = b
    // 使用 Operater 接口实现对二叉树的基本操作
    var it Operater
    it = root
    it.PrintBT()
    fmt.Println()
    fmt.Println("The depths of the Btree is:", it.Depth())
    fmt.Println("The leaf counts of the Btree is:", it.LeafCount())
}

编译并运行该程序，输出结果为：

root node ( left node (100,3.14),right node )
The depths of the Btree is: 3
The leaf counts of the Btree is: 3

通过输出结果可以看出，上面示例中二叉树的深度为 3，叶子节点数也为 3，这和验证结果完全一致。另外，对二叉树的操作还有査找、插入、删除节点等，大家可以在上面的基础上自行完成。

二叉树遍历

在二叉树的一些基本应用中，常常需要在树中查找具有某种特征的节点，或者对树中全部节点逐一进行某种处理，这就是二叉树的遍历（Traversing binary tree）。即如何按某条搜索路径访问树中的每个节点，使得每个节点均能被访问一次，而且仅被访问一次。

二叉树的遍历方法一般分为前序遍历、中序遍历和后序遍历，下面示例将演示如何使用 Order 接口实现二叉树的三种遍历。

【示例 3】二叉树的遍历。

// 二叉树的遍历
package main

import(
    "fmt"
    "btree"
)

func main() {
    //创建二叉树
    root := NewNode(nil, nil)
    root.SetData("root node")
    a := NewNode(nil, nil)
    a.SetData("left node")
    al := NewNode(nil, nil)
    al.SetData(100)
    ar := NewNode(nil, nil)
    ar.SetData(3.14)
    a.Left = al
    a.Right = ar
    b := NewNode(nil, nil)
    b.SetData("right node")
    root.Left = a
    root.Right = b
    // 使用 Order 接口实现对二叉树的基本操作
    var it Order
    it = root
    it.PreOrder()       //先序遍历
    fmt.Println()
    it.InOrder()        //中序遍历
    fmt.Println()
    it.PostOrder()      //后序遍历
}

编译并运行该程序，输出结果为：

root node left node 100 3.14 right node
left node 100 3.14 root node right node
left node 100 3.14 right node root node

通过输出结果可以看出，示例的三种遍历方法输出结果和验证结果完全一致。当然在对二叉树进行遍历的同时，用户也可以对树中的节点做各种处理，比如修改节点信息等。

< 上一页示例：实现有限状态机（FSM） Go语言包（package）下一页 >

优秀文章

精美而实用的网站，提供C语言、C++、STL、Linux、Shell、Java、Go语言等教程，以及socket、GCC、vi、Swing、设计模式、JSP等专题。

↑

Go语言二叉树数据结构的应用

树的定义和基本术语

二叉树简介

二叉树的链接存储结构

节点定义

接口定义

方法的实现

底层函数设计

二叉树基本应用测试

二叉树创建

二叉树基本操作

二叉树遍历

所有教程

优秀文章