二叉树的种类:
1.满二叉树
一棵二叉树只有度为0的结点和度为2的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。
2.完全二叉树
除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层(h从1开始),则该层包含 1~ 2^(h-1) 个节点。
之前的优先级队列其实是一个堆,堆就是一棵完全二叉树,同时保证父子节点的顺序关系。
3.二叉搜索树
前面介绍的树,都没有数值的,而二叉搜索树是有数值的了,二叉搜索树是一个有序树。
4.平衡二叉搜索树
平衡二叉搜索树:又被称为AVL(Adelson-Velsky and Landis)树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
二叉树的存储方式:
二叉树可以链式存储,也可以顺序存储。
那么链式存储方式就用指针, 顺序存储的方式就是用数组。顾名思义就是顺序存储的元素在内存是连续分布的,而链式存储则是通过指针把分布在各个地址的节点串联一起。
二叉树的遍历方式:
二叉树主要有两种遍历方式:
前序遍历:根左右
中序遍历:左根右
后序遍历:左右根
代码定义:
递归算法三要素:
1、确定递归函数的参数和返回值:确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数, 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2、确定终止条件:写完了递归算法, 运行的时候,经常会遇到栈溢出的错误,就是没写终止条件或者终止条件写的不对,操作系统也是用一个栈的结构来保存每一层递归的信息,如果递归没有终止,操作系统的内存栈必然就会溢出。
3、确定单层递归的逻辑:确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
以下是二叉树前序、中序、后序遍历的代码模板:
result数组是保存遍历的结果,遍历的值保存在这个创建的数组中
// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
preorder(root, result);
return result;
}
public void preorder(TreeNode root, List<Integer> result) {
if (root == null) {
return;
}
result.add(root.val);
preorder(root.left, result);
preorder(root.right, result);
}
}
// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
inorder(root, res);
return res;
}
void inorder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
inorder(root.left, list);
list.add(root.val); // 注意这一句
inorder(root.right, list);
}
}
// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
postorder(root, res);
return res;
}
void postorder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
postorder(root.left, list);
postorder(root.right, list);
list.add(root.val); // 注意这一句
}
}
这需要具体拿例子来理解
前序遍历:
前序遍历是中左右,每次先处理的是中间节点,那么先将根节点放入栈中,然后将右孩子加入栈,再加入左孩子。
为什么要先加入 右孩子,再加入左孩子呢? 因为这样出栈的时候才是中左右的顺序
中序遍历:
在迭代的过程中,其实我们有两个操作:
分析一下为什么刚刚写的前序遍历的代码,不能和中序遍历通用呢,因为前序遍历的顺序是中左右,先访问的元素是中间节点,要处理的元素也是中间节点,所以刚刚才能写出相对简洁的代码,因为要访问的元素和要处理的元素顺序是一致的,都是中间节点
那么再看看中序遍历,中序遍历是左中右,先访问的是二叉树顶部的节点,然后一层一层向下访问,直到到达树左面的最底部,再开始处理节点(也就是在把节点的数值放进result数组中),这就造成了处理顺序和访问顺序是不一致的。
那么在使用迭代法写中序遍历,就需要借用指针的遍历来帮助访问节点,栈则用来处理节点上的元素。
后序遍历:
再来看后序遍历,先序遍历是中左右,后续遍历是左右中,那么我们只需要调整一下先序遍历的代码顺序,就变成中右左的遍历顺序,然后在反转result数组,输出的结果顺序就是左右中了,如下图:
所以后序遍历只需要前序遍历的代码稍作修改就可以了
我们用迭代法写出了二叉树的前后中序遍历,可以看出前序和中序是完全两种代码风格,并不像递归写法那样代码稍做调整,就可以实现前后中序。
这是因为前序遍历中访问节点(遍历节点)和处理节点(将元素放进result数组中)可以同步处理,但是中序就无法做到同步!
前中后序代码如下:
// 前序遍历顺序:中-左-右,入栈顺序:中-右-左
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
result.add(node.val);
if (node.right != null){
stack.push(node.right);
}
if (node.left != null){
stack.push(node.left);
}
}
return result;
}
}
// 中序遍历顺序: 左-中-右 入栈顺序: 左-右
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()){
if (cur != null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
result.add(cur.val);
cur = cur.right;
}
}
return result;
}
}
// 后序遍历顺序 左-右-中 入栈顺序:中-左-右 出栈顺序:中-右-左, 最后翻转结果
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null){
return result;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.pop();
result.add(node.val);
if (node.left != null){
stack.push(node.left);
}
if (node.right != null){
stack.push(node.right);
}
}
Collections.reverse(result);
return result;
}
}
这种写法得需要记住这个模板,其实拿对应的例子,自己走一遍过程就明白了
比如说中序的时候,他是先处理的时候将根节点放进栈中,之后判断栈不为空就开始循环,给他再弹出去然后按照正常的放入栈中的顺序去放,就比如说中序放入栈中就是右中左的顺序,然后每次都得在中节点后加一个null进行标记,其他就是正常一样的
然后就是每次循环的时候取得是栈顶的位置,节点指针位置不为空的话就继续往下走,右中左的顺序,只有在遇到节点为空的时候就直接做弹出空值操作,定位栈顶的元素再弹出,最后放入结果数组中,其实不难理解就是遇到空值的时候其实就是到二叉树的最深处了
动画过程代码模板放在下边做体会吧,死记住就可以:
//统一迭代中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> st = new Stack<>();
if (root != null) st.push(root);
while (!st.empty()) {
TreeNode node = st.peek();
if (node != null) {
st.pop(); // 将该节点弹出,避免重复操作,下面再将右中左节点添加到栈中
if (node.right!=null) st.push(node.right); // 添加右节点(空节点不入栈)
st.push(node); // 添加中节点
st.push(null); // 中节点访问过,但是还没有处理,加入空节点做为标记。
if (node.left!=null) st.push(node.left); // 添加左节点(空节点不入栈)
} else { // 只有遇到空节点的时候,才将下一个节点放进结果集
st.pop(); // 将空节点弹出
node = st.peek(); // 重新取出栈中元素
st.pop();
result.add(node.val); // 加入到结果集
}
}
return result;
}
}
//统一迭代前序遍历
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> st = new Stack<>();
if (root != null) st.push(root);
while (!st.empty()) {
TreeNode node = st.peek();
if (node != null) {
st.pop(); // 将该节点弹出,避免重复操作,下面再将右中左节点添加到栈中
if (node.right!=null) st.push(node.right); // 添加右节点(空节点不入栈)
if (node.left!=null) st.push(node.left); // 添加左节点(空节点不入栈)
st.push(node); // 添加中节点
st.push(null); // 中节点访问过,但是还没有处理,加入空节点做为标记。
} else { // 只有遇到空节点的时候,才将下一个节点放进结果集
st.pop(); // 将空节点弹出
node = st.peek(); // 重新取出栈中元素
st.pop();
result.add(node.val); // 加入到结果集
}
}
return result;
}
}
//统一迭代后序遍历
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> st = new Stack<>();
if (root != null) st.push(root);
while (!st.empty()) {
TreeNode node = st.peek();
if (node != null) {
st.pop(); // 将该节点弹出,避免重复操作,下面再将右中左节点添加到栈中
st.push(node); // 添加中节点
st.push(null); // 中节点访问过,但是还没有处理,加入空节点做为标记。
if (node.right!=null) st.push(node.right); // 添加右节点(空节点不入栈)
if (node.left!=null) st.push(node.left); // 添加左节点(空节点不入栈)
} else { // 只有遇到空节点的时候,才将下一个节点放进结果集
st.pop(); // 将空节点弹出
node = st.peek(); // 重新取出栈中元素
st.pop();
result.add(node.val); // 加入到结果集
}
}
return result;
}
}
文章浏览阅读1.5k次。pyspider 是一个用python实现的功能强大的网络爬虫系统,能在浏览器界面上进行脚本的编写,功能的调度和爬取结果的实时查看,后端使用常用的数据库进行爬取结果的存储,还能定时设置任务与任务优先级等。本篇文章只是对这个框架使用的大体介绍,更多详细信息可见官方文档。安装首先是环境的搭建,网上推荐的各种安装命令,如: pip install pyspider但是因为各种权限的..._response.doc
文章浏览阅读3.2k次。vue + blockly 自定义块、工具箱、主题自定义块建议使用 Blockly Developer Tools 方便而且选择多样,随时生成块代码。自定义块块由三个组件组成:块定义对象:定义块的外观和行为,包括文本、颜色、字段和连接。工具箱引用:对工具箱 XML 中块类型的引用,因此用户可以将其添加到工作区。生成器函数:生成此块的代码字符串。它总是用 JavaScript 编写,即使目标语言不是 JavaScript。通过 Blockly Developer Tools _blockly vue
文章浏览阅读158次。最新笔记本显卡性能排名总表最新笔记本显卡性能排名总表以下排名整理自国外网站,以性能排名,越往前性能越好第一梯队:高端显卡GeForce GTX 280M SLIMobility Radeon HD 4870 X2GeForce GTX 260M SLIGeForce 9800M GTX SLIGeForce GTX 280MGeForce 9800M G..._mobility radeon x700 win98
文章浏览阅读2.6k次。解决Python词云库wordcloud不显示中文的问题2018-11-25背景:wordcloud是基于Python开发的词云生成库,功能强大使用简单。github地址:https://github.com/amueller/word_cloudwordcloud默认是不支持显示中文的,中文会被显示成方框。安装:安装命令:pip install wordcloud解决:经过测试发现不支持显示中文..._词云python代码无法输出文字
文章浏览阅读807次。扩展。_jmap 在线分析
文章浏览阅读1.1w次。随着炎热夏季的到来,当玩游戏正爽的时候,电脑突然死机了,自动关机了,是不是有想给主机一脚的冲动呢?这个很大的原因是因为CPU温度过高导致的。很多新手玩家可能都有一个疑虑,cpu温度多少以下正常?有些说是60,有些说是70,到底多高CPU温度不会死机呢?首先我们先看看如何查看CPU的温度。下载鲁大师并安装,运行鲁大师软件,即可进入软件界面,并点击温度管理,即可看到电脑各个硬件的温度。鲁大师一般情况下..._台式机玩游戏温度多少正常
文章浏览阅读5.5k次。1.问题说明openweather注册不成功,无法进行机器人验证2.解决方法无法收到谷歌提供的机器人验证信息,科学上网可解决。科学上网用来注册,后续登录和获取数据不需要,直接访问即可。_openweather api 创建账户被禁止了
文章浏览阅读4.7k次,点赞2次,收藏4次。一般需要ssh两个账户或两个设备才能有权限传输数据时经常遇到下面情况:我们一般连接跳板机使用的用户权限很小,能访问的文件不多,要是我想传输数据到我的设备上,却必须用跳板机连接设备怎么办?(别告诉我先在设备上搭个FTP服务器)下载winscp: 下载地址https://winscp.net/eng/downloads.php然后傻瓜式安装一键到底安装好就是配置访问服务器1、直接..._winscp 隧道 跳板机上的密码
文章浏览阅读1.3k次。JAVA语言概括和基本类型,数组,枚举_enum c++ java
文章浏览阅读316次。路由的概念路由器它称之为网关设备。路由器就是用于连接不同网络的设备路由器是位于OSI模型的第三层。路由器通过路由决定数据的转发。网关的背景:当时每家计算机厂商,用于交换数据的通信程序(协议)和数据描述格式各不相同。因此,就把用于相互转换这些协议和格式的计算机称为网关。路由器与三层交换器的对比路由协议对比路由器的作用:1.路由寻址2.实现不同网络之间相连的功能3.通过路由决定数据的转发,转发策略称为 路由选择。VLAN相关技术什么是VLAN?中文名称叫:虚拟局域网。虚_路由和vlan
文章浏览阅读2.8w次,点赞6次,收藏22次。设置div背景颜色透明度,内部元素不透明:.demo{ background-color:rgba(255,255,255,0.15) } 错误方式:.demo{ background-color:#5CACEE;opacity:0.75;} 这样会导致div里面的元素内容和背景颜色一起变透明只针对谷歌浏览器的测试_div设置透明度,里面的内容不透明
文章浏览阅读563次。1.[ u]文字:在文字的位置可以任意加入您需要的字符,显示为下划线效果。2.[ align=center]文字:在文字的位置可以任意加入您需要的字符,center位置center表示居中,left表示居左,right表示居右。5.[ color=red]文字:输入您的颜色代码,在标签的中间插入文字可以实现文字颜色改变。6.[ SIZE=数字]文字:输入您的字体大小,在标签的中间插入文..._discuzcode 大全