前言❤️❤️hello hello这里是洋不写bug~欢迎大家点赞关注收藏这篇博客会进入到树结构的学习会解析什么是树结构什么是二叉树以及二叉树的几种遍历方式和规律的分析这部分内容不仅是面试的高频考点也是408的常考内容这篇博客会从最基础的东西开始解析包能看懂的这个专栏的数据结构是代码都是用Java来写的JavaSE专栏现在已经全部更新完成铁汁们复习基础知识时非常推荐使用可以试一下个人主页洋不写bug的博客所属专栏数据结构专栏复习Java基础知识Java学习之旅从入门到进阶铁汁们对于数据结构基础的各种核心知识不太常用的也有都可以在上面的数据结构专栏学习专栏正在持续更新中有问题可以写在评论区或者私信我哦~1树结构简介线性结构就是排成一条线任何一个元素都只有一个前驱和一个后继像链表、顺序表、栈、队列这些都属于线性结构树这样的结构就是非线性结构最下面是一个树根树根上有很多树枝每个树枝又会分叉一个节点的后继可能有多个节点像家谱就是一个经典的数据结构某个节点可以向下延伸出很多节点延伸出的节点这个节点的“子节点”这个节点就称为“父节点”如下图“爷爷奶奶”这个节点就有三个子节点爸爸妈妈、二叔二婶、三叔三婶“爷爷奶奶”就是这三个节点爸爸妈妈、二叔二婶、三叔三婶的父节点在树结构中一个父节点可以包含多个子节点但是一个子节点只能有一个父节点就是一个父亲能有多个儿子但一个儿子只能有一个父亲树结构中最上面的那个节点就是根节点上面家谱中曾祖父曾祖母这个节点就是根节点在日常生活中很多结构都是树结构例如计算机的存储计算机有三个节点C盘、D盘、E盘每个盘下对应着很多目录文件夹和文件再比如学校也是树结构接下来铁汁们判断下下图中的三个结构是不是树结构是不是树判断是不是子树有三个标准都满足才是树结构结构1中C和D都是A的子节点子树C和D相交了结构2中E有两个父节点D和B结构3中G有两个父节点A和D因此这三个结构都不是树结构只要第一个和第二个标准有一个不满足那第三个标准就一定不满足树结构还要很多概念接下来就以下图中的树结构为例来介绍下这些概念树结构的元素专业术语应该是结点而不是节点因此下面解析树结构都会用结点结点的度一个结点含有子树的个数称为结点的度子树可以理解为子结点子结点可以视为是另一棵树的根结点A的结点的度就是6树的度一棵树中所有结点度的最大值就是树的度中A结点的度为6是最大的所以树的度就是6叶子结点度为0的结点就是叶子结点B、C、H、I、P、Q、K、L、M、N都是叶子结点父结点双亲结点这个很好理解例如A是B的父结点J是P的父结点子结点孩子结点B是A的子结点P是J的子结点根结点一棵树中没有父结点的结点就是根结点A就是根结点结点的层次从根节点开始根节点所在的层为第一层下一层为第二层树的深度或高度结点的最大层次图中树的深度为4兄弟结点兄弟结点有相同的父结点B和C互为兄弟结点K和L和M也互为兄弟结点森林 m (m ≥ 0) 棵互不相交的树的集合没有树就是空森林树结构有三种表示方式分别是双亲表示法、孩子表示法、孩子双亲表示法双亲表示法就是拿到一个结点A可以通过A.parent找到这个结点的父结点几乎不会用到classNode{Stringval;Nodeparent;}孩子表示法就是拿到一个结点A就可以通过A.children找到A的所有子结点孩子表示法是日常使用最多的拿到根结点就能访问到树中的所有结点classNode{Stringval;ListNodechildren;}孩子双亲表示法拿到一个结点A既可以通过A.parent拿到A结点的父结点也可以通过A.children拿到A结点的子结点但这种方法空间利用率就比较低classNode{Stringval;ListNodechildren;Nodeparent;}孩子兄弟表示法拿到一个结点A可以通过A.firstChild拿到A的第一个子结点B接着可以通过B.brotherNodes拿到B的所有兄弟结点这个就更加小众了只有在特定场景下会用到了解下即可classNode{Stringval;NodefirstChild;ListNodebrotherNodes;}2二叉树简介二叉树树上任意结点的度都不超过2那这棵树就是二叉树像只有一个结点或者结点的度为1也都属于二叉树在数据结构中主要学习的树结构就是二叉树满二叉树整棵树没有只存在一个分支的情况如下图满二叉树第k层有2 ^ (k - 1)个结点假设一共有n层那满二叉树就有2 ^ n - 1个结点完全二叉树相当于在满二叉树的基础上缺失了右下角可以这样理解完全二叉树在每一层都是从左往右铺结点的铺完铺不完无所谓重要的是中间不能跳过下图就不是完全二叉树在第4层不是从左往右一个一个铺的跳过了一个结点二叉树的存储基本上使用的都是孩子表示法这样只要拿到根结点树中的所有结点就都能拿到了写代码时就是每个结点中创建两个引用left和right通过left和right拿到当前结点的左右子结点如果没有左子结点或没有右子结点那就把对应的left和right的值设置为nullpublicclassNode{privateStringval;privateNodeleft;privateNoderight;publicNode(Stringval){this.valval;this.leftnull;this.rightnull;}}创建一棵树也很简单先创建下结点再连接下结点即可例如按照下图来创建二叉树创建二叉树写在createTree方法中方法返回根结点因为拿到根结点就能访问到整个树publicclassTest{publicstaticNodecreateTree(){NodeanewNode(A);NodebnewNode(B);NodecnewNode(C);NodednewNode(D);NodeenewNode(E);NodefnewNode(F);NodegnewNode(G);a.leftb;a.rightc;b.leftd;b.righte;e.leftg;c.rightf;returna;}publicstaticvoidmain(String[]args){NoderootcreateTree();}}3二叉树的遍历拿到二叉树的根结点后如何来遍历整个二叉树呢 有三种方法先序遍历中序遍历后序遍历这三种方法都是基于递归来实现的因此会稍微有点抽象 除了一些特殊情况绝大部分二叉树这三种遍历的结点的打印顺序是不一样的1先序遍历先序遍历就是分为三步先访问当前结点的值打印递归的针对左子树进行先序遍历递归的针对右子树进行先序遍历publicstaticvoidpreOrder(Noderoot){if(rootnull){return;}System.out.println(root.val);preOrder(root.left);preOrder(root.right);}接下来就画图来模拟下前序遍历的递归打印这里博主把打印的按照顺序标了序号初学的铁汁这部分一定要细品一下就拿A来说遍历时一定是preOrder(A.left)全部走完才能轮到preOreder(A.right)那前序遍历打印的顺序就是ABDEGCF在main方法中运行一下确实是这个顺序publicstaticvoidmain(String[]args){NoderootcreateTree();preOrder(root);}2中序遍历中序遍历也是基于递归的方法只是把访问当前结点的值放在了中间位置中序遍历分为三步递归遍历左子树访问当前结点的值打印递归遍历右子树中序遍历的方法名叫做inOrderin就表示访问当前结点的操作在两个递归遍历操作之间publicstaticvoidinOrder(Noderoot){if(rootnull){return;}inOrder(root.left);System.out.printf(root.val );inOrder(root.right);}接下来就画图模拟下中序遍历二叉树的递归过程中序遍历因为打印逻辑在中间分析就会更抽象一些就拿A结点来说只有把inOrder(A.left)执行完才能轮到打印A结点初学的铁汁非常建议画图细品一下这里打印的顺序就是DBGEACF在main方法中运行下也确实是这个顺序publicstaticvoidmain(String[]args){NoderootcreateTree();inOrder(root);}3后序遍历后序遍历就是把打印当前结点的操作放到最后也是分为三步递归遍历左子树递归遍历右子树打印当前结点递归遍历的方法名就是postOrder因为post有在.....之后的意思publicstaticvoidpostOrder(Noderoot){if(rootnull){return;}postOrder(root.left);postOrder(root.right);System.out.printf(root.val );}同样画图来模拟下后序遍历的递归过程后序遍历中当前结点是最后打印的要打印结点A要等到postOrder(A.left)和postOrder(A.right)的逻辑都走完才能执行打印语句后序遍历的打印顺序就是DGEBFCA在main方法中运行下也确实是这个顺序publicstaticvoidmain(String[]args){NoderootcreateTree();postOrder(root);}4层序遍历层序遍历就是一层一层的打印下面这个树的层序遍历结果就是ABCDEFG先序、中序、后序遍历代码简单但是理解起来不太好理解层序遍历理解起来好理解但是代码写起来就比较复杂层序遍历代码的实现需要搭配队列分为以下几步创建一个存储元素类型为Node的队列先把根结点入队列循环的取出队首元素访问这个元素的值(打印)把这个元素的左子树和右子树都分别入队列再回到第二步继续循环如下图先把A入队列取出队首元素A进行访问也就是打印A将A的左结点和右结点入队列接着取出队首元素B进行打印将B的左结点和右结点入队列接下来取出队首元素C把C的左结点和右结点入队列这样一直循环就实现了层序遍历的效果层序遍历的方法命名为levelOrder代码如下所示publicstaticvoidlevelOrder(Noderoot){if(rootnull){return;}QueueNodequeuenewArrayDeque();queue.offer(root);while(!queue.isEmpty()){Nodecurqueue.poll();System.out.printf(cur.val );if(cur.left!null){queue.offer(cur.left);}if(cur.right!null){queue.offer(cur.right);}}}4规律分析接下来根据前面的打印结果分析下先序、中序、后序遍历的打印规律从根结点的角度来看先序遍历的第一个元素就是根结点后序遍历的最后一个元素就是根结点从子树的角度来看先序遍历中的子树部分下图中用方框圈出的就是子树的一个元素就是子树的根结点后序遍历中的子树部分的最后一个元素就是子树的根结点中序遍历根结点在中间根结点左侧的元素属于左子树根结点右侧的元素属于右子树从子树的角度来看子树的根结点在中间左侧元素属于是子树的左子树的中序遍历结果右侧元素是子树的右子树的中序遍历结果二叉树最核心的一个基本功就是给出一个不是很复杂的二叉树不需要写代码不需要画图直接在脑子里想分析出最后的打印结果这个对于初学的铁汁可能有点难度可以先多画几次图接着再尝试在脑子里模拟递归的过程还是拿这个二叉树分析一下前序遍历打印结果前序遍历就是先打印当前结点再递归遍历左子树再递归遍历右子这里博主就大概用文字的形式描述下分析的过程首先是打印结点A接着递归遍历A的左子树就遍历到了B打印结点B接着遍历B的左子树遍历到了D打印结点D因为D结点的左右子树都为空所以D结点这里就不再往下遍历了这时候递归遍历B的左子树的操作已经完成开始递归遍历B的右子树遍历到了结点E打印结点E递归遍历E的左子树遍历到了G打印GG结点这里也停止继续往下遍历E的左子树遍历完了开始遍历E的右子树右子树为空停止继续往下遍历E结点遍历完成E结点遍历完成后B结点的左右子树就也遍历完成进而说明A结点的左子树遍历完成A结点的左子树遍历完成后开始遍历右子树遍历到了C结点打印C再遍历C的左子树左子树为空停止继续往下遍历C的左子树遍历完成后开始遍历右子树遍历到F打印FF的左右子树都为空不再继续往下遍历至此C的左右子树遍历完成也就说明A的右子树遍历完后整个子树先序遍历也就完成了这里是一边分析一边写的第1步分析完后就直接把AB写下来分析到第二步打印结点D把D写下来写到AB后面以此类推分析完成就能得到结果中序遍历和后序遍历博主就不再用大量文字描述分析过程了初学的铁汁如果感觉这部分比较抽象可以自己多画几次递归图结合递归图分析下慢慢的就能直接在脑子里模拟出过程下面这四道题目铁汁们可以尝试做一下第一题题目中已经指出是完全二叉树也就是一层一层从左往右铺的铺的时候不能跳过又给出了层序遍历的结果那我们就可以先画出二叉树(如下图)再看图得到前序遍历后的结果就是ABDHECFG第二题很简单先序遍历结果的第一个元素就是根结点因此二叉树的根结点就是E第三个题目特别经典就是给出两种序列让我们还原二叉树接着推出另一种序列这种题目一般给出的序列长度都比较短这里给出中序遍历序列为badce后序遍历序列为bdeca根据这两个序列还原二叉树就要用到前面的规律了通过后序序列可以知道a为根结点再看中序序列a左边的元素b属于左子树a右边的元素(dce)属于右子树再把d、c、e三个元素单独拿出来看推断下这三个元素组成的子树的形状后序序列中这三个元素的顺序是dec也就说明c是这个子树根结点在中序序列中这三个元素的顺序是dcec在中间且c为根结点就说明d是c的左节点e是c的右结点这样就可以得到dce的形状结构做这类题目的解法就是把几个元素拿出来单独分析分析组成的树结构画出树后先序、中序、后序序列中至少要知道两种才能推断出树的结构得出前序遍历的结果就是abcde第4个题目后序遍历和中序遍历的结果都是ABCDEF解法跟第三题是类似的这种两个序列结果一样的反而特别简单可以推出F是树的根结点中序序列是ABCDEF就说明F右子树是空的ABCDE都在左子树上接着再看A、B、C、D、E这5个元素分析这5个元素构成的树结构会发现E是这个子树的根结点E还是没有右子树ABCD都在左子树上再分析A、B、C、D这四个元素以此类推铁汁们就会发现这个树结构就是一条线后面的就不用再一 一分析了层序遍历的结果就是FEDCBA结语二叉树的学习算是数据结构中的一个难点并不是二叉树本身的结构复杂而是二叉树的方法基本上都涉及递归就比如遍历方式顺序表、链表、栈、堆都是通过循环来遍历的二叉树这里变成了通过递归来遍历包括树结图脑子中想出二叉树的遍历序列这个初学时可能会感觉比较抽象最好的方法就是在画图板上多画几次递归过程图细品下递归过程这样分析递归的能力就一定会提升以上就是今天的所有内容啦完结撒花