前言证明 已知：左右端点L、R，要求找到上图中空心点的位置 思路：通过不断缩小 [L,R] 的范围，无限逼近空心点 思想：先取 [L,R] 的中点 mid，再取 [mid,R] 的中点 mmid，通过比较 f(mid) 与 f(mmid) 的大小来缩小范围。当最后 L=R-1 时，再比较下这两个点的值，我们就找到了答案。1、当 f(mid) > f(mmid) 的时候，我们可以断

带权路径长度结点的权 有某种特殊含义的数值（表示节点的重要性等） 结点的带权路径长度 从树的根到该结点的路径长度（经过的边数） 与节点上的数的乘积 树的带权路劲长度 所有的叶子结点的带权路径长度之和（WPL） $$WPL=\sum^{n}_{i=1}w_il_i$$ ​ 下面就来举两个例子来介绍一下怎么计算（考的概率蛮大） $$ WPL=1 \times 2 + 2

一、树的遍历1）树的先根遍历（和二叉树前序遍历是异曲同工的）若树非空，先访问根节点，再依次对每棵树进行先根遍历 对于上面树的先根遍历序列应该为：A——>B——>E——>H——>F——>C——>G——>D——>H——>I——>J 123456789// 树的先根遍历void PreOrder(TreeNode *R){ i

森林的基本概念 一、双亲表示法（顺序存储）描述 每个结点中保存指向双亲的“指针” 结构体12345678910#define MAX_TREE_SIZE 100 // 树中最多的结点数typedef struct { // 树的结点定义 ElemType data; // 数据元素 int parent;

前言​ 对于普通二叉树而言，现在提出一个问题，如果随意给出你一个结点p，现在需要你找到它中序遍历对于结点p而言在遍历的时候的前驱或者后继（注意：这个的前驱是指中序遍历的时候的前驱哟！） 。这个时候就会比较麻烦了，你必须对这课树从根节点出发重新进行一次中序遍历，同时还需要准备两个指针分别指向当前结点p和当前结点的前驱pre两个。但是这样的话就会非常不方便，效率也会很低，因此我们就引入了线索二叉树来解

前言​ 这部分可以说是无论是考研还是期末考试都是非常喜欢出这种类型的题目的，只不过考研的话可能会更加恶心，没有考研需求的同学把这里看懂，复习的时候会轻松很多！ 注意​ 如果我们现在不知道一棵树长什么样子，只知道这棵树的前中后序、层次遍历的一种，我们是不可以确定一棵二叉树的。 ​ 如果我们需要确定一颗二叉树，就至少需要前序/后序/层次遍历 + 中序遍历。 前序+中序遍历序列前序遍

一、二叉树的遍历（理论部分）本节我将给大家介绍三种遍历方式： 前序遍历（根左右） 中序遍历（左根右） 后序遍历（左右根） 现在我们就来稍微讲一下这三个遍历是咋遍历的，后面括号里的内容实际上就是遍历的规则，可以结合参考下面进行理解。 前序遍历（前根遍历）以上图为例： ​ 首先从根节点出发，始终按照根左右的口诀进行遍历，所以结点1的下一步应该是遍历到结点2，到结点2之后继续按照根左右的规则进行

一、顺序存储方式结构体12345#define MaxSize 100struct TreeNode { ElemType data; // 结点中 bool isEmpty; // 结点是否为空 }t[MaxSize]; 初始化所有结点均为空1234// 注意，我们之后正式存储数据的时候习惯从t[1]开始存储，这样的好处是可以将下标和数据的编号一一对应上，如下图

定义是n（n>=0）个结点的有限集合。空二叉树，即n=0。 或者由一个根节点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。 特点： 每个结点最多只有两个子树 左右子树不可以颠倒（二叉树是有序树，因此它和度为2的有序树是有区别的） ​ 满二叉树$$一棵高度为h，且含有2^h - 1个结点的二叉树，不能多也不能少$$ 特点 只有

基本概念​ 树是n个结点的有限集合，n=0，为空树，这是一种特殊情况。 ​ 树就由一个一个结点和连线组成的，具体性质术语见下。 专业术语 空树： 结点数为0的树 叶子结点：没有后继的结点的结点 分支结点： 有后继的结点 非空树 有且仅有1个根节点 除了根节点外，任何一个结点有且仅有一个前驱 每个结点可以有0个或者多个后继结点 子树(看例子理解) 树是一种递归定义的数据结构 祖先