• LS = （a1, a2, a3,…an） 第一个元素a1是表头，其余元素组成的表（a2, a3,…an）是LS的表尾。
• E= （a, E）这是一个递归的表，长度是2。
  例题：
  （1） A = ();
  (2) B =(e)
  (3) C = (a,(b,c,d))
  (4) D = (A ,B,C)
  (5) E =(a,(E))
  
  文章图片
  

• 二叉树的性质：
• 在二叉树第 i 层最多有2的（i-1）次方个结点。
• 深度为k的二叉树最多有2的k次方-1个结点。
• 任何一颗二叉树T，如果其终端结点数是n0,度为2的结点数为n2，则n0 = n2 + 1;
• 满二叉树：一颗深度为k且有2的k次方-1个结点的二叉树
• 完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应，称为完全二叉树。
• 具有n个结点的完全二叉树的深度：Log2(n)(以2为底n的对数)向下取整+1；
  
  文章图片
  

• 当栈不为空 || 当前节点不为空，执行操作：
• 从根节点开始，输出当前结点；
• 依次输出树中最左端的节点，并入栈。
• 当节点为空停止入栈，取栈顶元素为当前节点并出栈，如果当前节点有右子树，则遍历其右子树。

void PreorderPrint(SearchBTree T)// 先序根(序)遍历二叉树并打印出结点值 { if (T == nullptr) { cout << "Empty tree!"; exit(1); } Stack S = new StackNode; // 借助栈来实现 initStack(S); TreeNode* pT = T; // 创建临时结点指向根节点 while (pT || !isEmpty(S))// 当结点不为空或者栈不为空执行循环 { if (pT)// 当pT不为空 { Push(S, pT); // pT入栈 cout << pT->data << " "; // 打印当前结点 pT = pT->left; // pT移动指向其左孩子 } else {// pT为空，则获取栈顶元素，并出栈 pT = getTop(S); Pop(S); // 若pT为空表示左子树的左孩子全部遍历完，依次出栈 pT = pT->right; // 当左孩子及根结点遍历完之后，开始遍历其右子树 } } cout << endl; delete S; }

• 当栈不为空 || 当前节点为不为空，执行操作：
• 依次访问左结点入栈，但不输出。当节点为空，则停止入栈。
• 访问栈顶元素作为当前节点并出栈，如果当前节点有右子树，则遍历访问其右子树，如果右子树为空，则又进入循环，输出栈顶元素并出栈，再获取右子树。

void InorderPrint(SearchBTree T)// 中根(序)遍历二叉树并打印出结点值 { if (T == nullptr) { cout << "Empty tree!"; exit(1); } Stack S = new StackNode; // 借助栈来实现 initStack(S); TreeNode* pT = T; // 创建临时结点指向根节点 while (pT || !isEmpty(S))// 当结点不为空或者栈不为空执行循环 { if (pT)// 当pT不为空 { Push(S, pT); // pT入栈 pT = pT->left; // pT移动指向其左孩子 } else {// pT为空，则 pT = getTop(S); Pop(S); cout << pT->data << " "; // 若pT为空表示左子树的左孩子全部遍历完，依次出栈并打印 pT = pT->right; // 当左孩子及根结点遍历完之后，开始遍历其右子树 } } cout << endl; delete S; }

• 非递归后根遍历相比前两个有点麻烦，需要引入一个中间变量标记已经访问节点。 当栈不为空或者当前节点为不为空，执行操作：
• 依次将根节点及其左子树的左端节点入栈，但不进行访问，当节点为空，停止入栈。
• 取栈顶元素作为当前节点，如果当前节点的右孩子（右子树）不为空且其右孩子不是上一次访问的节点。则当前节点变为其右子树，遍历其右子树。如果当前节点的右孩子为空或者其右孩子已经被访问，则访问当前节点，标记当前节点为已访问节点，出栈。将当前节点置为空（此时右孩子访问过了），继续取栈顶元素（为了访问根节点）。

void PostorderPrint(SearchBTree T)// 先根(序)遍历二叉树并打印出结点值 { if (T == nullptr) { cout << "Empty tree!"; exit(1); } Stack S = new StackNode; // 借助栈来实现 initStack(S); TreeNode* pT = T; // 创建临时结点指向根节点 TreeNode* qT = nullptr; while (pT || !isEmpty(S))// 当结点不为空或者栈不为空执行循环 { if (pT)// 当pT不为空 { Push(S, pT); // pT入栈 pT = pT->left; // pT移动指向其左孩子 } else { pT = getTop(S); // 取栈顶元素作为当前结点 if (pT->right && pT->right != qT)// 若当前节点有右孩子且不是上一次已经被访问的结点 { pT = pT->right; // 指向其右孩子 } else {// 若当前结点没有右孩子或者未被访问，则 Pop(S); // 出栈 cout << pT->data << " "; // 访问当前结点的数据 qT = pT; // 令pT记录当前结点，用于稍后判断是否已经被访问过 pT = nullptr; // 将当前结点赋值为空 } // 当左孩子及根结点遍历完之后，开始遍历其右子树 } } cout << endl; delete S; }

• 初始时，根结点入队列
• 然后，while循环判断队列不空时，使用poll（）方法获取对头结点，输出它，并把它的所有孩子结点入队列。

public void levelTraverse(BinarySearchTree tree){ levelTraverse(tree.root); } private void levelTraverse(BinaryNode root){ if(root == null) return; Queue> queue = new LinkedList<>(); //层序遍历时保存结点的队列 queue.offer(root); //初始化 while(!queue.isEmpty()){ BinaryNode node = queue.poll(); //获取对头元素并删除 System.out.print(node.element + " "); //访问节点 if(node.left != null) queue.offer(node.left); if(node.right != null) queue.offer(node.right); } }

• Huffman树，又称最优树，是一类带权路径长度最短的树。
• 树的路径长度：根结点到每一个结点的路径长度之和。
• 结点的带权路径长度 = 该结点到树根的路径长度 * 结点上权
• 带权路径长度WPL最小的二叉树称为最优二叉树或Huffman树

• 用两个数组分别存储数据元素（顶点）信息+数据元素之间的关系信息

• 邻接表是图的一种链式存储结构，表结点+头结点
• 每个表结点由3个域组成，其中邻接点域（adjvex）指示与顶点vi邻接的点在图中的位置，链域（nextarc）知识下一条边或弧的结点，info存储信息，如权值等。
• 每个链表上有一个头结点，由链域（firstarc）,指向链表中第一个结点，数据域（data）
  头结点 表结点
  
  文章图片
  
  2.图的遍历

• N = （V,(E)）；TE：最小生成树中边的集合。 V：所有顶点的集合
• 初始化：TE={}， U={u0} (u0∈V)；
• 重复执行以下操作：
  在所有的u∈U，v∈V-U的边（u，v）∈E中找权值最小的边(u0,v0)，加入TE中，同时vo并入集合U中，直到U=V为止。
• 此时TE中有n-1条边， T={V，{TE}}为N的最小生成树。
  
  文章图片
  
• 假设网中有n个结点，Prim算法时间复杂度是O(n2），与边数无关，适合求边稠密的网的最小生成树。
• Kruskal算法刚好相反，设变数是e，它的实践复杂度O（eloge），与结点数无关，适合求边稀疏的网的最小生成树。

• 假设连通网N=（V，{E}），令最小生成树的初始状态为只有n个顶点而没有边的非连通图T=（V，{}），图中每个顶点自成一个联通分量。
• 在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。
• 依次类推，直到T中所有顶点都在同一连通分量上为止。
  
  文章图片
  

• 由某个集合上的一个偏序得到该集合上的一个全序，这个操作称为拓扑排序。
• 偏序：若集合X上的关系R是自反的、反对称的和传递的，则称R是集合X上的偏序关系
• 全序：设R是集合X上的偏序，如果对于每个x,y∈X，必有xRy或有yRx，则称R是集合X上的全序关系。
• 直观来看，偏序指集合中仅有部分成员之间可比较（部分有序），而全序指集合中全体成员之间均可比较（全体有序）。
  
  文章图片
  
• 左图按照正常遍历那么有2种路径，分别为1234,1324。其中1始终在2，3遍历之前，2和3始终在4之前，2和3之间无法判断谁前谁后，所以这就是偏序。
• 再看右图在2和3之间加了一个指向，由2指向3，所以路线只有1234，所以它是全序。

• AOV网（activity on vertex）：顶点表示活动，弧表示活动间的优先关系的有向图
• 在有向图中选一个没有前驱的顶点并输出(入度为0的点)
• 在图中删除该顶点和所有以它为尾的弧（所有以该顶点出发的箭头）
• 重复上述两步，直到全部顶点都已输出，或者当前图中不存在无前驱的顶点为止。后一种情况说明有向图中存在环。
• 拓扑排序序列有很多种，下图只是其中一种。
  

推荐阅读

• 

  新途观后视镜怎么折叠
• 

  沈阳社保缴费基数2023年最新标准公布 沈阳个人社保缴费标准表一览
• 

  Android:dialog去除边框的实现(自带Style的padding)
• 

  黄豆泡一天一夜有毒吗
• 

  九天圣母庙的简介
• 

  王者荣耀马可波罗潮玩牛仔怎么样 马可波罗潮玩牛仔皮肤介绍
• 

  美容护肤美白的方法有什么？
• 

  苹果手机返回键设置在哪里
• 

  详解佳能MF443DW硒鼓更换方法 佳能MF443DW更换硒鼓需要清零吗
• 

  致错爱
• 

  像素|144Hz竞速屏 iQOO Neo5 SE手机外观图赏
• 

  士兵退役费算不算夫妻共同财产
• 

  海信电视怎么老是闪屏，海信电视总是闪啊闪是什么原因
• 

  负债的看过来！你们是怎么上岸的？
• 

  防火墙源码 分析,hacknet防火墙分析
• 

  46．请问观想念佛要注意什么（）
• 

  linux的命令挂载设备 linux挂载的概念
• 

  中立云（UCloud）主机配置步骤
• 

  身无分文到哪能搞到钱 走投无路干什么赚钱快
• 

  绿宝石火山灰有什么用 绿宝石火山灰做什么好

• 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
• C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
• 数据结构和算法|LeetCode 的正确使用方式
• 先序遍历 中序遍历 后序遍历 层序遍历
• 数据结构|C++技巧（用class类实现链表）
• 数据结构|贪吃蛇代码--c语言版 visual c++6.0打开
• 算法|算法-二分查找
• 数据结构学习指导|数据结构初阶（线性表）
• leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
• java|ObjectOrientedProgramming - 面向对象的编程（多态、抽象类、接口）- Java - 细节狂魔