数据结构-二叉树

定义

N 个有限元素的集合，在该集合中有一个根节点，每个节点可以有两个子节点，成为左子树和右子树。 像这种数据结构我们通常称之为树形结构，又因为他最多只有左右两个子节点的特点，我们称之为二叉树。

特殊类型 - 满二叉树

当二叉树只有度为 0 和 2 的节点，且度为 0 的节点都在同一层上。

特殊类型 - 完全二叉树

当二叉树深度为 k，且每一个节点都与深度为 k 的满二叉树中编号一一对应。
其特点是叶子节点只可能出现在层序最大的两层上。

特殊类型 - 二叉查找树

整体结构是二叉树，但是左子树的值小于根节点，右子树的值大于根节点

特殊类型 - 红黑树

红黑树是一种平衡二叉查找树

二叉树性质

1、二叉树第 i 层最多 2(i - 1) 个节点
2、深度为 h 的二叉树最多 2h - 1 个节点
3、度为 0 的节点数 = 度为 2 的节点数 + 1
4、对于一颗完全二叉树：（i >= 1）

• 当 i 为 1 时，该节点是根节点
• 当 i 大于 1 时，其父节点是 i/2
• 对于一个度为 2 的节点，其左子树为 2i，右子树为 2i+1（若 i>=0，则此处加 1）
• 最后一个非叶子节点 length / 2（若 i>=0，则此处减 1）

二叉树遍历

• 前序遍历：先访问根节点，然后遍历左子树，最后遍历右子树
• 中序遍历：先遍历左子树，然后访问根节点，最后遍历右子树
• 后续遍历：先遍历左子树，然后遍历右子树，最后访问根节点

前、中、后序遍历

package main

import "fmt"

type Node struct {
    Value string
    Left  *Node
    Right *Node
}

func Traversal(node *Node) {
    if node == nil {
        return
    }
    fmt.Println("前序遍历", node.Value)
    Traversal(node.Left)
    fmt.Println("中序遍历", node.Value)
    Traversal(node.Right)
    fmt.Println("后序遍历", node.Value)
}

func main() {
    node := &Node{
        Value: "A",
        Left: &Node{
            Value: "B",
            Left: &Node{
                Value: "D",
                Left:  nil,
                Right: nil,
            },
            Right: &Node{
                Value: "E",
                Left:  nil,
                Right: nil,
            },
        },
        Right: &Node{
            Value: "C",
            Left: &Node{
                Value: "F",
                Left:  nil,
                Right: nil,
            },
            Right: &Node{
                Value: "G",
                Left:  nil,
                Right: nil,
            },
        },
    }
    Traversal(node)
}