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

树的定义和基本术语

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

图：树型结构

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

二叉树简介

• 二叉树中每个节点最多有两棵子树，称为左子树、右子树；
• 左子树和右子树是有顺序的，有左右之分，次序不能随意颠倒；
• 即使某个节点只有一个子树，也要区分左右子树。

1) 斜树

图：左斜树和右斜树

2) 满二叉树

图：满二叉树

• 叶子只能出现在最下一层。
• 非叶子结点度一定是 2.
• 在同样深度的二叉树中，满二叉树的结点个数最多，叶子树最多。

3) 完全二叉树

图：完全二叉树

• 叶子结点只能出现在最下一层（满二叉树继承而来）。
• 最下层叶子结点一定集中在左部连续位置。
• 倒数第二层，如有叶子节点，一定出现在右部连续位置。
• 同样结点树的二叉树，完全二叉树的深度最小。

二叉树的链接存储结构

节点定义

图：二叉树链接存储结构

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

接口定义

• 二叉树新节点的创建、初始化；
• 二叉树的输出、度的计算、叶子节点统计等基本操作；
• 二叉树的前序、中序、后序遍历等。

1) Initer 接口

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

2) Operater 接口

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

3) Order 接口

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

方法的实现

1) SetData 方法

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

2) PrintBT 方法

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

3) Depth 方法

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

4) LeafCount 方法

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

5) PreOrder 方法

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

6) InOrder 方法

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

7) PostOrder 方法

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

底层函数设计

1) NewNode 函数

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

2) 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 函数

• 若一棵二叉树为空，则其深度为 0；
• 否则，其深度等于左子树或右子树的最大深度加 1。

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 函数

• 若一棵二叉树为空，则其叶子节点数为 0；
• 若一棵二叉树的左、右子树均为空，则其叶子节点数为 1；
• 否则叶子数等于左子树与右子树叶子总数之和。

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 函数

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

6) InOrder 函数

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

7) PostOrder 函数

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

二叉树基本应用测试

二叉树创建

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

// 二叉树的建立
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)

二叉树基本操作

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

import(
    "fmt"
    "btree"
)

func main() {
    //创建二叉树
    root := NewNode(nil,nil)
    root.SetData("root node")
    a := 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

二叉树遍历

// 二叉树的遍历
package main

import(
    "fmt"
    "btree"
)

func main() {
    //创建二叉树
    root := 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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!