1.二叉树第i层至多有2^(i-1)个结点(i>=1)。
2.深度为k的二叉树上,至多含2^k-1个结点(k>=1)
3.n0 = n2 + 1(度)
4.满二叉树:深度为k且含有2^k-1个结点的树。
5.完全二叉树:除最后一层外,每一层上的节点数均达到最大值;在最后一层上只缺少右边的若干结点。
(树中所含n个结点和满二叉树中编号为1至n的结点一一对应)。
6.具有n个结点的完全二叉树的深度为[log2n] + 1。
7.二叉树的链式存储表示:二叉链表、三叉链表(增加双亲指针域)、双亲链表、 线索链表。
8.二叉树的遍历:前、中、后。
9二叉树的遍历算法:递归、非递归(栈:现在经过不访问,一会访问的结点入栈,栈空结束遍历)。
10.二叉树递归遍历引申的算法:求树的深度、结点个数、复制二叉树等。
11.二叉树相关算法一定要考虑空树的情况。
13.表达式和二叉树的关系: [第一操作数][二元运算符][第二操作数] = [左节点][双亲结点][右结点],(先中后)缀对应(前中后)遍历。
14.线索二叉树:二叉链表中增加两个标志域,让左右两个指针增加功能:有子结点则指向子结点,没有则指向前驱和后继(某种遍历方式)。
15.树和二叉树的相互转换,树的叶子结点:左子树空。树、森林与二叉树的转换
16.遍历二叉树的所有叶子节点。
17.树的存储结构
18.哈夫曼树
19.平衡二叉树:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
[BinaryTree] 二叉树常考知识点
推荐阅读
- 博文阅读密码验证 - 博客园
- #10042. 「一本通 2.1 练习 8」收集雪花 || 离散化 || 双指针法 || C++ || LOJ
- AtCoder Beginner Contest 070|Elena|8.12|#471
- 树状数组 || 线段树 || Luogu P5200 [USACO19JAN]Sleepy Cow Sorting
- 悬线法 || BZOJ 1057: [ZJOI2007]棋盘制作 || Luogu P1169 [ZJOI2007]棋盘制作
- BZOJ2716: [Violet 3]天使玩偶
- 洛谷P3209 [HNOI2010]PLANAR
- NOIP2014-10-30模拟赛
- NOIP2014-9-6模拟赛
- BZOJ4869: [Shoi2017]相逢是问候