杭州做购物网站,网站建设yu,主页导航网站建设定制,福建seo优化报名明年4月蓝桥杯软件赛的同学们#xff0c;如果你是大一零基础#xff0c;目前懵懂中#xff0c;不知该怎么办#xff0c;可以看看本博客系列#xff1a;备赛20周合集 20周的完整安排请点击#xff1a;20周计划 每周发1个博客#xff0c;共20周#xff08;读者可以按…报名明年4月蓝桥杯软件赛的同学们如果你是大一零基础目前懵懂中不知该怎么办可以看看本博客系列备赛20周合集 20周的完整安排请点击20周计划 每周发1个博客共20周读者可以按自己的进度选“正常”和“快进”两种计划。 每周3次集中答疑周三、周五、周日晚上在QQ群上答疑 文章目录 1. 基本数据结构概述1.1 数据结构和算法的关系1.2 线性数据结构概述1.3 二叉树简介 2. 栈2.1 手写栈2.2 CSTL栈2.3 Java 栈2.4 Python栈2.5 习题 3. 二叉树3.1 二叉树概念3.2 二叉树的存储和编码3.2.1 二叉树的存储方法3.2.2 二叉树存储的编码实现3.2.3 二叉树的极简存储方法 3.3 例题3.4 习题 第7周: 栈、二叉树
1. 基本数据结构概述 很多计算机教材提到程序 数据结构 算法。 本作者曾给《数据结构》、《算法设计与分析》的作者王红梅老师题写了一句赠言“以数据结构为弓以算法为箭”。 数据结构是是计算机存储、组织数据的方法。常用的数据结构有数组Array、栈Stack、队列Queue、链表Linked List、树Tree、图Graph、堆Heap、散列表Hash等。分为两大类线性表、非线性表。数组、栈、队列、链表是线性表其他是非线性表。
1.1 数据结构和算法的关系 数据结构和算法往往密不可分。下面以图的存储为例说明数据结构和算法的关系。这几种存图的数据结构各有优缺点也各有自己的应用场景。 1边集数组 定义结构体数组
struct Edge{int u, v, w;
}edges[M];其中(u,v,w)表示一条边起点是u终点是v边长是w。edges[M]可以存M条边。 边集数组的优点是最节省空间的存图方法存储空间不可能再少了。n1000个点m5000条边的图使用的存储空间是12×5000 60KB。 边集数组的缺点不能快速定位某条边。如果要找某点u和哪些点有边连接得把整个edges[M]从头到尾搜一遍才能知道。 边集数组的的应用场景如果算法不需要查找特定的边就用边集数组。例如最小生成树Kruskal算法、最短路径Bellman-ford算法。 2邻接矩阵 定义一个二维数组 int edge[N][N];其中edge[i][j]表示点i和点j之间有一条边边长为edge[i][j]。它可以存N个点的边。若edge[i][j]0表示i和j之间没有边若edge[i][j] ! 0i和j之间有边边长为edge[i][j]。 邻接矩阵的优点能极快地查询任意两点之间是否有边。如果edge[i][j] ! 0说明点i和j之间有一条边边长edge[i][j]。 邻接矩阵的缺点如果图是一张稀疏图大部分点和边之间没有边那么邻接矩阵很浪费空间因为大多数edge[][]0没有用到。n1000个点m5000条边的图使用的存储空间是12×1000×1000 12MB。 邻接矩阵的应用场景1稠密图几乎所有的点之间都有边edge[][]数组几乎用满了很少浪费2算法需要快速查找边而且计算结果和任意两点的关系有关例如最短路径算法的Floyd算法。 3邻接表 邻接矩阵的优点十分节省空间因为只存储存在的边。 邻接矩阵的缺点没有明显的缺点。它的存储空间只比边集数组大一点点而查询边的速度只比邻接矩阵慢一点点。 邻接矩阵应用场景基于稀疏图的大部分算法。
1.2 线性数据结构概述 在所有数据结构中线性表是最简单的。线性表有数组、链表、队列、栈它们有一个共同的特征把同类型的数据一个接一个地串在一起。 下面对线性表做个概述并比较它们的优缺点。 1数组 数组是最最简单的数据结构它的逻辑结构和物理内存的存储完全一样。例如C语言中定义一个整型数组int a[10]系统会分配一个40字节的存储空间这100个字符的存储地址是连续的。
#include bits/stdc.h
using namespace std;
int main(){int a[10];for (int i0;i10;i) cout a[i] ; //打印10个整数的存储地址return 0;
}在作者机器上运行输出10个整数的存储地址 0x6dfec4 0x6dfec8 0x6dfecc 0x6dfed0 0x6dfed4 0x6dfed8 0x6dfedc 0x6dfee0 0x6dfee4 0x6dfee8 数组的优点1简单容易编程2访问快捷要定位到某个数据只需使用下标即可例如a[0]是第1个数据a[i]是第i-1个数据3与某些应用场景直接对应例如数列是一维数组可以在一维护数组上排序矩阵是二维数组表示空间坐标等等。 数组的缺点删除和增加数据很麻烦非常耗时。例如要删除数组int a[10]的第5个数据只能采用覆盖的方法从第6个数据开始每个往前挪一位。增加数据也麻烦例如要在第5个位置插入一个数据只能把原来第5个开始的数据逐个往后挪一位空出第5个位置给新数据。 2链表 链表是为了克服数组的缺点提出的一种线性表链表的插入和删除操作不需要挪动其他数据。简单地说链表是“是用指针串起来的数组”。链表的数据不是连续存放的而是用指针串起来的。例如下图删除链表的第3个数据只要把原来连接第3个数据的指针断开然后连接它前后的数据即可不用挪动其他的数据。 链表的优点增加和删除数据很便捷。这个优点弥补了数组的缺点。 链表的缺点定位某个数据比较麻烦。例如要输出第5个数据需要从链表头开始沿着指针一步步走找到第5个。链表的这个缺点却是数组的优点。 链表和数组的优缺点正好相反它们的应用场合不同数组适合静态数据链表适合动态数据。 链表如何编程实现在常见的数据结构教材中链表的数据节点是动态分配的各节点之间用指针来连接。但是在算法竞赛中如果手写链表一般不用动态分配而是用静态数组来模拟。手写链表的代码见《算法竞赛》第3页“1.1.2 静态链表”。当然除非必要一般不手写链表而是用系统提供的链表例如C STL的listJava LinkedListPython的list。 链表在蓝桥杯等算法竞赛中不太常用所以本章没有详细介绍。 3队列 队列是线性数据的一种使用方式模拟现实世界的排队操作。例如排队购物只能从队头离开队伍新来的人只能排到队尾不能插队。队列有一个出口和一个入口出口是队头入口是队尾。队列的编程实现可以用数组也可以用链表。 队列这种数据结构无所谓优缺点只有适合不适合。例如宽度优先搜索BFS就是基于队列的用其他数据结构都不合适。 4栈 栈也是线性数据的一种使用方式模拟现实世界的单出入口。例如一管泡腾片先放进去的泡腾片后出来。栈的编程比队列更简单同样可以用数组或链表实现。 栈有它的使用场合例如递归使用栈来处理函数的自我调用过程。
1.3 二叉树简介 二叉树是一种高度组织性、高效率的数据结构。例如在一棵有n个节点的满二叉树上定位某个数据只需走logn步插入和删除某个数据也只需logn步。在二叉树的基础上发展出了很多高级数据结构和算法。大多数高级数据结构例如树状数组、线段树、树链剖分、平衡树、动态树等都是基于二叉树的。
2. 栈 栈stack是比队列更简单的数据结构它的特点是“先进后出”。 队列有两个口一个入口和一个出口。而栈只有唯一的一个口既从这个口进入又从这个口出来。所以如果自己写栈的代码比队列的代码更简单。
2.1 手写栈 如果使用环境简单最简单的手写栈代码用数组实现。
const int N 300008; //定义栈的大小
struct mystack{int a[N]; //存放栈元素从a[0]开始int t -1; //栈顶位置初始栈为空置初值为-1void push(int data){ a[t] data; } //把元素data送入栈int top() { return a[t]; } //读栈顶元素不弹出void pop() { if(t-1) t--;} //弹出栈顶int size() { return t1;} //栈内元素的数量int empty() { return t-1 ? 1:0; } //若栈为空返回1
};使用栈时要注意不能超过栈的空间。上面第1行定义了栈的大小是N栈内的元素数量不要超过它。 用下面的例子给出上述手写代码的应用。 例题表达式括号匹配 题解 合法的括号串例如“(())”、“()()()”像“)(()”这样是非法的。合法括号组合的特点是左括号先出现右括号后出现左括号和右括号一样多。 括号组合的合法检查是栈的经典应用。用一个栈存储所有的左括号。遍历字符串的每一个字符处理流程是 1若字符是 ‘(’进栈。 2若字符是’)有两种情况如果栈不空说明有一个匹配的左括号弹出这个左括号然后继续读下一个字符如果栈空了说明没有与右括号匹配的左括号字符串非法输出NO程序退出。 3读完所有字符后如果栈为空说明每个左括号有匹配的右括号输出YES否则输出NO。 C代码
#include bits/stdc.h
using namespace std;
const int N 300008; //定义栈的大小
struct mystack{int a[N]; //存放栈元素从a[0]开始int t -1; //栈顶位置初始栈为空置初值为-1void push(int data){ a[t] data; } //把元素data送入栈int top() { return a[t]; } //读栈顶元素不弹出void pop() { if(t-1) t--; } //弹出栈顶int size() { return t1;} //栈内元素的数量int empty() {return t-1 ? 1:0; } //若栈为空返回1
}st;
int main(){char x;while(cinx){ //循环输入if(x) break; //输入为停止if(x() st.push(x); //左括号入栈if(x)){ //遇到一个右括号if(st.empty()) {coutNO;return 0;} //栈空没有左括号与右括号匹配else st.pop(); //匹配到一个左括号出栈}}if(st.empty()) coutYES; //栈为空所有左括号已经匹配到右括号输出yeselse coutNO;return 0;
}Java代码
import java.util.Scanner;
public class Main {static final int N 300008;static class mystack {int[] a new int[N];int t -1;void push(int data) { a[t] data; }int top() { return a[t]; }void pop(){ if(t -1) t--; }int size(){ return t 1; }boolean empty() { return t -1 ? true : false; }}public static void main(String[] args) {Scanner sc new Scanner(System.in);mystack st new mystack();String s sc.next();for (int i 0; i s.length(); i) {char x s.charAt(i);if(x ) break;if(x () st.push(x);if(x )) {if(st.empty()) {System.out.println(NO);return;}else st.pop();}}if(st.empty()) System.out.println(YES);else System.out.println(NO);}
}Python代码 Python的手写栈用到了list。用list模拟栈有一个好处不用担心栈空间不够大因为list自动扩展空间。而且list的栈操作非常快因为栈顶是list的末尾元素栈只有一个出入口只在list的末尾进行进栈和出栈操作操作极为快捷。下面是list实现的栈功能。 下面是例题的Python代码栈用list模拟。
st [] #定义栈用list实现
flag True #判断左括号和右括号的数量是否一样多
s input().strip()
for x in s:if x(: st.append(() #进栈if x):if len(st)!0: #len()栈的长度st.pop() #出栈也可以写成 del st[-1] st[-1]是栈顶else: #栈已空没有匹配的左括号flag Falsebreak
if len(st)0 and flag: print(YES)
else: print(NO)2.2 CSTL栈 竞赛时一般不自己手写栈而是用STL stack https://www.cplusplus.com/reference/stack/stack/。 STL stack的主要操作见下表。 用下面的例题说明STLqueue的应用 例题排列 题解把符合条件的一对i, j称为一个“凹”。首先模拟检查“凹”了解执行的过程。以“3 1 2 5”为例其中的“凹”有“3-1-2”和“3-1-2-5”还有相邻的“3-1”、“1-2”、“2-5”。一共5个“凹”总价值13。 像“3-1-2”和“3-1-2-5”这样的“凹”需要检查连续3个以上的数字。 例如“3 1 2”从“3”开始下一个应该比“3”小例如“1”再后面的数字比“1”大才能形成“凹”。 再例如“3-1-2-5”前面的“3-1-2”已经是“凹”了最后的“5”也会形成新的“凹”条件是这个“5”必须比中间的“1-2”大才行。 总结上述过程是先检查“3”再检查“1”符合“凹”再检查“2”比前面的“1”大符合“凹”再检查“5”比前面的“2”大符合“凹”。 以上是检查一个“凹”的两头还有一种是“嵌套”。一旦遇到比前面小的数字那么以这个数字为头可能形成新的“凹”。例如“6 4 2 8”其中的“6-4-2-8”是“凹”内部的“4-2-8”也是凹。如果学过递归、栈就会发现这是嵌套所以本题用栈来做很合适。 以“6 4 2 8”为例用栈模拟找“凹”。当新的数比栈顶的数小就进栈如果比栈顶的数大就出栈此时找到了一个“凹”并计算价值。下图中的圆圈数字是数在数组中的下标位置用于计算题目要求的价值。 图(1)6进栈。 图(2)4准备进栈发现比栈顶的6小说明可以形成凹4进栈。 图(3)2准备进栈发现比栈顶的4小说明可以形成凹2进栈。 图(4)8准备进栈发现比栈顶的2大这是一个凹“4-2-8”对应下标“②–④”弹出2然后计算价值j-i1④-②13。 图(5)8准备进栈发现比栈顶的4大这是一个凹“6-4-8”对应下标“①–④”弹出4然后计算价值j-i1④-①14。 图(6)8终于进栈了数字也处理完了结束。 在上述过程中只计算了长度为3和3以上的凹并没有计算题目中“3a[i]-a[j]之间不存在其他数字”的长度为2的凹所以最后统一加上这种情况的价值(n-1)×2 6。 最后统计得“6 4 2 8”的总价值是34613。 C代码
#include bits/stdc.h
using namespace std;
const int N 300008;
int a[N]; //这里a[]是题目的数字排列
int main(){int n; cinn;for(int i 1;i n;i) cina[i]; //输入数列stack int st; //定义栈long long ans 0;for(int i 1;i n;i){while(!st.empty() a[st.top()] a[i]){st.pop();if(!st.empty()){int last st.top();ans (i - last 1);}}st.push(i);}ans (n - 1) * 2; //3a[i]-a[j]之间不存在其他数字的情况coutans;
}2.3 Java 栈 Java Stack https://docs.oracle.com/en/java/javase/14/docs/api/java.base/java/util/Stack.html 有以下操作。 例题 排列 的Java代码。
import java.util.Scanner;
import java.util.Stack;
public class Main {static final int N 300008;public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();int[] a new int[N];for(int i 1; i n; i) a[i] sc.nextInt(); StackInteger st new Stack();long ans 0;for(int i 1; i n; i) {while(!st.empty() a[st.peek()] a[i]) {st.pop();if(!st.empty()) {int last st.peek();ans (long)(i - last 1);}}st.push(i);}ans (n - 1) * 2;System.out.println(ans);}
}2.4 Python栈 python的栈可以用以下三种方法实现1list2deque3LifoQueue。比较它们的运行速度list和deque一样快而LifoQueue慢得多建议使用list。前面已经介绍了用list实现栈的方法。 下面是例题 排列 的代码。
n int(input())
a [int(x) for x in input().split()]
st [] #定义栈用list实现
ans 0
for i in range(n):while len(st) ! 0 and a[st[-1]] a[i]: #st[-1]是栈顶st.pop() #弹出栈顶if len(st) ! 0:last st[-1] #读栈顶ans (i - last 1)st.append(i) #进栈
ans (n - 1) * 2
print(ans)2.5 习题
小鱼的数字游戏 后缀表达式 栈 【模板】栈
3. 二叉树 前面介绍的数据结构数组、队列、栈都是线性的它们存储数据的方式是把相同类型的数据按顺序一个接一个串在一起。简单的形态使线性表难以实现高效率的操作。 二叉树是一种层次化的、高度组织性的数据结构。二叉树的形态使得它有天然的优势在二叉树上做查询、插入、删除、修改、区间等操作极为高效基于二叉树的算法也很容易实现高效率的计算。
3.1 二叉树概念 二叉树的每个节点最多有两个子节点分别称为左孩子、右孩子以它们为根的子树称为左子树、右子树。二叉树的每一层以2的倍数递增所以二叉树的第k层最多有2k-1个节点。根据每一层的节点分布情况有以下常见的二叉树。 1满二叉树 特征是每一层的节点数都是满的。第一层只有1个节点编号为1第二层有2个节点编号2、3第三层有4个节点编号4、5、6、7…第k层有 2 k − 1 2^{k-1} 2k−1个节点编号 2 k − 1 、 2 k − 1 1 、 . . . 、 2 k − 1 2^{k-1}、2^{k-1}1、...、2^k-1 2k−1、2k−11、...、2k−1。 一棵n层的满二叉树节点一共有 1 2 4 . . . 2 n − 1 2 n − 1 124...2^{n-1} 2^{n-1} 124...2n−12n−1个。 2完全二叉树 如果满二叉树只在最后一层有缺失并且缺失的节点都在最后称为完全二叉树。图1.3演示了一棵满二叉树和一棵完全二叉树。 3平衡二叉树 任意左子树和右子树的高度差不大于1称为平衡二叉树。若只有少部分子树的高度差超过1这是一棵接近平衡的二叉树。 4退化二叉树 如果树上每个节点都只有1个孩子称为退化二叉树。退化二叉树实际上已经变成了一根链表。如果绝大部分节点只有1个孩子少数有2个孩子也看成退化二叉树。 二叉树之所以应用广泛得益于它的形态。高级数据结构大部分和二叉树有关下面列举二叉树的一些优势。 1在二叉树上能进行极高效率的访问。一棵平衡的二叉树例如满二叉树或完全二叉树每一层的节点数量约是上一层数量的2倍也就是说一棵有N个节点的满二叉树树的高度是O(logN)。从根节点到叶子节点只需要走logN步例如N 100万树的高度仅有logN 20只需要20步就能到达100万个节点中的任意一个。但是如果二叉树不是满的而且很不平衡甚至在极端情况下变成退化二叉树访问效率会打折扣。维护二叉树的平衡是高级数据结构的主要任务之一。 2二叉树很适合做从整体到局部、从局部到整体的操作。二叉树内的一棵子树可以看成整棵树的一个子区间求区间最值、区间和、区间翻转、区间合并、区间分裂等用二叉树都很快捷。 3基于二叉树的算法容易设计和实现。例如二叉树用BFS和DFS搜索处理都极为简便。二叉树可以一层一层地搜索这是BFS。二叉树的任意一个子节点是以它为根的一棵二叉树这是一种递归的结构用DFS访问二叉树极容易编码。
3.2 二叉树的存储和编码
3.2.1 二叉树的存储方法 要使用二叉树首先得定义和存储它的节点。 二叉树的一个节点包括三个值节点的值、指向左孩子的指针、指向右孩子的指针。需要用一个结构体来定义二叉树。 二叉树的节点有动态和静态两种存储方法竞赛中一般采用静态方法。 1动态存储二叉树。例如写c代码数据结构的教科书一般这样定义二叉树的节点
struct Node{int value; //节点的值可以定义多个值Node *lson, *rson; //指针分别指向左右子节点
};其中value是这个节点的值lson和rson是指向两个孩子的指针。动态新建一个Node时用new运算符动态申请一个节点。使用完毕后需要用delete释放它否则会内存泄漏。动态二叉树的优点是不浪费空间缺点是需要管理不小心会出错竞赛中一般不这样用。 2用静态数组存储二叉树。在算法竞赛中为了编码简单加快速度一般用静态数组来实现二叉树。下面定义一个大小为N的结构体数组。N的值根据题目要求设定有时节点多例如N100万那么tree[N]使用的内存是12M字节不算大。
struct Node{ //静态二叉树int value; //可以把value简写为vint lson, rson; //左右孩子可以把lson、rson简写为ls、rs
}tree[N]; //可以把tree简写为ttree[i]表示这个节点存储在结构体数组的第i个位置lson是它的左孩子在结构体数组的位置rson是它的右孩子在结构体数组的位置。lson和rson指向孩子的位置也可以称为指针。 下图演示了一棵二叉树的存储圆圈内的字母是这个节点的value值。根节点存储在tree[5]上它的左孩子lson7表示左孩子存储在tree[7]上右孩子rson3存储在tree[3]。 编码时一般不用tree[0]因为0常常被用来表示空节点例如叶子节点tree[2]没有子节点就把它的子节点赋值为lson rson 0。
3.2.2 二叉树存储的编码实现 下面写代码演示上图中二叉树的建立并输出二叉树。 1C代码。第16~21行建立二叉树然后用print_tree()输出二叉树。
#include bits/stdc.h
using namespace std;
const int N100; //注意const不能少
struct Node{ //定义静态二叉树结构体char v; //把value简写为vint ls, rs; //左右孩子把lson、rson简写为ls、rs
}t[N]; //把tree简写为t
void print_tree(int u){ //打印二叉树if(u){coutt[u].v ; //打印节点u的值print_tree(t[u].ls); //继续搜左孩子print_tree(t[u].rs); //继续搜右孩子}
}
int main(){t[5].vA; t[5].ls7; t[5].rs3;t[7].vB; t[7].ls2; t[7].rs0;t[3].vC; t[3].ls9; t[3].rs6;t[2].vD; // t[2].ls0; t[2].rs0; 可以不写因为t[]是全局变量已初始化为0t[9].vE; // t[9].ls0; t[9].rs0; 可以不写t[6].vF; // t[6].ls0; t[6].rs0; 可以不写int root 5; //根是tree[5]print_tree(5); //输出 A B D C E Freturn 0;
}初学者可能看不懂print_tree()是怎么工作的。它是一个递归函数先打印这个节点的值t[u].v然后继续搜它的左右孩子。上图的打印结果是”A B D C E F”步骤如下 1首先打印根节点A 2然后搜左孩子是B打印出来 3继续搜B的左孩子是D打印出来 4D没有孩子回到BB发现也没有右孩子继续回到A 5A有右孩子C打印出来 6打印C的左右孩子E、F。 这个递归函数执行的步骤称为“先序遍历”先输出父节点然后再搜左右孩子并输出。还有“中序遍历”和“后序遍历”将在后面讲解。 2Java代码
import java.util.*;
class Main {static class Node {char v;int ls, rs;}static final int N 100;static Node[] t new Node[N];static void print_tree(int u) {if (u ! 0) {System.out.print(t[u].v );print_tree(t[u].ls);print_tree(t[u].rs);}}public static void main(String[] args) {t[5] new Node(); t[5].v A; t[5].ls 7; t[5].rs 3;t[7] new Node(); t[7].v B; t[7].ls 2; t[7].rs 0;t[3] new Node(); t[3].v C; t[3].ls 9; t[3].rs 6;t[2] new Node(); t[2].v D;t[9] new Node(); t[9].v E;t[6] new Node(); t[6].v F;int root 5;print_tree(5); // 输出 A B D C E F}
}3Python代码
N 100
class Node: # 定义静态二叉树结构体def __init__(self):self.v # 把value简写为vself.ls 0 # 左右孩子把lson、rson简写为ls、rsself.rs 0
t [Node() for i in range(N)] # 把tree简写为t
def print_tree(u):if u:print(t[u].v, end ) # 打印节点u的值print_tree(t[u].ls)print_tree(t[u].rs)
t[5].v, t[5].ls, t[5].rs A, 7, 3
t[7].v, t[7].ls, t[7].rs B, 2, 0
t[3].v, t[3].ls, t[3].rs C, 9, 6
t[2].v D # t[2].ls0; t[2].rs0; 可以不写因为t[]已初始化为0
t[9].v E # t[9].ls0; t[9].rs0; 可以不写
t[6].v F # t[6].ls0; t[6].rs0; 可以不写
root 5 # 根是tree[5]
print_tree(5) # 输出 A B D C E F3.2.3 二叉树的极简存储方法 如果是满二叉树或者完全二叉树有更简单的编码方法连lson、rson都不需要定义因为可以用数组的下标定位左右孩子。 一棵节点总数量为k的完全二叉树设1号点为根节点有以下性质 1 p 1 p 1 p1的节点其父节点是 p / 2 p/2 p/2。例如 p 4 p4 p4父亲是 4 / 2 2 4/22 4/22 p 5 p5 p5父亲是 5 / 2 2 5/22 5/22。 2如果 2 × p k 2×p k 2×pk那么 p p p没有孩子如果 2 × p 1 k 2×p1 k 2×p1k那么 p p p没有右孩子。例如 k 11 k11 k11 p 6 p6 p6的节点没有孩子 k 12 k12 k12 p 6 p6 p6的节点没有右孩子。 3如果节点 p p p有孩子那么它的左孩子是 2 × p 2×p 2×p右孩子是 2 × p 1 2×p1 2×p1。 图中圆圈内是节点的值圆圈外数字是节点存储位置。 1C代码。用 l s ( p ) ls(p) ls(p)找p的左孩子用 r s ( p ) rs(p) rs(p)找p的右孩子。 l s ( p ) ls(p) ls(p)中把 p ∗ 2 p*2 p∗2写成 p 1 p1 p1用了位运算。
#include bits/stdc.h
using namespace std;
const int N100; //注意const不能少
char t[N]; //简单地用一个数组定义二叉树
int ls(int p){return p1;} //定位左孩子也可以写成 p*2
int rs(int p){return p1 | 1;} //定位右孩子也可以写成 p*21
int main(){t[1]A; t[2]B; t[3]C;t[4]D; t[5]E; t[6]F; t[7]G;t[8]H; t[9]I; t[10]J; t[11]K;coutt[1]:lsont[ls(1)] rsont[rs(1)]; //输出 A:lsonB rsonCcoutendl;coutt[5]:lsont[ls(5)] rsont[rs(5)]; //输出 E:lsonJ rsonKreturn 0;
}2Java代码。
import java.util.Arrays;
public class Main {static int ls(int p){ return p1;}static int rs(int p){ return p1 | 1;}public static void main(String[] args) {final int N 100;char[] t new char[N];t[1]A; t[2]B; t[3]C;t[4]D; t[5]E; t[6]F; t[7]G;t[8]H; t[9]I; t[10]J; t[11]K;System.out.print(t[1]:lsont[ls(1)] rsont[rs(1)]);//输出A:lsonB rsonCSystem.out.println();System.out.print(t[5]:lsont[ls(5)] rsont[rs(5)]);//输出E:lsonJ rsonK}
}3Python代码。
N 100
t [] * N
def ls(p): return p 1
def rs(p): return (p 1) | 1t[1] A; t[2] B; t[3] C
t[4] D; t[5] E; t[6] F; t[7] G
t[8] H; t[9] I; t[10] J; t[11] Kprint(t[1] :lson t[ls(1)] rson t[rs(1)]) # 输出 A:lsonB rsonC
print(t[5] :lson t[ls(5)] rson t[rs(5)]) # 输出 E:lsonJ rsonK其实即使二叉树不是完全二叉树而是普通二叉树也可以用这种简单方法来存储。如果某个节点没有值那就空着这个节点不用方法是把它赋值为一个不该出现的值例如赋值为0或无穷大INF。这样会浪费一些空间好处是编程非常简单。
3.3 例题 二叉树是很基本的数据结构大量算法、高级数据结构都是基于二叉树的。二叉树有很多操作最基础的操作是搜索遍历二叉树的每个节点有先序遍历、中序遍历、后序遍历。这3种遍历都用到了递归函数二叉树的形态天然适合用递归来编程。 1先父序遍历父节点在最前面输出。先输出父节点再访问左孩子最后访问右孩子。上图的先序遍历结果是ABDCEF。为什么把结果分解为A-BD-CEF。父亲是A然后是左孩子B和它带领的子树BD最后是右孩子C和它带领的子树CEF。这是一个递归的过程每个子树也满足先序遍历例如CEF父亲是C然后是左孩子E最后是右孩子F。 2中父序遍历父节点在中间输出。先访问左孩子然后输出父节点最后访问右孩子。上图的中序遍历结果是DBAECF。为什么把结果分解为DB-A-ECF。DB是左子树然后是父亲A最后是右子树ECF。每个子树也满足中序遍历例如ECF先左孩子E然后是父亲C最后是右孩子F。 3后父序遍历父节点在最后输出。先访问左孩子然后访问右孩子最后输出父节点。上图的后序遍历结果是DBEFCA。为什么把结果分解为DB-EFC-A。DB是左子树然后是右子树EFC最后是父亲A。每个子树也满足后序遍历例如EFC先左孩子E然后是右孩子F最后是父亲C。 这三种遍历中序遍历是最有用的它是二叉查找树的核心。
例题 二叉树的遍历 1C代码
#include bits/stdc.h
using namespace std;
const int N 100005;
struct Node{int v; int ls, rs;
}t[N]; //tree[0]不用0表示空结点
void preorder (int p){ //求先序序列if(p ! 0){cout t[p].v ; //先序输出preorder (t[p].ls);preorder (t[p].rs);}
}
void midorder (int p){ //求中序序列if(p ! 0){midorder (t[p].ls);cout t[p].v ; //中序输出midorder (t[p].rs);}
}
void postorder (int p){ //求后序序列if(p ! 0){postorder (t[p].ls);postorder (t[p].rs);cout t[p].v ; //后序输出}
}
int main() {int n; cin n;for (int i 1; i n; i) {int a, b; cin a b;t[i].v i;t[i].ls a;t[i].rs b;}preorder(1); cout endl;midorder(1); cout endl;postorder(1); cout endl;
}
2Java代码 下面的Java代码和上面的C代码略有不同。例如在preorder()中没有直接打印节点的值而是用joiner.add()先记录下来遍历结束后一起打印这样快一些。本题 n 1 0 6 n10^6 n106规模大时间紧张。
import java.util.Scanner;
import java.util.StringJoiner;
class Main {static class Node {int v, ls, rs;Node(int v, int ls, int rs) {this.v v;this.ls ls;this.rs rs;}}static final int N 100005;static Node[] t new Node[N]; //tree[0]不用0表示空结点static void preorder(int p, StringJoiner joiner) { //求先序序列if (p ! 0) {joiner.add(t[p].v ); //不是直接打印而是先记录下来preorder(t[p].ls,joiner);preorder(t[p].rs,joiner);}}static void midorder(int p, StringJoiner joiner) { //求中序序列if (p ! 0) {midorder(t[p].ls,joiner);joiner.add(t[p].v );//中序输出midorder(t[p].rs,joiner);}}static void postorder(int p, StringJoiner joiner) { //求后序序列if (p ! 0) {postorder(t[p].ls,joiner);postorder(t[p].rs,joiner);joiner.add(t[p].v ); //后序输出}}public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();for (int i 1; i n; i) {int a sc.nextInt(), b sc.nextInt();t[i] new Node(i, a, b);}StringJoiner joiner new StringJoiner( ); preorder(1, joiner); System.out.println(joiner); joiner new StringJoiner( );midorder(1, joiner); System.out.println(joiner);joiner new StringJoiner( );postorder(1, joiner); System.out.println(joiner);}
}3Python代码
N 100005
t [0] * N # tree[0]不用0表示空结点
class Node:def __init__(self, v, ls, rs):self.v vself.ls lsself.rs rsdef preorder(p): # 求先序序列if p ! 0:print(t[p].v, end ) # 先序输出preorder(t[p].ls)preorder(t[p].rs)def midorder(p): # 求中序序列if p ! 0:midorder(t[p].ls)print(t[p].v, end ) # 中序输出midorder(t[p].rs)def postorder(p): # 求后序序列if p ! 0:postorder(t[p].ls)postorder(t[p].rs)print(t[p].v, end ) # 后序输出n int(input())
for i in range(1, n1):a, b map(int, input().split())t[i] Node(i, a, b)preorder(1); print()
midorder(1); print()
postorder(1); print()3.4 习题
完全二叉树的权值 FBI树 American Heritage 求先序排列 文章转载自： http://www.morning.fwqgy.cn.gov.cn.fwqgy.cn http://www.morning.rwrn.cn.gov.cn.rwrn.cn http://www.morning.ddzqx.cn.gov.cn.ddzqx.cn http://www.morning.srkwf.cn.gov.cn.srkwf.cn http://www.morning.ywqsk.cn.gov.cn.ywqsk.cn http://www.morning.skpdg.cn.gov.cn.skpdg.cn http://www.morning.sbrxm.cn.gov.cn.sbrxm.cn http://www.morning.jrwbl.cn.gov.cn.jrwbl.cn http://www.morning.qnhpq.cn.gov.cn.qnhpq.cn http://www.morning.rgrz.cn.gov.cn.rgrz.cn http://www.morning.wcrcy.cn.gov.cn.wcrcy.cn http://www.morning.hhkzl.cn.gov.cn.hhkzl.cn http://www.morning.wjwfj.cn.gov.cn.wjwfj.cn http://www.morning.gqksd.cn.gov.cn.gqksd.cn http://www.morning.qlsbz.cn.gov.cn.qlsbz.cn http://www.morning.qmsbr.cn.gov.cn.qmsbr.cn http://www.morning.qwnqt.cn.gov.cn.qwnqt.cn http://www.morning.rhsg.cn.gov.cn.rhsg.cn http://www.morning.iznek.com.gov.cn.iznek.com http://www.morning.lmqw.cn.gov.cn.lmqw.cn http://www.morning.bssjp.cn.gov.cn.bssjp.cn http://www.morning.fynkt.cn.gov.cn.fynkt.cn http://www.morning.mgwdp.cn.gov.cn.mgwdp.cn http://www.morning.zylrk.cn.gov.cn.zylrk.cn http://www.morning.pjjkz.cn.gov.cn.pjjkz.cn http://www.morning.ahlart.com.gov.cn.ahlart.com http://www.morning.hjssh.cn.gov.cn.hjssh.cn http://www.morning.skql.cn.gov.cn.skql.cn http://www.morning.qrhh.cn.gov.cn.qrhh.cn http://www.morning.krjyq.cn.gov.cn.krjyq.cn http://www.morning.nqlnd.cn.gov.cn.nqlnd.cn http://www.morning.hwljx.cn.gov.cn.hwljx.cn http://www.morning.qdsmile.cn.gov.cn.qdsmile.cn http://www.morning.swlwf.cn.gov.cn.swlwf.cn http://www.morning.qgmwt.cn.gov.cn.qgmwt.cn http://www.morning.kzqpn.cn.gov.cn.kzqpn.cn http://www.morning.rnqyy.cn.gov.cn.rnqyy.cn http://www.morning.sypzg.cn.gov.cn.sypzg.cn http://www.morning.ywndg.cn.gov.cn.ywndg.cn http://www.morning.jtnph.cn.gov.cn.jtnph.cn http://www.morning.pkmw.cn.gov.cn.pkmw.cn http://www.morning.tpnxj.cn.gov.cn.tpnxj.cn http://www.morning.wkws.cn.gov.cn.wkws.cn http://www.morning.xlbtz.cn.gov.cn.xlbtz.cn http://www.morning.kgphd.cn.gov.cn.kgphd.cn http://www.morning.mjbkp.cn.gov.cn.mjbkp.cn http://www.morning.fgkrh.cn.gov.cn.fgkrh.cn http://www.morning.nqlcj.cn.gov.cn.nqlcj.cn http://www.morning.npxcc.cn.gov.cn.npxcc.cn http://www.morning.rgksz.cn.gov.cn.rgksz.cn http://www.morning.shxmr.cn.gov.cn.shxmr.cn http://www.morning.wnnts.cn.gov.cn.wnnts.cn http://www.morning.mstrb.cn.gov.cn.mstrb.cn http://www.morning.dkbsq.cn.gov.cn.dkbsq.cn http://www.morning.gmmxh.cn.gov.cn.gmmxh.cn http://www.morning.wttzp.cn.gov.cn.wttzp.cn http://www.morning.jhfkr.cn.gov.cn.jhfkr.cn http://www.morning.zzqgc.cn.gov.cn.zzqgc.cn http://www.morning.zwpzy.cn.gov.cn.zwpzy.cn http://www.morning.hsdhr.cn.gov.cn.hsdhr.cn http://www.morning.wskn.cn.gov.cn.wskn.cn http://www.morning.ptqpd.cn.gov.cn.ptqpd.cn http://www.morning.txmlg.cn.gov.cn.txmlg.cn http://www.morning.yrhsg.cn.gov.cn.yrhsg.cn http://www.morning.jqhrk.cn.gov.cn.jqhrk.cn http://www.morning.jbpdk.cn.gov.cn.jbpdk.cn http://www.morning.wlbwp.cn.gov.cn.wlbwp.cn http://www.morning.kdgcx.cn.gov.cn.kdgcx.cn http://www.morning.bpmnj.cn.gov.cn.bpmnj.cn http://www.morning.xqknl.cn.gov.cn.xqknl.cn http://www.morning.ycmpk.cn.gov.cn.ycmpk.cn http://www.morning.pqfbk.cn.gov.cn.pqfbk.cn http://www.morning.mdwtm.cn.gov.cn.mdwtm.cn http://www.morning.jsmyw.cn.gov.cn.jsmyw.cn http://www.morning.jqllx.cn.gov.cn.jqllx.cn http://www.morning.xbnkm.cn.gov.cn.xbnkm.cn http://www.morning.ndxmn.cn.gov.cn.ndxmn.cn http://www.morning.gcszn.cn.gov.cn.gcszn.cn http://www.morning.mdwtm.cn.gov.cn.mdwtm.cn http://www.morning.gfkb.cn.gov.cn.gfkb.cn
