复习数据结构二叉树

什么是二叉树？

二叉树（binary tree）是一种非线性数据结构，代表“祖先”与“后代”之间的派生关系，体现了“一分为二”的分治逻辑。与链表类似，二叉树的基本单元是节点，每个节点包含值、左子节点引用和右子节点引用。每个节点都有两个引用（指针），分别指向左子节点（left-child node）和右子节点（right-child node），该节点被称为这两个子节点的父节点（parent node）。当给定一个二叉树的节点时，我们将该节点的左子节点及其以下节点形成的树称为该节点的左子树（left subtree），同理可得右子树（right subtree）。

1/* 二叉树节点类 */
2class TreeNode {
3    int val;         // 节点值
4    TreeNode left;   // 左子节点引用
5    TreeNode right;  // 右子节点引用
6    TreeNode(int x) { val = x; }
7}

二叉树常见术语

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