二叉树

什么是二叉树

二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树” （left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找和二叉堆。

二叉树有哪些种类

二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：

• 空二叉树

• 只一个根结点的二叉树

• 只有左子树

• 只有右子树

• 完全二叉树

类型上有三种：

• 完全二叉村 -若二叉树的高度为 h，除了 h 层外，其它各层（1～h-1）的结点数都达到最大个数，第 h 层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

• 满二叉树 -除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

• 平衡二叉树 -平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

二叉树遍历

• 前序遍历 根左右

• 中序遍历 左根右

• 后序遍历 左右根

• 层次遍历 与对的层次遍历一样，基本思想从第一层开始，依次遍历每层

Golang 遍历代码示例

package main

import (
    "fmt"
)

type Node struct {
    Value       int
    Left, Right *Node
}

func (node *Node) Print() {
    fmt.Print(node.Value, " ")
}

func (node *Node) SetValue(v int) {
    if node == nil {
        fmt.Println("setting value to nil.node ignored.")
        return
    }
    node.Value = v
}

//前序遍历
func (node *Node) PreOrder() {
    if node == nil {
        return
    }
    node.Print()
    node.Left.PreOrder()
    node.Right.PreOrder()
}

//中序遍历
func (node *Node) MiddleOrder() {
    if node == nil {
        return
    }
    node.Left.MiddleOrder()
    node.Print()
    node.Right.MiddleOrder()
}

//后序遍历
func (node *Node) PostOrder() {
    if node == nil {
        return
    }
    node.Left.PostOrder()
    node.Right.PostOrder()
    node.Print()
}

//层次遍历(广度优先遍历)
func (node *Node) BreadthFirstSearch() {
    if node == nil {
        return
    }
    result := []int{}
    nodes := []*Node{node}
    for len(nodes) > 0 {
        curNode := nodes[0]
        nodes = nodes[1:]
        result = append(result, curNode.Value)
        if curNode.Left != nil {
            nodes = append(nodes, curNode.Left)
        }
        if curNode.Right != nil {
            nodes = append(nodes, curNode.Right)
        }
    }
    for _, v := range result {
        fmt.Print(v, " ")
    }
}

//层数(递归实现)
//对任意一个子树的根节点来说，它的深度=左右子树深度的最大值+1
func (node *Node) Layers() int {
    if node == nil {
        return 0
    }
    leftLayers := node.Left.Layers()
    rightLayers := node.Right.Layers()
    if leftLayers > rightLayers {
        return leftLayers + 1
    } else {
        return rightLayers + 1
    }
}

//层数(非递归实现)
//借助队列，在进行按层遍历时，记录遍历的层数即可
func (node *Node) LayersByQueue() int {
    if node == nil {
        return 0
    }
    layers := 0
    nodes := []*Node{node}
    for len(nodes) > 0 {
        layers++
        size := len(nodes) //每层的节点数
        count := 0
        for count < size {
            count++
            curNode := nodes[0]
            nodes = nodes[1:]
            if curNode.Left != nil {
                nodes = append(nodes, curNode.Left)
            }
            if curNode.Right != nil {
                nodes = append(nodes, curNode.Right)
            }
        }
    }
    return layers
}

// 二叉入插入操作
func insert(root *Node, data int) {
    if root == nil {
        root = &Node{Value: data}
        return
    }
    p := root
    for p != nil {
        if data > p.Value {
            if p.Right == nil {
                p.Right = &Node{Value: data}
                return
            }
            p = p.Right
        } else {
            if p.Left == nil {
                p.Left = &Node{Value: data}
                return
            }
            p = p.Left
        }
    }
}

// 二叉树删除操作
func delete(root *Node, data int) {
    p := root
    var pp *Node
    for p != nil && p.Value != data {
        pp = p
        if data > p.Value {
            p = p.Right
        } else {
            p = p.Left
        }
    }
    if p == nil {
        return
    }

    // 要删除的节点有两个子节点
    if p.Left != nil && p.Right != nil {
        minP := p.Right
        minPP := p
        for minP.Left != nil {
            minPP = minP
            minP = minP.Left
        }
        p.Value = minP.Value
        p = minP
        pp = minPP
    }
    // 删除节点是叶子节点或者只一个节点
    var child *Node
    if p.Left != nil {
        child = p.Left
    } else if p.Right != nil {
        child = p.Right
    } else {
        child = nil
    }

    if pp == nil {
        root = child
    } else if pp.Left == p {
        pp.Left = child
    } else {
        pp.Right = child
    }
}

func CreateNode(v int) *Node {
    return &Node{Value: v}
}

func main() {
    root := Node{Value: 3}
    root.Left = &Node{}
    root.Left.SetValue(0)
    root.Left.Right = CreateNode(2)
    root.Right = &Node{5, nil, nil}
    root.Right.Left = CreateNode(4)

    fmt.Print("\n前序遍历: ")
    root.PreOrder()
    fmt.Print("\n中序遍历: ")
    root.MiddleOrder()
    fmt.Print("\n后序遍历: ")
    root.PostOrder()
    fmt.Print("\n层次遍历: ")
    root.BreadthFirstSearch()
    fmt.Println("\n层数: ", root.Layers())
    fmt.Println("\n层数: ", root.LayersByQueue())

    insert(&root, 6)
    fmt.Print("\n中序遍历: ")
    root.MiddleOrder()

    delete(&root, 0)
    fmt.Print("\n中序遍历: ")
    root.MiddleOrder()
}

参考

• go语言实现--二叉树
• 二叉树