[c++]csp-j初赛——树

宇宙免责申明:本文由deepseek做过更改,以及进行了语言上的优化,可能会出现错误,如有错误,请私信联系.本文的所有图均为本人手画,由于画图时神志不清,如果发现图中有错误,请私信联系.树一、树的基本概念树是一种非线性数据结构用于描述数据元素之间的层次关系。它由nn≥0个节点组成一个具有层次关系的集合二、 核心术语一览表术语含义初赛常考指数根节点没有父节点的节点每棵树有且仅有一个⭐⭐⭐叶子节点度为0的节点没有子节点⭐⭐⭐父节点/子节点直接相连的上下层节点⭐⭐⭐节点的度一个节点含有的子节点个数⭐⭐⭐⭐树的度树中所有节点度的最大值⭐⭐⭐节点的层次根为第1层根的子节点为第2层……⭐⭐⭐树的深度/高度树中节点的最大层次⭐⭐⭐⭐祖先从根到该节点路径上的所有节点⭐⭐森林多棵互不相交的树的集合⭐⭐二叉树定义二叉树Binary Tree 是每个节点最多只有两个子节点的树分别称为左子节点和右子节点次序不能颠倒。如图二叉树概念辨析总览类型定义初赛考点满二叉树除叶子节点外每个节点都有2个子节点所有叶子节点都在同一层深度为 h 的满二叉树共有2ʰ − 1个节点完全二叉树只有最后一层不满且最后一层的节点全部集中在左侧连续位置满二叉树是完全二叉树的特殊情况常考数组下标计算左孩子 2i右孩子 2i1「注」重点区分完全二叉树 ≠ 满二叉树。满二叉树是“完美塞满”完全二叉树是“最后一层从左到右连续排列”。如图二叉树层数计算在 CSP-J 初赛中默认根节点位于第 1 层。设二叉树的高度为hhh总结点数为NNN。第iii层的最大节点数二叉树的第iii层最多能容纳的节点数为2 i−12^{\,i-1}2i−1。每个节点最多向下延伸出 2 个子节点节点数呈等比数列1,2,4,…1, 2, 4, \dots1,2,4,…满二叉树的高度推导若该树为满二叉树则前hhh层的所有节点均已填满。总节点数NNN等于前hhh层的最大节点数之和N124⋯2h−1 N 1 2 4 \dots 2^{h-1}N124⋯2h−1根据等比数列求和公式首项a11a_11a1​1公比q2q2q2项数hhhN1⋅(2h−1)2−12h−1 N \frac{1 \cdot (2^h - 1)}{2 - 1} 2^h - 1N2−11⋅(2h−1)​2h−1由此反推满二叉树的高度2hN1 ⟹ hlog⁡2(N1) 2^h N 1 \implies h \log_2(N 1)2hN1⟹hlog2​(N1)完全二叉树的高度推导完全二叉树的前h−1h-1h−1层必然是满二叉树其节点数为2h−1−12^{h-1} - 12h−1−1。由于hhh为正整数该不等式组等价于常用的向下取整公式h⌊log⁡2N⌋1 h \lfloor \log_2 N \rfloor 1h⌊log2​N⌋1普通二叉树的高度范围推导当每层都尽可能填满节点时高度达到理论最小值。此时最小的整数hhh必须满足N≤2h−1N \le 2^{h} - 1N≤2h−1解得hmin⁡⌈log⁡2(N1)⌉ h_{\min} \lceil \log_2 (N 1) \rceilhmin​⌈log2​(N1)⌉当每层都仅有 1 个节点退化为单链表时高度达到理论最大值hmax⁡N h_{\max} Nhmax​N