二叉树的常见类型1. 满二叉树定义除叶子节点外每个节点都有左右两个子节点所有叶子都在同一层。 特点深度为k节点总数\(2^k-1\)。2. 完全二叉树定义除最后一层外其余每一层节点都满最后一层节点从左往右连续排列中间不能有空缺。满二叉树一定是完全二叉树完全二叉树不一定是满二叉树。 数组存储二叉树一般用完全二叉树堆就是完全二叉树。3. 二叉搜索树 BST二叉查找树定义左子树所有节点值 根节点右子树所有节点值 根节点左右子树也满足 BST 规则。 特点查找、插入、删除平均\(O(\log n)\)最坏退化成链表\(O(n)\)。4. 平衡二叉树 AVL 树定义二叉搜索树任意节点左右子树高度差绝对值 ≤1。 特点保证平衡查找稳定\(O(\log n)\)插入删除会旋转调整。5. 红黑树RB-Tree定义一种自平衡二叉搜索树通过颜色规则维持平衡。 特点不严格要求高度差插入删除旋转次数更少Java TreeMap、C map 底层。6. 线索二叉树定义利用二叉树空指针域存放前驱、后继节点的指针线索。 作用不用栈就能遍历二叉树。7. 哈夫曼树最优二叉树定义带权路径长度 WPL 最小的二叉树。 特点没有度为 1 的节点用于哈夫曼编码、数据压缩。8. 二叉堆大根堆 / 小根堆底层是完全二叉树大根堆父节点 ≥ 子节点小根堆父节点 ≤ 子节点 用途优先队列、TopK 问题。9. 普通二叉树没有任何约束任意节点 0/1/2 个子节点是最基础的二叉树。C 语言 非递归求二叉树高度BFS 层序#include stdio.h #include stdlib.h // 二叉树结点定义 typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; // 队列结点BFS用 typedef struct QueueNode { TreeNode *data; struct QueueNode *next; } QueueNode; typedef struct Queue { QueueNode *front, *rear; } Queue; // 初始化队列 Queue* initQueue() { Queue *q (Queue*)malloc(sizeof(Queue)); q-front q-rear NULL; return q; } // 入队 void enQueue(Queue *q, TreeNode *node) { QueueNode *newNode (QueueNode*)malloc(sizeof(QueueNode)); newNode-data node; newNode-next NULL; if(q-rear NULL) { q-front q-rear newNode; } else { q-rear-next newNode; q-rear newNode; } } // 出队 TreeNode* deQueue(Queue *q) { if(q-front NULL) return NULL; QueueNode *temp q-front; TreeNode *res temp-data; q-front q-front-next; if(q-front NULL) q-rear NULL; free(temp); return res; } // 判断队列空 int isEmpty(Queue *q) { return q-front NULL; } // 非递归BFS求树高 int maxDepth(TreeNode* root) { if(root NULL) return 0; Queue *q initQueue(); enQueue(q, root); int depth 0; while(!isEmpty(q)) { int levelSize 0; // 统计当前层节点个数 QueueNode *p q-front; while(p ! NULL) { levelSize; p p-next; } // 遍历当前一层 for(int i 0; i levelSize; i) { TreeNode *cur deQueue(q); if(cur-left ! NULL) enQueue(q, cur-left); if(cur-right ! NULL) enQueue(q, cur-right); } depth; } free(q); return depth; }方法 2栈实现 DFS 迭代版C 语言// 栈元素保存节点当前深度 typedef struct StackNode { TreeNode *node; int depth; struct StackNode *next; } StackNode; typedef struct Stack { StackNode *top; } Stack; Stack* initStack() { Stack *s (Stack*)malloc(sizeof(Stack)); s-top NULL; return s; } void push(Stack *s, TreeNode *node, int d) { StackNode *newNode (StackNode*)malloc(sizeof(StackNode)); newNode-node node; newNode-depth d; newNode-next s-top; s-top newNode; } StackNode* pop(Stack *s) { if(s-top NULL) return NULL; StackNode *temp s-top; s-top s-top-next; return temp; } int isStackEmpty(Stack *s) { return s-top NULL; } int maxDepthDFS(TreeNode* root) { if(root NULL) return 0; Stack *s initStack(); push(s, root, 1); int maxD 0; while(!isStackEmpty(s)) { StackNode *cur pop(s); if(cur-depth maxD) maxD cur-depth; // 先压右再压左保证左先访问 if(cur-node-right) push(s, cur-node-right, cur-depth 1); if(cur-node-left) push(s, cur-node-left, cur-depth 1); free(cur); } free(s); return maxD; }考点总结BFS 层序逐层遍历每处理完一层深度 1空间最坏 O (n)DFS 栈栈存储(节点当前深度)弹出时更新最大深度时间复杂度\(O(n)\)每个结点访问一次空树高度 0DFS迭代栈版求二叉树高度 核心思想一句话用栈模拟递归的调用过程深度优先一条路走到最深处记录每一个节点所在的深度全程维护最大深度。拆解递归本质递归求高度max(左子树高度,右子树高度)1递归会一路往下访问遇到叶子节点才回溯。 递归是系统帮我们压栈、保存当前节点信息迭代 DFS 就是我们自己手动用栈保存【节点 当前深度】。栈里存什么栈元素不是单纯节点是一对信息(当前节点, 该节点的深度)根节点入栈深度 1每次弹出栈顶节点拿它的深度去更新全局最大深度maxD入栈顺序重点先压右孩子再压左孩子栈是后进先出所以弹出的时候先访问左子树再访问右子树和递归 DFS 顺序保持一致。遍历逻辑循环直到栈为空弹出栈顶节点更新最大深度如果有右孩子右孩子入栈深度 1如果有左孩子左孩子入栈深度 1举个简单例子1 / \ 2 3压入 (1,1)弹出 (1,1)maxD1压右 (3,2)压左 (2,2)弹出 (2,2)maxD22 无孩子弹出 (3,2)maxD23 无孩子 栈空返回最大深度 2和递归对比递归函数调用栈自动保存上下文迭代 DFS自己手动维护栈保存节点和深度避免递归栈溢出树很深的时候复杂度时间\(O(n)\)每个节点只访问一次空间\(O(n)\)最坏斜树栈里面存全部节点核心思路原来代码只记录最大深度值现在要输出到达最大深度的完整路径。 难点栈只存(节点,深度)不够还要记录这条路径上前面所有节点。两种思路栈保存(当前节点深度到这个节点的路径数组)简单直观适合理解回溯思路用一个全局 / 数组保存当前路径找到叶子时判断深度更新最长路径更省内存考研常用需求输出任意一条最长路径二叉树可能有多条最长路径这里输出第一条找到的思路讲解迭代 DFS 版沿用刚才的栈框架栈元素需要存三样东西结点指针当前结点的深度到达该结点的路径存结点值流程根节点入栈路径 [根值]深度 1弹出栈顶元素如果是叶子结点判断深度是不是大于当前记录的最大深度如果是更新最大深度保存这条路径不是叶子先压右孩子再压左孩子栈后进先出优先走左分支子节点路径 当前路径复制一份追加子节点的值栈空之后打印保存好的最长路径C 完整代码迭代 DFS输出最长路径#include stdio.h #include stdlib.h typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; // 栈元素节点、深度、路径数组、路径长度 typedef struct StackItem { TreeNode *node; int depth; int *path; // 保存路径值 int pathLen; struct StackItem *next; } StackItem; typedef struct Stack { StackItem *top; } Stack; Stack* initStack() { Stack *s (Stack*)malloc(sizeof(Stack)); s-top NULL; return s; } void push(Stack *s, TreeNode *node, int d, int oldPath[], int oldLen) { StackItem *newItem (StackItem*)malloc(sizeof(StackItem)); newItem-node node; newItem-depth d; newItem-pathLen oldLen 1; newItem-path (int*)malloc(sizeof(int) * newItem-pathLen); // 复制旧路径 for(int i 0; i oldLen; i) { newItem-path[i] oldPath[i]; } newItem-path[oldLen] node-val; newItem-next s-top; s-top newItem; } StackItem* pop(Stack *s) { if(s-top NULL) return NULL; StackItem *tmp s-top; s-top s-top-next; return tmp; } int isStackEmpty(Stack *s) { return s-top NULL; } // 求最长深度最长路径 void getLongestPath(TreeNode* root, int *maxDepth, int **resultPath, int *resLen) { *maxDepth 0; *resultPath NULL; *resLen 0; if(root NULL) return; Stack *s initStack(); // 根节点路径 int rootPath[1]; rootPath[0] root-val; push(s, root, 1, rootPath, 0); while(!isStackEmpty(s)) { StackItem *cur pop(s); TreeNode *p cur-node; // 叶子结点判断是否是更长路径 if(p-left NULL p-right NULL) { if(cur-depth *maxDepth) { *maxDepth cur-depth; // 释放旧结果 if(*resultPath) free(*resultPath); *resLen cur-pathLen; *resultPath (int*)malloc(sizeof(int)*(*resLen)); for(int i 0; i *resLen; i) { (*resultPath)[i] cur-path[i]; } } } // 先压右再压左优先遍历左子树 if(p-right) { push(s, p-right, cur-depth1, cur-path, cur-pathLen); } if(p-left) { push(s, p-left, cur-depth1, cur-path, cur-pathLen); } free(cur-path); free(cur); } free(s); } // 新建节点 TreeNode* createNode(int v) { TreeNode *n (TreeNode*)malloc(sizeof(TreeNode)); n-val v; n-left n-right NULL; return n; } int main(void) { // 构造样例树 /* 1 / \ 2 3 / 4 */ TreeNode *root createNode(1); root-left createNode(2); root-right createNode(3); root-left-left createNode(4); int maxDep; int *path; int pathLen; getLongestPath(root, maxDep, path, pathLen); printf(最大深度 %d\n, maxDep); printf(最长路径); for(int i 0; i pathLen; i) { printf(%d , path[i]); } printf(\n); free(path); return 0; }输出最大深度 3 最长路径1 2 4更推荐递归回溯版本代码短写题首选原理用数组保存当前路径往下走就加入节点回溯的时候删掉遇到叶子比较长度记录最长路径。#include stdio.h #include stdlib.h typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; int maxDep 0; int ansPath[100]; int curPath[100]; void dfs(TreeNode *root, int depth, int idx) { if(root NULL) return; curPath[idx] root-val; // 叶子节点 if(root-left NULL root-right NULL) { if(depth maxDep) { maxDep depth; // 复制到答案路径 for(int i 0; i idx; i) { ansPath[i] curPath[i]; } } return; } dfs(root-left, depth1, idx1); dfs(root-right, depth1, idx1); } TreeNode* createNode(int v) { TreeNode *n malloc(sizeof(TreeNode)); n-val v; n-left n-right NULL; return n; } int main() { TreeNode *root createNode(1); root-left createNode(2); root-right createNode(3); root-left-left createNode(4); dfs(root,1,0); printf(max depth%d\n,maxDep); printf(path:); for(int i0;imaxDep;i){ printf(%d ,ansPath[i]); } return 0; } 
长河君 · 2026/10/2 2:22:59 · 阅读 1.2k 【数据结构】树与二叉树代码终极强化（Finish）
二叉树的常见类型1. 满二叉树定义除叶子节点外每个节点都有左右两个子节点所有叶子都在同一层。 特点深度为k节点总数\(2^k-1\)。2. 完全二叉树定义除最后一层外其余每一层节点都满最后一层节点从左往右连续排列中间不能有空缺。满二叉树一定是完全二叉树完全二叉树不一定是满二叉树。 数组存储二叉树一般用完全二叉树堆就是完全二叉树。3. 二叉搜索树 BST二叉查找树定义左子树所有节点值 根节点右子树所有节点值 根节点左右子树也满足 BST 规则。 特点查找、插入、删除平均\(O(\log n)\)最坏退化成链表\(O(n)\)。4. 平衡二叉树 AVL 树定义二叉搜索树任意节点左右子树高度差绝对值 ≤1。 特点保证平衡查找稳定\(O(\log n)\)插入删除会旋转调整。5. 红黑树RB-Tree定义一种自平衡二叉搜索树通过颜色规则维持平衡。 特点不严格要求高度差插入删除旋转次数更少Java TreeMap、C map 底层。6. 线索二叉树定义利用二叉树空指针域存放前驱、后继节点的指针线索。 作用不用栈就能遍历二叉树。7. 哈夫曼树最优二叉树定义带权路径长度 WPL 最小的二叉树。 特点没有度为 1 的节点用于哈夫曼编码、数据压缩。8. 二叉堆大根堆 / 小根堆底层是完全二叉树大根堆父节点 ≥ 子节点小根堆父节点 ≤ 子节点 用途优先队列、TopK 问题。9. 普通二叉树没有任何约束任意节点 0/1/2 个子节点是最基础的二叉树。C 语言 非递归求二叉树高度BFS 层序#include stdio.h #include stdlib.h // 二叉树结点定义 typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; // 队列结点BFS用 typedef struct QueueNode { TreeNode *data; struct QueueNode *next; } QueueNode; typedef struct Queue { QueueNode *front, *rear; } Queue; // 初始化队列 Queue* initQueue() { Queue *q (Queue*)malloc(sizeof(Queue)); q-front q-rear NULL; return q; } // 入队 void enQueue(Queue *q, TreeNode *node) { QueueNode *newNode (QueueNode*)malloc(sizeof(QueueNode)); newNode-data node; newNode-next NULL; if(q-rear NULL) { q-front q-rear newNode; } else { q-rear-next newNode; q-rear newNode; } } // 出队 TreeNode* deQueue(Queue *q) { if(q-front NULL) return NULL; QueueNode *temp q-front; TreeNode *res temp-data; q-front q-front-next; if(q-front NULL) q-rear NULL; free(temp); return res; } // 判断队列空 int isEmpty(Queue *q) { return q-front NULL; } // 非递归BFS求树高 int maxDepth(TreeNode* root) { if(root NULL) return 0; Queue *q initQueue(); enQueue(q, root); int depth 0; while(!isEmpty(q)) { int levelSize 0; // 统计当前层节点个数 QueueNode *p q-front; while(p ! NULL) { levelSize; p p-next; } // 遍历当前一层 for(int i 0; i levelSize; i) { TreeNode *cur deQueue(q); if(cur-left ! NULL) enQueue(q, cur-left); if(cur-right ! NULL) enQueue(q, cur-right); } depth; } free(q); return depth; }方法 2栈实现 DFS 迭代版C 语言// 栈元素保存节点当前深度 typedef struct StackNode { TreeNode *node; int depth; struct StackNode *next; } StackNode; typedef struct Stack { StackNode *top; } Stack; Stack* initStack() { Stack *s (Stack*)malloc(sizeof(Stack)); s-top NULL; return s; } void push(Stack *s, TreeNode *node, int d) { StackNode *newNode (StackNode*)malloc(sizeof(StackNode)); newNode-node node; newNode-depth d; newNode-next s-top; s-top newNode; } StackNode* pop(Stack *s) { if(s-top NULL) return NULL; StackNode *temp s-top; s-top s-top-next; return temp; } int isStackEmpty(Stack *s) { return s-top NULL; } int maxDepthDFS(TreeNode* root) { if(root NULL) return 0; Stack *s initStack(); push(s, root, 1); int maxD 0; while(!isStackEmpty(s)) { StackNode *cur pop(s); if(cur-depth maxD) maxD cur-depth; // 先压右再压左保证左先访问 if(cur-node-right) push(s, cur-node-right, cur-depth 1); if(cur-node-left) push(s, cur-node-left, cur-depth 1); free(cur); } free(s); return maxD; }考点总结BFS 层序逐层遍历每处理完一层深度 1空间最坏 O (n)DFS 栈栈存储(节点当前深度)弹出时更新最大深度时间复杂度\(O(n)\)每个结点访问一次空树高度 0DFS迭代栈版求二叉树高度 核心思想一句话用栈模拟递归的调用过程深度优先一条路走到最深处记录每一个节点所在的深度全程维护最大深度。拆解递归本质递归求高度max(左子树高度,右子树高度)1递归会一路往下访问遇到叶子节点才回溯。 递归是系统帮我们压栈、保存当前节点信息迭代 DFS 就是我们自己手动用栈保存【节点 当前深度】。栈里存什么栈元素不是单纯节点是一对信息(当前节点, 该节点的深度)根节点入栈深度 1每次弹出栈顶节点拿它的深度去更新全局最大深度maxD入栈顺序重点先压右孩子再压左孩子栈是后进先出所以弹出的时候先访问左子树再访问右子树和递归 DFS 顺序保持一致。遍历逻辑循环直到栈为空弹出栈顶节点更新最大深度如果有右孩子右孩子入栈深度 1如果有左孩子左孩子入栈深度 1举个简单例子1 / \ 2 3压入 (1,1)弹出 (1,1)maxD1压右 (3,2)压左 (2,2)弹出 (2,2)maxD22 无孩子弹出 (3,2)maxD23 无孩子 栈空返回最大深度 2和递归对比递归函数调用栈自动保存上下文迭代 DFS自己手动维护栈保存节点和深度避免递归栈溢出树很深的时候复杂度时间\(O(n)\)每个节点只访问一次空间\(O(n)\)最坏斜树栈里面存全部节点核心思路原来代码只记录最大深度值现在要输出到达最大深度的完整路径。 难点栈只存(节点,深度)不够还要记录这条路径上前面所有节点。两种思路栈保存(当前节点深度到这个节点的路径数组)简单直观适合理解回溯思路用一个全局 / 数组保存当前路径找到叶子时判断深度更新最长路径更省内存考研常用需求输出任意一条最长路径二叉树可能有多条最长路径这里输出第一条找到的思路讲解迭代 DFS 版沿用刚才的栈框架栈元素需要存三样东西结点指针当前结点的深度到达该结点的路径存结点值流程根节点入栈路径 [根值]深度 1弹出栈顶元素如果是叶子结点判断深度是不是大于当前记录的最大深度如果是更新最大深度保存这条路径不是叶子先压右孩子再压左孩子栈后进先出优先走左分支子节点路径 当前路径复制一份追加子节点的值栈空之后打印保存好的最长路径C 完整代码迭代 DFS输出最长路径#include stdio.h #include stdlib.h typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; // 栈元素节点、深度、路径数组、路径长度 typedef struct StackItem { TreeNode *node; int depth; int *path; // 保存路径值 int pathLen; struct StackItem *next; } StackItem; typedef struct Stack { StackItem *top; } Stack; Stack* initStack() { Stack *s (Stack*)malloc(sizeof(Stack)); s-top NULL; return s; } void push(Stack *s, TreeNode *node, int d, int oldPath[], int oldLen) { StackItem *newItem (StackItem*)malloc(sizeof(StackItem)); newItem-node node; newItem-depth d; newItem-pathLen oldLen 1; newItem-path (int*)malloc(sizeof(int) * newItem-pathLen); // 复制旧路径 for(int i 0; i oldLen; i) { newItem-path[i] oldPath[i]; } newItem-path[oldLen] node-val; newItem-next s-top; s-top newItem; } StackItem* pop(Stack *s) { if(s-top NULL) return NULL; StackItem *tmp s-top; s-top s-top-next; return tmp; } int isStackEmpty(Stack *s) { return s-top NULL; } // 求最长深度最长路径 void getLongestPath(TreeNode* root, int *maxDepth, int **resultPath, int *resLen) { *maxDepth 0; *resultPath NULL; *resLen 0; if(root NULL) return; Stack *s initStack(); // 根节点路径 int rootPath[1]; rootPath[0] root-val; push(s, root, 1, rootPath, 0); while(!isStackEmpty(s)) { StackItem *cur pop(s); TreeNode *p cur-node; // 叶子结点判断是否是更长路径 if(p-left NULL p-right NULL) { if(cur-depth *maxDepth) { *maxDepth cur-depth; // 释放旧结果 if(*resultPath) free(*resultPath); *resLen cur-pathLen; *resultPath (int*)malloc(sizeof(int)*(*resLen)); for(int i 0; i *resLen; i) { (*resultPath)[i] cur-path[i]; } } } // 先压右再压左优先遍历左子树 if(p-right) { push(s, p-right, cur-depth1, cur-path, cur-pathLen); } if(p-left) { push(s, p-left, cur-depth1, cur-path, cur-pathLen); } free(cur-path); free(cur); } free(s); } // 新建节点 TreeNode* createNode(int v) { TreeNode *n (TreeNode*)malloc(sizeof(TreeNode)); n-val v; n-left n-right NULL; return n; } int main(void) { // 构造样例树 /* 1 / \ 2 3 / 4 */ TreeNode *root createNode(1); root-left createNode(2); root-right createNode(3); root-left-left createNode(4); int maxDep; int *path; int pathLen; getLongestPath(root, maxDep, path, pathLen); printf(最大深度 %d\n, maxDep); printf(最长路径); for(int i 0; i pathLen; i) { printf(%d , path[i]); } printf(\n); free(path); return 0; }输出最大深度 3 最长路径1 2 4更推荐递归回溯版本代码短写题首选原理用数组保存当前路径往下走就加入节点回溯的时候删掉遇到叶子比较长度记录最长路径。#include stdio.h #include stdlib.h typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; int maxDep 0; int ansPath[100]; int curPath[100]; void dfs(TreeNode *root, int depth, int idx) { if(root NULL) return; curPath[idx] root-val; // 叶子节点 if(root-left NULL root-right NULL) { if(depth maxDep) { maxDep depth; // 复制到答案路径 for(int i 0; i idx; i) { ansPath[i] curPath[i]; } } return; } dfs(root-left, depth1, idx1); dfs(root-right, depth1, idx1); } TreeNode* createNode(int v) { TreeNode *n malloc(sizeof(TreeNode)); n-val v; n-left n-right NULL; return n; } int main() { TreeNode *root createNode(1); root-left createNode(2); root-right createNode(3); root-left-left createNode(4); dfs(root,1,0); printf(max depth%d\n,maxDep); printf(path:); for(int i0;imaxDep;i){ printf(%d ,ansPath[i]); } return 0; }