数据结构-二叉树

树（Tree）是一种非常重要的数据结构，它模拟了一种层级或者分支结构。在树结构中，数据以节点（Node）的形式存储，并且每个节点都可以有零个或多个子节点。
以下是树结构的基本概念：

• 节点的度（Degree）：节点的子树个数
• 树的度：树的所有节点中最大的度数
• 叶子节点（Leaf）：度为0的节点
• 子节点（Child）：一个节点下面的节点。
• 父节点（Parent）：有子节点的节点。
• 兄弟节点（Sibling）：共享同一父节点的节点。
• 深度（Depth）：树中节点的最大层数。
• 高度（Height）：节点的高度，叶节点的高度为1，其余节点的高度是其所有子节点高度的最大值加1。
• 路径（Path）：从一个节点到另一个节点的序列

二叉树
如果树中每个节点最多只能有两个子节点，这样的树就称之为二叉树

二叉树的重要特性

• 一个二叉树第i层的最大节点数为：2^(i-1),i>=1
• 深度为k的二叉树有最大节点总数为：2^k-1,k>=1
• 对任何非空的二叉树T，若n0表示叶子节点的个数，n2是度为2的非叶子节点个数，那么两者满足关系n0 = n2 + 1

完美二叉树
除了最下一层的叶子节点外，每层节点都有两个子节点，就构成了满二叉树

完全二叉树
除了二叉树最后一层，其他各层的节点数都达到最大个数，且最后一层从左向右的叶节点连续存在，只缺右侧若干节点。完美二叉树是特殊的完全二叉树