二叉树基本讲解

一、什么是二叉树（基础概念）每个节点最多两个孩子：左孩子、右孩子最上面的节点叫根节点 root没有孩子的叫叶子节点遍历方式：前序、中序、后序、层序结构示意：1 / \ 2 3 / \ 4 5二、二叉树节点结构（C++）// 二叉树节点定义 struct TreeNode { int val; // 数据域 TreeNode* left; // 左孩子指针 TreeNode* right; // 右孩子指针 // 构造函数 TreeNode(int x) : val(x), left(NULL), right(NULL) {} };三、方式 1：手动创建二叉树（最基础）逐个 new 节点，手动连接左右孩子。// 创建一棵固定的二叉树 TreeNode* CreateTree() { // 根节点 TreeNode* root = new TreeNode(1); // 第二层 root-left = new TreeNode(2); root-right = new TreeNode(3); // 第三层 root-left-left = new TreeNode(4); root-left-right = new TreeNode(5); return root; }四、方式 2：根据数组创建二叉树（层序）LeetCode / 考试常用，数组按层序，-1表示空节点。例如数组：{1,2,3,4,5,-1,-1}#include queue using namespace std; TreeNode* CreateTreeByArray(int arr[], int n) { if (n == 0 || arr[0] == -1) return NULL; queueTreeNode* q; // 根节点 TreeNode* root = new TreeNode(arr[0]); q.push(root); int i = 1; while (!q.empty() i n) { TreeNod