【算法】小白也能懂 · 第 10 节：二叉树基础与遍历

前面我们学习了数组、链表、栈、队列、哈希表和图，它们都是常用的数据结构。今天我们来认识一种在算法面试和实际开发中出场率极高的数据结构——二叉树（Binary Tree）。它是树结构中最简单也最重要的一种，理解了二叉树，再去学习更复杂的树（如红黑树、B 树）就会轻松很多。

1. 什么是二叉树

二叉树是一种层级结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

用一个生活中的例子来理解：想象一个公司的组织架构，CEO 是根节点，CEO 下面有两个副总裁（左子节点和右子节点），每个副总裁下面又可以有两个总监，以此类推。这就是一棵二叉树。

二叉树的几个基本概念：

• 根节点（Root）：最顶层的节点，没有父节点
• 叶子节点（Leaf）：没有子节点的节点
• 深度（Depth）：从根节点到该节点的边数
• 高度（Height）：从该节点到最远叶子节点的边数，树的高度等于根节点的高度

2. 二叉树的存储

在 C++ 中，二叉树通常用链表来表示。每个节点包含数据和指向左右子节点的指针：

structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(nullptr),right(nullptr){}};

创建一棵简单的二叉树：

// 1// / \ // 2 3// / \ // 4 5TreeNode*root=newTreeNode(1);root->left=newTreeNode(2);root->right=newTreeNode(3);root->left->left=newTreeNode(4);root->left->right=newTreeNode(5);