中序后继在中序线索二叉树中找到指定结点*p的中序后继next①若p->rtag==1，则next = p->rchild②若p->rtag == 0，指定结点有右孩子中序遍历====左 根 右===========左 根 (左 根 右)===========左 根 ((左 根 右) 根 左)next = p的右子树种最左下结点 实现代码1234567891011121314151

问题引入从中序遍历的角度来看，找前驱、后继很不方便；遍历操作必须从根开始 思路从根节点开始，重新进行一次中序遍历，指针q记录当前访问的节点，指针p记录上一个被访问的结点。①当q == p时，p为前驱②当p == p时，q为后继 方案n个结点的二叉树，有n+1个空链域！可以用来记录前驱、后继的信息。指向前驱、后继的指针称为“线索” 前驱线索: 由左孩子指针充当后继线索: 由右孩子指针充当 存储结构1

构造方法如果只给出一棵二叉树的前/中/后/层 序遍历序列中的一种，不能唯一确定一棵二叉树，构造分以下三种情况①前序 + 中序遍历序列②后续 + 中序遍历序列③层序 + 中序遍历序列 遍历序列前序+中序前序遍历: 根节点、前序遍历左子树、前序遍历右子树中序遍历: 中序遍历左子树、根节点、中序遍历右子树 左子树的前序遍历序列 = 左子树的中序遍历序列右子树的前序遍历序列 = 右子树的中序遍历序列 例子

基本思想①初始化一个辅助队列②根节点入队③若队列非空，则队头结点出队，访问该节点，并将其左、右孩子插入队尾(存在的话)④重复③直到队列为空 实现代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676

定义遍历: 按照某种次序把所有结点都访问一遍层次遍历: 基于树的层次特性确定的次序规则 递归特征:①要么是个空二叉树②要么就是由“根节点+左子树+右子树”组成的二叉树 先序遍历: 根左右(NLR)中序遍历: 左根右(LNR)后续遍历: 左右根(LRN) 算数表达式分析树将操作数作为二叉树的叶子结点,操作符作为二叉树的非叶子结点 graph TD; A(("-")); B(("

顺序存储定义一个长度为MaxSize的数组t，按照从上至下、从右至左的顺序依次存储完全二叉树的各个节点 实现代码123456#define MaxSize 100struct TreeNode { int value; //结点中的数据元素 bool isEmpty; //结点是否为空};TreeNode t[MaxSize]; 初始化操作 1234

定义二叉树是n(n≥0)个节点的有限集合：①或者为空二叉树,即n=0②或者由一个根节点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树特点:①每个节点至多只有两棵子树②左右子树不能颠倒(二叉树是有序树) 特殊二叉树满二叉树:一棵高度为h，且含有2^h - 1个节点的二叉树特点:①只有最后一层有叶子节点②不存在度为1的节点③按层序从1开始编号，节点为i的做孩子为2i，右

定义树是n(n≥0)个节点的有限集合，n=0时，称为空树,这是一种特殊情况。在任意一个非空树种应满足:1)有且仅有一个特点的称为根的节点。2)当n>1时，其余节点可分为m(m>0)个互不相交的有限集合$$T_1,T_2,..T_m$$其中每个集合又是一颗树，并且称为根节点的子树 基本概念节点的层次(深度): 从上往下数节点的高度: 从下往上数树的高度(深度): 总共多少层节点的度: 有

匹配模式串的匹配模式: 在主串中找到与模式串相同的子串，并返回其所在的位置 模式匹配若主串S中存在与串T相同的子串，则返回它在主串S中第一次出现的位置，否则函数值为0。只要有一个字符不同，就可以停止检查当前子串 朴素模式匹配算法代码一: 123456789101112131415161718192021222324252627282930313233343536373839404142434445

引入原因朴素模式匹配算法中，当某些子串与模式串能部分匹配时，主串的扫描指针i经常回溯，导致时间开销增加 实现代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767