二叉树1.树形概念想了解二叉树的概念我们得先知道数的概念树是⼀种⾮线性的数据结构它是由nn0个有限结点组成⼀个具有层次关系的集合。把它叫做树是因为它看起来像⼀棵倒挂的树也就是说它是根朝上⽽叶朝下的。它具有以下的特点•有⼀个特殊的结点称为根结点根结点没有前驱结点•除根结点外其余结点被分成M(M 0)个互不相交的集合T1、T2、…、Tm其中每⼀个集合Ti(1 i m) ⼜是⼀棵与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱可以有0个或多个后继•树是递归定义的注意树形结构中的子树是没有交集的、图中的两个子树之间有了练习那么我们就不能称这种结果为树。接下来了解一下树中的特殊名词结点的度⼀个结点含有⼦树的个数称为该结点的度 如上图A的度为6树的度⼀棵树中所有结点度的最⼤值称为树的度 如上图树的度为6叶⼦结点或终端结点度为0的结点称为叶结点 如上图B、C、H、I…等节点为叶结点双亲结点或⽗结点若⼀个结点含有⼦结点则这个结点称为其⼦结点的⽗结点 如上图A是B的⽗结点孩⼦结点或⼦结点⼀个结点含有的⼦树的根结点称为该结点的⼦结点 如上图B是A的孩⼦结点根结点⼀棵树中没有双亲结点的结点如上图A结点的层次从根开始定义起根为第1层根的⼦结点为第2层以此类推树的⾼度或深度树中结点的最⼤层次 如上图树的⾼度为4树的以下概念只需了解在看书时只要知道是什么意思即可⾮终端结点或分⽀结点度不为0的结点 如上图D、E、F、G…等节点为分⽀结点兄弟结点具有相同⽗结点的结点互称为兄弟结点 如上图B、C是兄弟结点堂兄弟结点双亲在同⼀层的结点互为堂兄弟如上图H、I互为兄弟结点结点的祖先从根到该结点所经分⽀上的所有结点如上图A是所有结点的祖先⼦孙以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙。如上图所有结点都是A的⼦孙森林由mm0棵互不相交的树组成的集合称为森林2.二叉树2.1二叉树的概念⼀棵⼆叉树是结点的⼀个有限集合该集合或者为空或者是由⼀个根节点加上两棵别称为左⼦树和右⼦树的⼆叉树组成。从上图可以看出⼆叉树不存在度⼤于2的结点⼆叉树的⼦树有左右之分次序不能颠倒因此⼆叉树是有序树2.2 两种特殊的⼆叉树1. 满⼆叉树:⼀棵⼆叉树如果每层的结点数都达到最⼤值则这棵⼆叉树就是满⼆叉树。也就是说如果⼀棵⼆叉树的层数为K且结点总数是 则它就是满⼆叉树。2. 完全⼆叉树:完全⼆叉树是效率很⾼的数据结构完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为K的有n个结点的⼆叉树当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从0⾄n-1的结点⼀ 对应时称之为完全⼆叉树。 要注意的是满⼆叉树是⼀种特殊的完全⼆叉树。2.3 ⼆叉树的性质若规定根结点的层数为1则⼀棵⾮空⼆叉树的第i层上最多有(i0)个结点若规定只有根结点的⼆叉树的深度为1则深度为K的⼆叉树的最⼤结点数是(k0)对任何⼀棵⼆叉树, 如果其叶结点个数为 n0, 度为2的⾮叶结点个数为 n2,则有n0n21具有n个结点的完全⼆叉树的深度k为上取整对于具有n个结点的完全⼆叉树如果按照从上⾄下从左⾄右的顺序对所有节点从0开始编号则对于序号为i的结点有◦ 若i0双亲序号(i-1)/2i0i为根结点编号⽆双亲结点◦ 若2i1n左孩⼦序号2i1否则⽆左孩⼦◦ 若2i2n右孩⼦序号2i2否则⽆右孩⼦2.4二叉树的代码表示⼆叉树的链式存储是通过⼀个⼀个的节点引⽤起来的。//无父亲表示法staticclassNode{intval;Nodeleft;Noderight;publicNode(intval){this.valval;}}//有父亲表示法staticclassNode{intval;Nodeleft;Noderight;Nodeparent;publicNode(intval){this.valval;}}2.5二叉树的基本操作1.创建一颗二叉树//这个节点指向二叉树的根节点privatestaticNoderoot;publicstaticNodecreateTree(){Nodenode1newNode(1);Nodenode2newNode(2);Nodenode3newNode(3);Nodenode4newNode(4);Nodenode5newNode(5);Nodenode6newNode(6);Nodenode7newNode(7);node1.leftnode2;node1.rightnode3;node2.leftnode4;node2.rightnode5;node3.leftnode6;node3.rightnode7;rootnode1;returnnode1;}创建后的二叉树长这样有了二叉树后我们该如何遍历呢最最最核心的思想是递归这时候我们通常有四种遍历方式1.前序遍历2.中序遍历3.后序遍历4.层序遍历1.首先看第一种前序遍历前序遍历的要点是先遍历当前节点再遍历左节点最后遍历右节点//前序遍历------顺序先遍历当前节点再遍历左节点最后遍历右节点publicvoidpreOrder(Noderoot){if(rootnull){return;}System.out.println(root.val);preOrder(root.left);preOrder(root.right);}递归的过程大概是这样的但是博主画的肯有点抽象将就看吧下面是代码运行的过程图画的 图像更加简陋博主一定好好学习画画因此我们得到的前序遍历结果为1, 245 , 36 , 7。2.接下来是中序遍历中序遍历的顺序是先遍历左节点根节点右节点这样的顺序进行的。publicvoidinOrder(Noderoot){if(rootnull){return;}inOrder(root.left);System.out.println(root.val);inOrder(root.right);}中序遍历的结果为 4 2 5 1 3 6 7 。具体的实现图像可以参考上面的标准大家自己画一个3.然后是后续遍历后续遍历的顺序是左子树 右子树跟节点publicvoidpostOrder(Noderoot){if(rootnull){return;}postOrder(root.left);postOrder(root.right);System.out.println(root.val);}后续遍历的结果是 4 5 2 6 7 3 1 。4.最后是层序遍历层序遍历的时候我们要实现从上到下从左到右的顺序实现这和我们的队列先进先出很符合为何说符合呢第一层放进去后再将第二层的孩子放进去第一层出第二层的孩子在分别把他们的孩子放进去这样的结构完全符合队列publicvoidfloorOrder(Noderoot){if(rootnull){return;}QueueNodequenenewLinkedList();quene.add(root);while(!quene.isEmpty()){Nodecurquene.poll();System.out.println(cur.val);//左子树入队if(cur.left!null){quene.offer(cur.left);}//右子树入队if(cur.right!null){quene.offer(cur.right);}}}层序遍历大概示意图如下二叉树的基本操作1.获取树中节点的个数2.获取叶⼦节点的个数3.⼦问题思路-huoqu求叶⼦结点个数4.获取第K层节点的个数5.获取⼆叉树的⾼度6.检测值为value的元素是否存在7.判断⼀棵树是不是完全⼆叉树首先回答问题一获取树中节点的个数这里我们使用递归的操作进行判断个数。publicstaticintsize(Noderoot){if(rootnull){return0;}if(root.leftnullroot.rightnull){return1;}return1size(root.left)size(root.right);}2.获取叶子节点个数这个问题与问题一类似publicstaticintgetLeafSize(Noderoot){if(rootnull){return0;}//递归的终止条件没有子树if(root.leftnullroot.rightnull){return1;}returngetLeafSize(root.right)getLeafSize(root.left);}3.⼦问题思路-huoqu求叶⼦结点个数这个问题与前两个思路i类似publicstaticintgetLeafSize(Noderoot){if(rootnull){return0;}//递归的终止条件没有子树if(root.leftnullroot.rightnull){return1;}returngetLeafSize(root.right)getLeafSize(root.left);}4.获取第K层节点的个数这里任然使用递归的事项来实现publicstaticintgetKsize(Noderoot,intk){if(k0){return0;}if(rootnull){return0;}//递归的终止条件当k1时返回1if(k1){return1;}intval1getKsize(root.left,k-1);intval2getKsize(root.right,k-1);returnval1val2;}5.获取⼆叉树的⾼度这个和 1 2 3题类似publicintheight(Noderoot){if(rootnull){return0;}if(root.leftnullroot.rightnull){return1;}return1Math.max(height(root.left),height(root.right));}6.检测值为value的元素是否存在publicstaticNodefind(Noderoot,intval){if(rootnull){returnnull;}if(root.valval){returnroot;}Nodenodefind(root.left,val);if(node!null){returnnode;}returnfind(root.right,val);}7.判断⼀棵树是不是完全⼆叉树这个问题是一个比较复杂的问题我们需要先考虑什么样的情况不是完全二叉树代码中用一个引子来指示前面是否存在过没有子树的情况这里我们可以定义一个boolean panpublicstaticbooleanisCompleteTree(Noderoot){if(rootnull){returntrue;}//将二叉树放进对列中应为上下顺序和左右顺序易分辨//接下来写层序遍历的过程QueueNodequeuenewLinkedList();queue.offer(root);//判断是否有空节点使用pan来标记是否有空节点booleanpanfalse;while(!queue.isEmpty()){Nodevalqueue.poll();//如果没遇见空节点if(!pan){//如果左子树为空右子树不为空直接falseif(val.leftnullval.right!null){returnfalse;}//如果左子树不为空则将左子树添加进队列中否则开启二阶段(将pan变成true)if(val.left!null){queue.offer(val.left);}else{pantrue;//这句的真实含义是将这个if语句终止掉应为上面的!pan此时为false直接进入下一个else}//同理子右子树不为空则将右子树添加进队列中否则开启二阶段(将pan变成true)if(val.right!null){queue.offer(val.right);}else{pantrue;}}else{//此时后面的元数都必须是叶子节点不允许有左.右子树if(val.left!null||val.right!null){returnfalse;}}}//循环结束后没有返回false说明没毛直接truereturntrue;}