树

二叉树

二叉树是一种非线性数据结构，代表“祖先”和“后代”之间的派生关系，体现了"一分为二"的分治逻辑。数据元素和链表类似，二叉树的基本单元是节点，每个节点包含值，左子节点引用和右子节点引用。

type TreeNode struct {
    Val     int
    Left    *TreeNode
    Right  *TreeNode  
}

/*构造方法*/
func NewTreeNode(v int) *TreeNode {
    return &TreeNode{
        Val: v,
        Left: nil,
        Right: nil,
    }
}

每个节点都有两个引用指针，分别指向左子节点和右子节点，该节点被称为这两个子节点的“父节点”。当给定一个二叉树的节点时，我们将该节点的子节点树及其以下节点形成的树成为该节点的左子树，同理右节点对应的是右子树。

在二叉树中，除叶节点外，其他所有节点都包含子节点和非空子树。

二叉树常见术语

二叉树常见术语如图所示。

• 根节点（root node）：位于二叉树顶层的节点，没有父节点。
• 叶节点（leaf node）：没有子节点的节点，其两个指针均指向 None 。
• 边（edge）：连接两个节点的线段，即节点引用（指针）。
• 节点所在的层（level）：从顶至底递增，根节点所在层为 1 。
• 节点的度（degree）：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。
• 二叉树的高度（height）：从根节点到最远叶节点所经过的边的数量。
• 节点的深度（depth）：从根节点到该节点所经过的边的数量。

• 节点的高度（height）：从距离该节点最远的叶节点到该节点所经过的边的数量

  
  binary_tree_terminology.png