建设网站流程,seo课程培训班,钉钉爱客crm,网上接装修单在哪个平台#x1f387;#x1f387;#x1f387;作者#xff1a; 小鱼不会骑车 #x1f386;#x1f386;#x1f386;专栏#xff1a; 《数据结构》 #x1f393;#x1f393;#x1f393;个人简介#xff1a; 一名专科大一在读的小比特#xff0c;努力学习编程是我唯一… 作者 小鱼不会骑车 专栏 《数据结构》 个人简介 一名专科大一在读的小比特努力学习编程是我唯一的出路 二叉树1. 树的定义1.1 树的概念1.1.1 概念1.1.2 概念重要1.2 树的表示形式2. 二叉树2.1 二叉树定义2.2 二叉树的特点2.2.1 二叉树的特点2.2.2 二叉树的五种基本形态2.3 两种特殊的二叉树2.3.1 满二叉树2.3.2 完全二叉树2.4 二叉树的性质由公式推导附加几道练习题2.5 二叉树的存储2.6 二叉树的遍历2.6.1 前序遍历2.6.2 中序遍历2.6.3 后续遍历2.6.4 层序遍历2.6.5 前中后遍历的练习题2.7 二叉树的基本操作2.7.1 获取二叉树结点个数2.7.2 获取叶子节点个数2.7.2.1 遍历思路2.7.2.2 子问题思路2.7.3 获取第K层结点的个数2.7.3.1 遍历思路2.7.3.2 子问题思路2.7.4 获取二叉树的高度2.7.5 检测value的元素是否存在2.7.6 层序遍历2.7.7 判断一颗树是不是完全二叉树1. 树的定义
对于树在我们现实生活中是非常常见的大家可以看到一个树由一个根部和很多树杈组成就像这样 那我们便可以根据这颗树联想到一种数据结构就是树型结构把它叫做树是因为它看 起来像一棵倒挂的树也就是说它 是根朝上而叶朝下的。
关于树的结构有很多种但是我们现在主要学习的就是二叉树对于AVL树红黑树B树B树B*树……这些我们需要到高阶数据结构中才会了解到。
1.1 树的概念
1.1.1 概念
树Tree 树是nn 0个结点的有限集。n0 时称为空树. 在任意一颗非空树中有且仅有一个特定的称为根Root的结点并且根节点没有前驱结点. 当 n1 时其余节点可以分为m (m0)个互不相交的有限集T1,T2……Tn,其中每一个集合本身又是一棵树并且称为根的子树SubTree. 那我们再看看这是不是一颗树
这种不是树因为前面讲到过子树之间不能有交集切记 那我们在生活中都哪里用到了树形结构呢
举例
就像在文件夹中我单开一个之后出现一堆文件点开一个又是一堆文件其实这里涉及到的结构就是树形结构。 1.1.2 概念重要 这里我们结合上述图片讲解(观看顺序上文字下图) 结点的度一个结点含有子树的个数称为该结点的度 如上图A的度为3 树的度一棵树中所有结点度的最大值称为树的度 如上图树的度为3 叶子结点或终端结点度为0的结点称为叶结点 如上图J,F,K,L,I节点为叶结点 双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点 如上图A是B的父结点 孩子结点或子结点一个结点含有的子树的根结点称为该结点的子结点 如上图B是A的孩子结点 根结点一棵树中没有双亲结点的结点如上图A 结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推 树的高度或深度树中结点的最大层次 如上图树的高度为4 树的以下概念只需了解在看书时只要知道是什么意思即可
非终端结点或分支结点度不为0的结点 如上图D、E、H、G…等节点为分支结点兄弟结点具有相同父结点的结点互称为兄弟结点 如上图B、C是兄弟结点堂兄弟结点双亲在同一层的结点互为堂兄弟如上图G、H、I互为堂兄弟结点结点的祖先从根到该结点所经分支上的所有结点如上图A是所有结点的祖先子孙以某结点为根的子树中任一结点都称为该结点的子孙。如上图所有结点都是A的子孙森林由mm0棵互不相交的树组成的集合称为森林
另外强调两点重要的
n0 时根节点时唯一的不可能存在多个根节点别和现实中的大叔混在一起现实中的树有很多根须那是真正的树数据结构中的树只能有一个跟结点。m0 时子树的个数没有限制但是他们一定是互不相交的如上图1-2中的结构就不符合树的定义因为他的子树相交了.
1.2 树的表示形式
树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了实际中树有很多种表示方式如双亲表示法孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。
class Node {int value; // 树中存储的数据Node firstChild; // 第一个孩子引用Node nextBrother; // 下一个兄弟引用
}2. 二叉树
2.1 二叉树定义
我们做个小游戏
猜数字我用计算机随机一个数字数字范围为是1~100每猜一个数字我就会告诉你猜 “大了” 或者猜“小了”请大家想办法猜出这个数字有一个前提条件是猜数字的次数不能超过7次。
这个游戏对于没有接触过数据结构或者算法的人来说他们可能猜的方法是51015这样一点点的增加进行猜测这种效率其实是很差的。
其实正确的解法应该是折半查找算法如下图如果用的是该算法就一定能在七次内猜出结果下三层省略。 我们通过下面的代码生成0~100的随机数 public static void main(String[] args) {Random random new Random();Scanner scanner new Scanner(System.in);int p random.nextInt(100)1;//(0包含指定值不包含所以1如果是0就变成1如果是99就变成100)int size 0;while (scanner.hasNextLine()) {int z scanner.nextInt();if(z p) {System.out.println(猜大了第(size)次);}else if(z p){System.out.println(猜小了第(size)次);}else {System.out.println(第(size)猜对了);break;}}}下面开始测试 如果我们用这种方式进行查找效率会提高很多我们可以想想如果有100亿个数字需要找到指定值我们需要猜多少次一百亿是10个0我们按照2^10 1024 ,那么需要3个1024相乘再*10我们向上取整2 ^ 3 8,2 ^ 4 1616 10,我们取4可以得出100亿约等于2 ^ 34,那么按照每次查找一半只需呀log(2 ^ 34)次默认以2为底 34,多么恐怖啊100亿个数字中查找一个数只需呀34次
并且不止是折半查找对于这种某个阶段的结果都是两种形式的比如开和关0和1真和假上和下对与错正面与反面等都适合用树状结构来建模而这种树是一种很特殊的树状结构叫做二叉树。 二叉树Binary Tree是 n ( n0 )个结点的有限集和该集合或者为空集( 称为空二叉树 ),或者由一个根节点或两颗互不相交的分别称为根节点的左子树和右子树的二叉树组成。 上图1-1的A结点有三个子树所以不是二叉树。
2.2 二叉树的特点
2.2.1 二叉树的特点
每个结点最多有两棵子树所以二叉树中不存在度大于2的结点。注意不是必须有子树而是最多有。该节点没有子树或者只有一颗子树也都是可以的。左子树和右子树是有顺序的次序不能颠倒就像我们穿鞋如果左脚穿右鞋或者右脚穿左鞋那就会及其别扭和难受的。即使树中某个结点只有一棵子树也要区分它是左子树还是右子树下图中即使树1 和 树2 中存的值是一样的但是由于结构不一样所以他们不能称为完全相同的二叉树就像你在班级里你有一个同桌那么你的同桌坐在你的左边和坐在你的右边是两种完全不一样的位序。即使人没有变但是所处的位置是有区别的。 2.2.2 二叉树的五种基本形态 空二叉树。 只有一个根节点。 根节点只有左树。 根节点只有右树。 根节点既有左树又有右树。 其实这五种形态的二叉树大家还是很容易理解的那么我们深入探讨一下假如有三个结点的二叉树会有几种组合方式
我们看下图如果只是按照形态划分的话那么只有三种形态分别图1图2图5如果是按照结构划分的话那就是五种如下图图 1 到 图 5 分别代表着不同的二叉树。 2.3 两种特殊的二叉树
2.3.1 满二叉树 满二叉树特点:
在一个二叉树种如果所有分支节点都存在左子树和右子树并且所有叶子都在同一层上这样的二叉树称为满二叉树。一棵二叉树如果每层的结点数都达到最大值则这棵二叉树就是满二叉树。也就是说如果一棵二叉树的层数为K且结点总数是2^k-1 则它就是满二叉树。
2.3.2 完全二叉树
完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。 2.4 二叉树的性质由公式推导附加几道练习题
1.若规定根结点的层数为1则一棵非空二叉树的第i层上最多有2 ^ (i-1) (i0) 个结点.
论证 2.若规定只有根结点的二叉树的深度为1则深度为K的二叉树的最大结点数是 2 ^ k - 1 (k0)
论证
3.重点对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0n21
论证 求这个结论时,我们先了解一个知识点就是一个N个节点的树有N-1条边有了这个知识点之后我们再进行计算 4.具有n个结点的完全二叉树的深度k为 log(n 1)向上取整(默认以2为底这里忽略不写)
论证 5.对于具有n个结点的完全二叉树如果按照从上至下从左至右的顺序对所有节点从0开始编号则对于序号为i 的结点有
若i0双亲序号(i-1)/2i0i为根结点编号无双亲结点若2i1n左孩子序号2i1否则无左孩子若2i2n右孩子序号2i2否则无右孩子
举例 1.某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为 A 不存在这样的二叉树 B 200 C 198 D 199 2.在具有 2n 个结点的完全二叉树中叶子结点个数为 A n B n1 C n-1 D n/2 3.一个具有767个节点的完全二叉树其叶子节点个数为 A 383 B 384 C 385 D 386 4.一棵完全二叉树的节点数为531个那么这棵树的高度为 A 11 B 10 C 8 D 12 答案 1.B 解析度为0的结点比度为2的结点多一个题意说了度为2的结点有199则度为0的结点为1991200 2.A 解析在有2N个结点的完全二叉树由于是完全二叉树中那么只可能存在一个1个度为1的结点下面就是判断度为1的结点是否存在 我们设总共有N个结点假设度为1的结点为0 N n0n1n2 N n00n2 (注n2n0-1) N 2n0-1奇数 所以度为1的结点为0不符合条件 接下来假设度为1的结点有1个 N n0n1n2 N n01n2 N 2n0-11 N 2n0(偶数符合条件) 接下来把N替换成题意中的2N, 2N 2n0 N n0 最后选A 3.B 该题解法和上述一样判断是否存在度为1的结点 由于该树是完全二叉树并且该树的结点为767是奇数所以可以推出度为1的结点不存在 所以根据公式 N n0n1n2 767 n00n2 767 2n0-1 768 2n0 384 n0 4.B 解析有结点数求高度直接套公式 log(5311)向上取整 10 选择B 2.5 二叉树的存储
二叉树的存储结构分为顺序存储和类似于链表的链式存储。
二叉树的链式存储是通过一个一个的节点引用起来的常见的表示方式有二叉和三叉表示方式具体如下
// 孩子表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用常常代表右孩子为根的整棵右子树
Node parent; // 当前节点的根节点
}我们重点讲解孩子表示法结构如图 2.6 二叉树的遍历
为了后续方便讲解我们先创建一个二叉树。
public class BinaryTreeE extends ComparableE {static class Node E{NodeE left;NodeE right;E val;public Node(E val) {this.val val;}}public NodeE root//每个二叉树都需要一个根节点;
}public static void main(String[] args) {BinaryTreeCharacter b new BinaryTree();BinaryTree.NodeCharacter A new BinaryTree.Node(A);BinaryTree.NodeCharacter B new BinaryTree.Node(B);BinaryTree.NodeCharacter C new BinaryTree.Node(C);BinaryTree.NodeCharacter D new BinaryTree.Node(D);BinaryTree.NodeCharacter E new BinaryTree.Node(E);BinaryTree.NodeCharacter F new BinaryTree.Node(F);BinaryTree.NodeCharacter G new BinaryTree.Node(G);BinaryTree.NodeCharacter H new BinaryTree.Node(H);b.root A;A.left B;A.right C;B.left D;B.right E;C.left F;C.right G;}学习二叉树结构最简单的方式就是遍历。所谓遍历(Traversal)是指沿着某条搜索路线依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如打印节点内容、节点内容加1)。 遍历是二叉树上最重要的操作之一是二叉树上进行其它运算之基础。
2.6.1 前序遍历
所谓前序遍历就是根节点-》左子树-》右子树 规则是若二叉树为空则直接返回否则先访问根节点然后遍历左子树再前序遍历右子树。如下图 我们通过代码实现以下并且看一下结果 // 前序遍历void preOrder(Node E root){if(rootnull) {return;}System.out.print(root.val );preOrder(root.left);preOrder(root.right);}运行结果 2.6.2 中序遍历
中序遍历 左树-》根-》右树 规则把左树遍历完了之后再去打印根节点之后再遍历右树遇到空就返回否则一直递归下去。
下面就不画动图了偷个懒哈我们根据递归的代码带大家一步一步分析因为需要全部放在同一个图片内辛苦大家放大观看 运行结果 代码如下 // 中序遍历void inOrder(NodeEroot){if(rootnull) {return;}inOrder(root.left);System.out.print(root.val );inOrder(root.right);}2.6.3 后续遍历
后续遍历左树-》右树-》根
遍历规则先遍历左树左树为空遍历右树左右为空就打印
如果我们对上述的递归代码熟悉之后那么我们便可以自己写出后序遍历的递归代码就是调整一下打印的位置。 // 后序遍历void postOrder(Node E root){if(rootnull) {return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val );}2.6.4 层序遍历
关于层序遍历我们先知道打印的顺序就好后续会讲解 先将代码放入这里大家可以看看
//层序遍历void levelOrder(NodeE root){//利用队列QueueNodeE queuenew LinkedList();queue.offer(root);while (!queue.isEmpty()) {NodeE curqueue.poll();System.out.print(cur.val);if(cur.left!null)queue.offer(cur.left);if(cur.right!null)queue.offer(cur.right);}System.out.println();}2.6.5 前中后遍历的练习题 1.某完全二叉树按层次输出同一层从左到右的序列为 ABCDEFGH 。该完全二叉树的前序序列为() A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA 2.二叉树的先序遍历和中序遍历如下先序遍历EFHIGJK;中序遍历HFIEJKG.则二叉树根结点为() A: E B: F C: G D: H 3.设一课二叉树的中序遍历序列badce后序遍历序列bdeca则二叉树前序遍历序列为() A: adbce B: decab C: debac D: abcde 4.某二叉树的后序遍历序列与中序遍历序列相同均为 ABCDEF 则按层次输出(同一层从左到右)的序列为() A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEF 【参考答案】 1.A 2.A 3.D 4.A
1 1 1
2.7 二叉树的基本操作
2.7.1 获取二叉树结点个数
关于求二叉树的结点个数我们有两种解法
子问题思路 子问题思路就是将这个树分为根节点和左子树的结点数右子树的结点数其中每颗左子树或者右子树又是一个独立的二叉树再次进行根节点左子树结点右子树结点。这里采用从左往右的遍历思路都可以这里就不画图了大家可以自己画图思索一下对于数据结构多画多想多写代码是学好数据结构最好的利刃 //获取树中结点的个数public int size(NodeE root) {if(root null) {return 0;}return 1size(root.left)size(root.right);}遍历思路 遍历思路就是每遍历一个结点就size,我们采取前序遍历方法中序后序都可以因为每个结点只遍历了一次遇见根节点就 // 获取树中节点的个数private int size;// 获取树中节点的个数public void sizePlus(NodeE root) {if(rootnull) {return ;}size;sizePlus(root.left);sizePlus(root.right);}2.7.2 获取叶子节点个数
2.7.2.1 遍历思路
所谓叶子节点就是度为0的结点就说明叶子节点是没有左子树和右子树的那么我们的代码就可以把判断条件改为只要是该节点的左树和右树为空那就count,代码入下: // 获取叶子节点的个数,遍历思路//遍历思路求得叶子个数然后再去调用leaf就可以得到叶子的个数//叶子个数int count 0;public int getLeafNodeCountPlus(NodeE root){funcGetLeafNodeCountPlus(root);return count;}public void funcGetLeafNodeCountPlus(NodeE root) {if(rootnull) {return ;}//左子树右子树为空就if(root.leftnullroot.rightnull) {count;}funcGetLeafNodeCountPlus(root.left);funcGetLeafNodeCountPlus(root.right);}2.7.2.2 子问题思路
子问题思路就是左子树的叶子结点右树的叶子结点每个左子树或者右子树又是一个新的二叉树. // 子问题思路-求叶子结点个数public int funcGetLeafNodeCountPlus(NodeE root) {if(root null) {return 0;}//左右树为空就返回1if(root.left null root.right null) {return 1;}return funcGetLeafNodeCountPlus(root.left)funcGetLeafNodeCountPlus(root.right);}2.7.3 获取第K层结点的个数
所谓获取第K层的结点个数那么我们可以定义一个记录高度的变量当我的高度和k相同并且该节点不为空那就说明这个结点是第k层的结点。
2.7.3.1 遍历思路
如果是第k层结点就count /*** 左树的第n层和右树的第n层* 遍历* param root k* return int*/public int count;int getKLevelNodeCount(NodeE root,int k){funcGetKLevelNodeCount(root,k);return count;}public void funcGetKLevelNodeCount (NodeE root,int k) {if(k1root!null) {count;return;}if(rootnull) {return;}getKLevelNodeCount(root.left,k-1);getKLevelNodeCount(root.right,k-1);}2.7.3.2 子问题思路
左子树的第k层结点右子树的第k层结点。 /*** 子问题解决求树的第n层的结点* param root k* return int*/int getKLevelNodeCountPlus(NodeE root,int k){if(rootnull) {return 0;}if(k1) {return 1;}//左树第k层结点右树第k层结点return getKLevelNodeCountPlus(root.left,k-1) getKLevelNodeCountPlus(root.right,k-1);}2.7.4 获取二叉树的高度
获取二叉树的高度这道题上述讲到了树的高度或深度树中结点的最大层次因为要找到树的最大层次所以第一件事就是找到叶子结点然后开始返回但是并不是所有的叶子节点都在最后一层如图1所以我们可以思考一下可不可以将获取树的高度这个问题分解一下改成获取左子树的高度和右子树的高度然后对比哪个高就返回哪个并且加上根节点因为根节点本身也占一层。那调用左子树的高度时又变成了获取该树的左子树和右子树深度的最大值再加上当前的根节点。那么我们可以根据这个思路去写代码 // 获取二叉树的高度/*** 比较左树和右树的高度* param root* return*/public int getHeight(NodeE root){if(rootnull) {return 0;}int agetHeight(root.left);int bgetHeight(root.right);//左树高度和右树高度求最大值再1return Math.max(a1, b1);}2.7.5 检测value的元素是否存在
采用遍历思路当根节点的值为 val 时就返回 true ,如果根节点为空说明没有找到就返回 false ,如果根节点不为null并且还没有找到val那么继续去左树和右树中查找如果找到了就返回true,最后的返回值是左子树| | 右子树只要有一个为真就返回真 // 检测值为value的元素是否存在public boolean find(NodeE root, E val){if(rootnull) {return false;}if(root.valval) {return true;}//遍历当前结点和左子树和右子树boolean a1 find(root.left,val);boolean a2 find(root.right,val);return a1||a2;}2.7.6 层序遍历
层序遍历上述也介绍到了就是从左到右从上到下遍历遍历完这一层所有的结点再去遍历下一层的结点。
对于层序遍历我们需要借助一个工具就是队列我们来看图 代码如下 //层序遍历void levelOrder(NodeE root){//利用队列QueueNodeE queuenew LinkedList();queue.offer(root);while (!queue.isEmpty()) {NodeE curqueue.poll();System.out.print(cur.val);if(cur.left!null)queue.offer(cur.left);if(cur.right!null)queue.offer(cur.right);}System.out.println();}2.7.7 判断一颗树是不是完全二叉树
关于完全二叉树的介绍上述有讲到判断完全二叉树也是需要一个工具依旧是队列上述的队列实现了层序遍历那么我们可以在这个层序遍历的基础上给升级一下我们通过完全二叉树和非完全二叉树来对比一下
完全二叉树 非完全二叉树 根据对比我们发现完全二叉树的队列当出第一个空结点后其余结点都是空结点但是非完全二叉树的队列在弹出第一个空结点后其余结点一定有非空结点。 代码入下
// 判断一棵树是不是完全二叉树boolean isCompleteTree(NodeE root){//队列实现DequeNodeE queuenew LinkedList();queue.offer(root);//为空退出循环while (queue.peek()!null){NodeE curqueue.poll();queue.offer(cur.left);queue.offer(cur.right);}//判断剩余结点是否包含非空节点for (int i 0; i queue.size(); i) {if(queue.poll()!null) {return false;}}return true;}
