深圳营销网站建设联系方式,苏州市建设交通高等学校网站,seo快速排名优化,哈尔滨工程招投标信息网1. 树型结构 1.1 认识树 在学习二叉树之前我们需要了解一下树型结构
树是一种非线性的数据结构,它是由n个结点组成的一个有层次关系的集合,看起来像个倒挂的树,也就是根朝上,枝叶朝下. 特点: 1. 根结点没有前驱结点 2. 除了根结点外其他的结点被分为互不相交的集合,每个集合又…1. 树型结构 1.1 认识树 在学习二叉树之前我们需要了解一下树型结构
树是一种非线性的数据结构,它是由n个结点组成的一个有层次关系的集合,看起来像个倒挂的树,也就是根朝上,枝叶朝下. 特点: 1. 根结点没有前驱结点 2. 除了根结点外其他的结点被分为互不相交的集合,每个集合又是一棵类似的子树.每棵子树的根结点都只有一个前驱,有0或多个后继. 3. 树是递归定义的 1.2 树的概念
重点: 结点的度: 一个结点含有子树的个数为结点的度. 树的度: 所有结点的最大的度就是树的度. 叶子结点(终端结点): 度为0的结点. 双亲结点(父节点): 如果一个结点含有子节点,那么这个结点就是其子节点的父节点. 孩子结点(子节点): 一个结点的子树所含有的根结点称为该结点的子节点. 根结点: 一棵树没有双亲的结点. 结点的层次: 从根开始定义,根为第一层,根的子节点为第二层... 树的深度: 指的是从根结点(度为0)自顶向下逐层累加至该结点时的深度.树的深度十数中最大结点的深度. 树的高度: 结点的高度指从该结点最底层的叶子节(度为0)点出发,自定向上逐层累加至该结点的高度.树的高度是树中高度最大的结点的高度. 以下了解即可 非终端结点(分支结点): 度不为0的结点. 兄弟结点: 有相同父亲的结点互称为兄弟结点. 堂兄弟结点: 双亲在同一层的结点互为堂兄弟结点. 结点的祖先: 从根到该结点所经分支上的所有结点. 子孙: 某结点经由下面的结点就是该结点的子孙. 森林: 由m棵互补相交的树组成的集合为森林. 1.3 树的表示形式 树的存储方法有很多表示方式: 双亲表示法,孩子表示法,孩子双亲表示法,孩子兄弟表示法 主要了解孩子兄弟表示法: 然后树型结构的话主要就应用在我们的文件和目录管理上 2. 二叉树 2.1 概念
二叉树: 每个结点的度都是2
如果一棵树是二叉树,那么它的每一棵子树都是二叉树,二叉树是有序树 合成二叉树的结构 2.2 俩种特殊的二叉树
满二叉树: 一棵二叉树如果每层的结点数都达到最大值则这棵二叉树就是满二叉树。也就是说如果一棵二叉树的层数为K且结点总数是2^(k -1) 则它就是满二叉树。简而言之就是每层结点都达到最大值:2^(k - 1); 完全二叉树: 全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树简而言之就是从上到下从左到右依次存放,不能有割开的 满二叉树是一种特殊的完全二叉树 2.3 二叉树的性质
1. 若规定根结点的层数为1则一棵非空二叉树的第i层上最多有2^(i - 1) (i0)个结点. 2. 若规定只有根结点的二叉树的深度为1则深度为K的二叉树的最大结点数是 2^k -1(k0). 3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0n21 4. 具有n个结点的完全二叉树的深度k为 log2(n-1)上取整,2在这里为底数 5. 对于具有n个结点的完全二叉树如果按照从上至下从左至右的顺序对所有节点从0开始编号则对于序号为i的结点有
若i0双亲序号(i-1)/2i0i为根结点编号无双亲结点
若2i1n左孩子序号2i1否则无左孩子
若2i2n右孩子序号2i2否则无右孩子 2.3.1 一些相关计算题
第一题: 第二题和第三题: 第四题: 2.4 二叉树的遍历
遍历指的是 沿着某条路线遍历
前序遍历(先根遍历): 根 - 左子树 - 右子树
中序遍历: 左子树 - 根 - 右子树
后序遍历: 左子树 - 右子树 - 根
层次遍历: 从左到右从上到下依次遍历 2.4.1 一些相关的题目
题目一: 题目二: 题目三: 题目四 题目五: 问:如果给你一个前序和后序能否创建一个二叉树?
前序和后序不能创建一个二叉树: 因为前序和后序确定的都是根,不能确定左右.
2.5 二叉树的底层实现 2.5.1 前置准备
我们来自己实现一个二叉树,为了更好的理解二叉树,我们先手动连接一个二叉树.在这之前我先介绍一些我们自定义的属性和类.首先我们先创建结点内部类,我们使用孩子表示法,每个结点分为val域,left域,right域.然后我们提供一个构造方法,每次创建结点的时候我们都要把val的参数传进去. 然后我们正式进入二叉树的手动连接,我们如图手动构造二叉树,我们只要对着图操纵每个结点的right和left即可. 2.5.2 实现二叉树的三种遍历操作
前序遍历,我们按照: 根结点 - 左子树 - 右子树. 这种顺序来进行遍历,因此我们先要判断根结点是不是空的,然后我们再打印根结点,再递归左子树,然后递归右子树.如图,我们就展示了遍历A的左子树一部分的遍历流程. 中序遍历,我们按照: 左子树 - 根结点 - 右子树.这种顺序来进行遍历,首先我们还是要判断根结点是不是空的,然后我们先递归左子树,然后递归到最左边结点的时候,我们就打印我们的子树的根结点,然后我们再递归我们的右子树.如图简要分析了一下它的过程. 后序遍历,我们按照: 左子树 - 右子树 - 根结点.这种顺序来对二叉树进行遍历.我们先递归左子树,然后递归右子树,最后在进行打印,如图. 2.5.3 获取树中结点的个数
1 遍历的方式 : 只要遍历的结点不为空,我们就让全局变量
我们获取树中的结点数目,我们只要遍历整个树,然后经过一个结点就记录一下就可以; ,因此我们选择前序遍历.每次遍历一个结点,我们就让全局遍历 2 用子问题的思路来解决: 整棵树的结点数 左子树的结点数 右子树的结点数 根结点(1) 2.5.4 获取叶子结点的个数
1 遍历的方式: 按照某种方式来进行遍历,遍历到某个结点,判断是不是叶子,是就计数器 2 用子问题的思路来写: 整棵数的叶子 左子树的叶子 右子树的叶子
用子问题,我们就可以充分利用我们的返回值了 2.5.5 获取第k层结点的个数
子问题方法: 第k层节点数 左子树的k-1 层的节点数 右子树k-1层的结点数
我们从上到下标号,每次遍历到下一层,我们k就--,直到k 1的时候,我们就遍历到了给定的第k层,然后我们就返回1. 2.5.6 获取二叉树的高度
子问题解决: 整棵树的高度 max(左子树的高度,右子树的高度) 1 不定义结点数变量也可以,但是在刷题软件往往会超时,因为第一种写法只递归了一次,而下面这种写法在判断的时候递归了一次,在返回值的时候又递归了一次. 2.5.7 返回检测值为value的结点
我们直接前序遍历,先判断根结点是不是,然后判断左子树里面有没有val,再判断右子树有没有.我们如果没有找到,一定返回的是null,如果找到了,我们一定返回的是那个结点. 2.5.8 整体代码
package 二叉树;import java.util.ArrayList;
import java.util.List;//TODO 孩子表示法
//
public class BinaryTree {static class TreeNode {//每一棵树的结点public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val val;}}//手动连接二叉树public TreeNode createTree() {TreeNode A new TreeNode(A);TreeNode B new TreeNode(B);TreeNode C new TreeNode(C);TreeNode D new TreeNode(D);TreeNode E new TreeNode(E);TreeNode F new TreeNode(F);TreeNode G new TreeNode(G);TreeNode H new TreeNode(H);A.left B;B.left D;B.right E;E.right H;A.right C;C.left F;C.right G;return A;}//进行遍历操作// 前序遍历(根左右)//用递归 的方式来写 : 把大问题处理成小问题,处理方式是一样的void preOrder(TreeNode root) {//先判断根结点为不为空if (root null) {return;}//不为空就按照根左右的方式来打印;System.out.print(root.val );//遍历根结点的左子树preOrder(root.left);//遍历根结点的右子树preOrder(root.right);}// 中序遍历(左根右)void inOrder(TreeNode root) {if (root null) {return;}//从左子树开始遍历inOrder(root.left);//打印左子树的值System.out.print(root.val );inOrder(root.right);}// 后序遍历(左右根)void postOrder(TreeNode root) {if (root null) {return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val );}//把前序遍历的结构存储到List里面去ListInteger list1 new ArrayList();public ListInteger preorderTraversal(TreeNode root) {//先判断根结点为不为空if (root null) {return list1;}//不为空就按照根左右的方式来打印;list1.add((int) root.val);//遍历根结点的左子树preorderTraversal(root.left);//遍历根结点的右子树preorderTraversal(root.right);return list1;//如何合理利用返回值?}//我们进行优化public ListInteger preorderTraversal2(TreeNode root) {ListInteger list new ArrayList();//先判断根结点为不为空if (root null) {return list;}//不为空就按照根左右的方式来打印;list.add((int) root.val);//遍历根结点的左子树ListInteger leftTree preorderTraversal2(root.left);//把左边的树放进去list.addAll(leftTree);//遍历根结点的右子树ListInteger rightTree preorderTraversal2(root.right);//把右边的树放进去list.addAll(rightTree);return list;}public int nodeSize;//TODO 获取树中的个数//只要遍历的结点不为空,我们就//遍历思路来写int size(TreeNode root) {if(root null) {return 0;}nodeSize;size(root.left);size(root.right);return nodeSize;//利用返回值来进行优化}//用子问题的思路来解决:整棵树的结点个数 左子树结点个数 右子树结点个数int size2(TreeNode root) {if(root null) {return 0;}return size2(root.left) size2(root.right) 1;//左子树的结点数 右子树的结点数 根结点(1)}//TODO 获取叶子结点的个数//遍历思路来写// 按照某种方式来进行遍历,遍历到某个结点,判断是不是叶子,是就计数器int leafCount;int getLeafNodeCount(TreeNode root){if(root null) {return 0;}//如果每次遍历我们的结点左右都为空就让全局变量leftCount;if (root.left null root.right null) {leafCount;}getLeafNodeCount(root.left);getLeafNodeCount(root.right);return leafCount;}//用子问题的思路来写: 整棵数的叶子 左子树的叶子 右子树的叶子int getLeafNodeCount1(TreeNode root) {if(root null) {return 0;}//如果左右都为null那么就返回1if(root.right null root.left null) {return 1;}//计算左子树和右子树的return getLeafNodeCount1(root.left) getLeafNodeCount1(root.right);}//接下来我们都用子问题来解决//TODO 获取第k层结点的个数//第k层的结点数 左子树k-1层的节点数 右子树k-1层的节点数int getLeveNodeCount(TreeNode root, int k) {if(root null) {return 0;}if(k 1) {return 1;}//计算k-1层的左子树结点 计算k-1层的右子树结点return getLeveNodeCount(root.left,k - 1) getLeveNodeCount(root.right,k - 1);}//TODO 获取二叉树的高度 时间复杂度O(N)因为遍历了每一个结点//整棵树的高度 max(左子树的高度,右子树的高度) 1int getHight(TreeNode root) {if (root null){return 0;}//计算左树的高度int leftHight getHight(root.left);int rightHight getHight(root.right);//返回左树和右树的高度最高的1return leftHight rightHight ? leftHight 1 : rightHight 1;}int getHight2(TreeNode root) {if (root null){return 0;}//返回左树和右树的最大值1return getHight(root.left) getHight(root.right) ? getHight(root.left) 1 : getHight(root.right) 1;//这里递归太多次了没有第一种好,第一种只递归了一次}//TODO 检测值为value的元素是否存在//直接前序遍历,先判断根是不是,然后判断左子树是不是,最后判断右子树是不是TreeNode find(TreeNode root ,char val) {if(root null) {return null;}//判断根是不是if(root.val val) {return root;}//判断左子树TreeNode ret1 find(root.left,val);if(ret1 ! null) {//如果不为空就找到了return ret1;}//判断右子树是不是TreeNode ret2 find(root.right,val);if(ret2 ! null) {return ret2;}//左右都没找到return null;}}运行结果:
