手机网站怎么做微信登陆,做的网站怎么发布,华为官方网站,如何 建公司网站本篇会加入个人的所谓鱼式疯言
❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言
而是理解过并总结出来通俗易懂的大白话,
小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的.
#x1f92d;#x1f92d;#x1f92d;可能说的不是那么严谨.但小编初心是能让更多人…本篇会加入个人的所谓鱼式疯言
❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言
而是理解过并总结出来通俗易懂的大白话,
小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的.
可能说的不是那么严谨.但小编初心是能让更多人能接受我们这个概念 前言
在上篇中我们学习了 二叉树的基本概念 以及他们的特性结论并运用到了 具体的题目 中去解决问题 。
而在本篇中小编讲继续学习 二叉树 的基本操作, 主要围绕着我们 遍历二叉树 来讲解 人狠话不多下面让我们切入主题吧
目录 二叉树的遍历初识 前序遍历 中序遍历
4.后序遍历 层序遍历 二叉树遍历的应用
一. 二叉树的遍历初识
学习二叉树的结构最简单的方式就是遍历所谓遍历 是指 沿着某条搜索路线依次树中的某个节点均做一次访问 访问节点所做的操作 依赖于要解决的各种实际问题。
遍历是二叉树是最重要的操作之一是 二叉树上进行其他运算 的基础
1. 二叉树的遍历简介 在遍历二叉树时 如果没有进行某种约定每个人都按照自己的方式来遍历 得到的结果就比较乱 如果我们按照某个规则 来遍历 则每个人对于遍历结果都是相同的 如果 N 代表 根节点L 代表左节点 R 代表 右节点 那根据遍历的的节点有以下的遍历方式。 NLR 前序遍历 (先序遍历) 根据 根——》 左 ——》 右 的顺序对二叉树进行遍历 LNR : 中序遍历 根据 左——》 根——》 右 的顺序 对二叉树进行遍历 LRN 后序遍历 : 根据 左——》 右 ——》 根 的顺序对二叉树进行遍历
详细的遍历方式 小编下面细讲哦
在遍历二叉树之前 我们先用一下代码简单的 构建一颗二叉树
public class MyBinaryTree {public static class TreeNode {public TreeNode left;public TreeNode right;public char val;public TreeNode(char val) {this.val val;}}private TreeNode root;// 构造二叉树public TreeNode createBinaryTree() {rootnew TreeNode(A);TreeNode Bnew TreeNode(B);TreeNode Dnew TreeNode(D);TreeNode Enew TreeNode(E);TreeNode Hnew TreeNode(H);TreeNode Cnew TreeNode(C);TreeNode Fnew TreeNode(F);TreeNode Gnew TreeNode(G);root.leftB;B.leftD;B.rightE;E.rightH;root.rightC;C.leftF;C.rightG;return root;}// 前序遍历
void preOrder(Node root);
// 中序遍历
void inOrder(Node root);
// 后序遍历
void postOrder(Node root);}二. 前序遍历
1. 前序遍历的特点 按照从左子树开始走一直 往下递归每一步所走的路径成为我们的根先遍历完根之后。 按照根左右的顺序 当我们走完每个根节点的左子树 时 先往下递 再往回归 , 左节点成为新的根 会到最初的根节点之后再向右子树进行 先递后归 的操作, 动画演示 2. 前序遍历的实现
因为前序遍历有 递归 和 非递归 的两种方式 但 遍历的原理和方向都是一致的
在本篇文章中。小编都会带着小伙伴们 一 一 实现 1. 前序遍历的递归实现 // 前序遍历public void FirstDisplay(TreeNode root) {if (rootnull) {return;}System.out.print(root.val );FirstDisplay(root.left);FirstDisplay(root.right);}这里的代码的递归思路就是完美的按照我们遍历方向来的 先访问后递归 2. 前序遍历的非递归实现
// 非递归的前序遍历public void FirstDisplayNo(TreeNode root) {// 先创建一个栈来存放树的每个节点StackTreeNode stacknew Stack();// 先把艮节点创建一遍TreeNode curroot;/*** 外循环主要遍历 右边的节点* 用于出栈的数据* 并让节点向右移动*/while (cur ! null || !stack.empty()) {/*** 在这个内循环中* 当往左走就添加数据一直到为 null 结束* 并进行打印*/while (cur ! null) {// 先打印System.out.print(cur.val );// 打印完就入栈stack.add(cur);// 节点向左移动curcur.left;}// 出栈存放数据curstack.pop();// 并向右走curcur.right;// 当再次循环时如果左边还有节点就会继续存放}System.out.println();} 非递归的 实现步骤 先定义一个栈 来记录我们每次遍历过的 根节点 先让根节点一直 向左走 当遍历完我们的 左子树 也就是我们的 root null 时候 并且入栈 记录下来以便后面我们遍历 右子树 然后出栈 开始 向右走 遍历我们的 右子树 当整个栈为 null 并且到达的这个节点 cur 也为 null 就意味着遍历完整个 二叉树所有的节点 鱼式疯言
无论是 递归还是非递归的 前序遍历 , 我们的 前序遍历思路就是 先走根 根走完走左 左走完回到根 再走右 一层一层的走 一步一步的回 。 细节处理
在代码上我们要注意的就是这个当节点为 null 也就意味着我们要开始 回退 到 上一个节点
二. 中序遍历 1. 中序遍历的特点
我们知道 中序遍历 是以 左- 根-右的顺序 进行遍历 我们先从 走左边 还是让每个左节点先成为新的根 当这个新的根的 左子树 都走完之后 才能真正访问我们当前 新的节点。 以此类推我们新的节点访问结束后就会进行回退到前一个旧的节点继续访问最终当整个 左子树走完 并且 访问完我们的根 就遍历我们的右子树 最终回到我们整颗树的 根节点 动画演示 2.中序遍历的实现 1.中序遍历的递归实现
// 中序遍历
public void middleDisplay(TreeNode root) {if (rootnull) {return;}middleDisplay(root.left);System.out.print(root.val );middleDisplay(root.right);
}这里的代码的递归思路就是完美的按照我们遍历方向来的 先递归后访问 小编在这里就 不赘述 了 2. 中序遍历的非递归实现
// 非递归的中序遍历public void middleDisplayNo (TreeNode root) {// 创建一个栈用于回退节点StackTreeNode stacknew Stack();// 先放根节点TreeNode curroot;/*** 外循环主要用于遍历 右边* 更是用于出栈的回退*/while (cur ! null || !stack.empty()) {/*** 内循环先遍历下去* 边遍历边存放*/while (cur ! null) {stack.add(cur);curcur.left;}// 出栈最后一个无左节点的左子树curstack.pop();// 打印该节点System.out.print(cur.val );// 再往右走curcur.right;}System.out.println();}非递归的实现步骤
我们先定义一个 栈 用来存储走过的每个 左子树的节点 先 往左边 的节点走先整个左子树 的每个节点都入栈 当 这个节点 为 null 就 停止入栈 然后进行出栈 出栈的时候我们就可以对该节点进行打印访问 并且向 右子树节点 开始走 当整个栈为 null 并且 该节点也为 null 也就意味着遍历完二叉树 所有的节点
鱼式疯言
中序遍历的最核心的要点就是 无论是 递归 还是 非递归 的 中序遍历 一定要先走完每个左子树 当我们进行 回退 的时候。 才轮的到该 根节点去遍历 最后才走 右子树的一种 顺序. 三. 后序遍历
1. 后序遍历的特点 后序遍历的顺序就是 左-右-根 的顺序 还是先走左边的节点让 左边的节点 成为 新的根 直到找到走完整个 左子树 回退后继续走 右子树当 右子树走完之后回去的根节点就是我们要 访问 的 动画演示 2. 后序遍历的实现 1. 后序遍历的递归实现 // 后序遍历public void lastDisplay(TreeNode root) {if (rootnull) {return;}lastDisplay(root.left);lastDisplay(root.right);System.out.print(root.val );}这里的代码的递归思路就是完美的按照我们遍历方向来的 先递归后访问 小编在这里就 不赘述 了 2. 后序遍历的非递归实现 // 非递归的后序遍历public void lastDisplayNo (TreeNode root) {StackTreeNode stacknew Stack();TreeNode curroot;TreeNode flgnull;while (cur ! null || !stack.empty()) {while (cur ! null) {stack.add(cur);curcur.left;}TreeNode topstack.peek();if (top.right null || flgtop.right) {System.out.print(top.val );flgtop;stack.pop();} else {curtop.right;}}System.out.println();}非递归的实现思路
我们先定义一个栈用来存放节点 而这里存放的节点有可能是 左子树的节点也有可能是 右子树的节点 先向左走让左子树的节点先入栈 然后 查看栈顶元素如果栈顶元素的右节点 为 null 我们就 打印访问 该节点 如果栈顶元素的 右节点 不为 null , 我们就 让 该节点 向右走 , 并且入栈 以此循环往复当 栈为 null 并且 节点 cur 也为 null 说明我们已经遍历完这个 二叉树所有的节点 鱼式疯言
无论是 非递归还是递归实现 对二叉树的 后序遍历 小伙伴们只需要记住一点 后序遍历 一定是 两边先走完 ,最后回到我们的根节点才 访问 的 小伙伴们一定要把每个节点都看出一颗独立的树。每个节点 都是一个 独立的根节点 来理解我们的 三大遍历
TreeNode flg nullif (top.right null || flgtop.right) {System.out.print(top.val );flgtop;stack.pop();} 细节处理 我们需要用一个 flg 来记录上一个已经 访问过 的节点判断 是否访问过 防止再次让 top 向右走继续入栈 否则会进入 死循环
四. 层序遍历
谈及完前面的 三大遍历 这些是我们 操作二叉树的根本 但还有还要介绍一种 比较特殊的遍历 1. 层序遍历的特点 二叉树 层序遍历 的方向是从 根节点按照 从上而下从左到右 的顺序进行遍历 二叉树的每一个节点 动画演示 2. 层序遍历的实现
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/class Solution {ListListInteger Snew ArrayListListInteger();public ListListInteger levelOrder(TreeNode root) {if(rootnull) {return S;}creatOrder(root,0);return S;}public void creatOrder(TreeNode root,int i) {if(rootnull) {return ;}if(S.size()i) {S.add(new ArrayListInteger());}S.get(i).add(root.val);creatOrder(root.left,i1);creatOrder(root.right,i1);}
}具体实现步骤 我们用一个 二维数组二维顺序表 来存储每一个节点二叉树 每一层代表是二维数组的 每一行 在这二叉树每一层的行中从左往右的节点 代表二维数组的 每一列 当二叉树从 左子树 开始递归 意味着先存储 每一行 的 二叉树的节点 当二叉树向 右子树 开始递归 意味着存储 每一列 的 二叉树的节点 最终当整个二叉树完全递归就意味着 全部的节点都存储在 这个二维数组 (二维顺序表) 中
鱼式疯言 if(S.size()i) {S.add(new ArrayListInteger());}细节处理 每新添加 一行数据 需要 扩容 就是需要再 实例化一个顺序表 已有的行数就 不需要了 小伙伴们有没有发现二叉树的层序遍历本质上和我们的 完全二叉树的定义 是一样的都是满足 自上而下自左而右 的特点 六. 二叉树遍历的应用
学习完了 二叉树遍历小伙伴们是时候 牛刀小试 一下了
1. 习题一
1.某完全二叉树按层次输出同一层从左到右的序列为 ABCDEFGH 。该完全二叉树的前序序列为()
A: ABDHECFG
B: ABCDEFGH
C: HDBEAFCG
D: HDEBFGCA
题目解析
我们知道了二叉树的 层序遍历 , 并且小伙伴们还有没有注意一个条件就是 完全二叉树 完全二叉树的特点就是 自上而下 自左而右 节点不间断 那么我们不妨画个草图吧 画出草图我们就很明显的知道了答案选 A
2. 习题二
2.二叉树的先序遍历和中序遍历如下先序遍历EFHIGJK;中序遍历HFIEJKG.则二叉树根结点为()
A: E
B: F
C: G
D: H
题目解析
此题题目就是 答案 我们知道前序遍历 是从 根节点 开始的 , 所以 第一个访问出来的节点 就是我们的 根节点
故答案选A
3. 习题三
3.设一课二叉树的中序遍历序列badce后序遍历序列bdeca则二叉树前序遍历序列为()
A: adbce
B: decab
C: debac
D: abcde
题目解析
此题的精髓就在于我们要根据 中序遍历 和 后序遍历 画出草图 根据草图得到我们的 前序遍历 画草图的方法
方法 先根据后序遍历寻找 根节点
对于 后序遍历 来说根节点是从右往左 然后结合 中序遍历的特点 来确定 左右节点 的位置
故此题答案选: D
4. 习题四
4.某二叉树的后序遍历序列与中序遍历序列相同均为 ABCDEF 则按层次输出(同一层从左到右)的序列为()
A: FEDCBA
B: CBAFED
C: DEFCBA
D: ABCDEF
题目解析 :
此题的精髓就在于我们要根据 中序遍历 和 后序遍历 画出草图 根据草图得到我们的 层序遍历 依照上一题的方法我们成功画出草图最终得到我们的层序遍历
故答案选: A
鱼式疯言
独家秘方 对于我们已知 前序和中序 遍历我们的方法就是根据 前序遍历从左往右 找根节点然后结合 中序遍历 画出草图 对于 我们已知的 后序和中序 遍历 我们的方法是 根据 后序遍历 从右往左找根节点 然后结合中序遍历 画出草图 对于上述题目来说 画图是 根本
总结 . 二叉树的遍历初识 我们通过基本的概念知道了二叉树是通过一定 规则和方向 来遍历我们 每一个节点 . 前序遍历 : 本源是 根-左-右的方向遍历 . 中序遍历 本源是 左-根-右的方向遍历 .后序遍历 本质上还是根据 左-右-根的方向遍历 . 层序遍历 遵循一个 自上而下 自左而右 的顺序遍历 . 二叉树遍历的应用 我们主打一个对于这四种遍历的性质的理解和应用来画图解题 如果觉得小编写的还不错的咱可支持 三连 下 (定有回访哦) , 不妥当的咱请评论区 指正 希望我的文章能给各位宝子们带来哪怕一点点的收获就是 小编创作 的最大 动力
