二叉树的学习

二叉树

1.树形概念

想了解二叉树的概念我们得先知道数的概念
树是⼀种⾮线性的数据结构，它是由n（n>=0）个有限结点组成⼀个具有层次关系的集合。把它叫做树是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。它具有以下的特点：
•有⼀个特殊的结点，称为根结点，根结点没有前驱结点
•除根结点外，其余结点被分成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的⼦孙
森林：由m（m>=0）棵互不相交的树组成的集合称为森林

2.二叉树

2.1二叉树的概念

⼀棵⼆叉树是结点的⼀个有限集合，该集合：

1. 或者为空
2. 或者是由⼀个根节点加上两棵别称为左⼦树和右⼦树的⼆叉树组成。
   
   从上图可以看出：
3. ⼆叉树不存在度⼤于2的结点
4. ⼆叉树的⼦树有左右之分，次序不能颠倒，因此⼆叉树是有序树

2.2 两种特殊的⼆叉树

1. 满⼆叉树:⼀棵⼆叉树，如果每层的结点数都达到最⼤值，则这棵⼆叉树就是满⼆叉树。也就是说，如果⼀棵⼆叉树的层数为K，且结点总数是 ，则它就是满⼆叉树。
2. 完全⼆叉树:完全⼆叉树是效率很⾼的数据结构，完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为K的，有n个结点的⼆叉树，当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从0⾄n-1的结点⼀ 对应时称之为完全⼆叉树。 要注意的是满⼆叉树是⼀种特殊的完全⼆叉树。

2.3 ⼆叉树的性质

1. 若规定根结点的层数为1，则⼀棵⾮空⼆叉树的第i层上最多有(i>0)个结点
2. 若规定只有根结点的⼆叉树的深度为1，则深度为K的⼆叉树的最⼤结点数是(k>=0)
3. 对任何⼀棵⼆叉树, 如果其叶结点个数为 n0, 度为2的⾮叶结点个数为 n2,则有n0＝n2＋1
4. 具有n个结点的完全⼆叉树的深度k为上取整
5. 对于具有n个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的顺序对所有节点从0开始编号，则对
   于序号为i的结点有：
   ◦ 若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，⽆双亲结点
   ◦ 若2i+1<n，左孩⼦序号：2i+1，否则⽆左孩⼦
   ◦ 若2i+2<n，右孩⼦序号：2i+2，否则⽆右孩⼦

2.4二叉树的代码表示

⼆叉树的链式存储是通过⼀个⼀个的节点引⽤起来的。

//无父亲表示法staticclassNode{intval;Nodeleft;Noderight;publicNode(intval){this.val=val;}}//有父亲表示法staticclassNode{intval;Nodeleft;Noderight;Nodeparent;publicNode(intval){this.val=val;}}

2.5二叉树的基本操作

1.创建一颗二叉树

//这个节点指向二叉树的根节点privatestaticNoderoot;publicstaticNodecreateTree(){Nodenode1=newNode(1);Nodenode2=newNode(2);Nodenode3=newNode(3);Nodenode4=newNode(4);Nodenode5=newNode(5);Nodenode6=newNode(6);Nodenode7=newNode(7);node1.left=node2;node1.right=node3;node2.left=node4;node2.right=node5;node3.left=node6;node3.right=node7;root=node1;returnnode1;}

创建后的二叉树长这样

有了二叉树后我们该如何遍历呢，最最最核心的思想是递归，这时候我们通常有四种遍历方式；1.前序遍历，2.中序遍历，3.后序遍历，4.层序遍历

1.首先看第一种；前序遍历前序遍历的要点是先遍历当前节点，再遍历左节点，最后遍历右节点

//前序遍历------>顺序，先遍历当前节点，再遍历左节点，最后遍历右节点publicvoidpreOrder(Noderoot){if(root==null){return;}System.out.println(root.val);preOrder(root.left);preOrder(root.right);}

递归的过程大概是这样的，但是博主画的肯有点抽象（将就看吧），下面是代码运行的过程图（画的 图像更加简陋（博主一定好好学习画画👊））

因此我们得到的前序遍历结果为1, 2，4，5 , 3，6 , 7。

2.接下来是中序遍历中序遍历的顺序是先遍历左节点，根节点，右节点这样的顺序进行的。

publicvoidinOrder(Noderoot){if(root==null){return;}inOrder(root.left);System.out.println(root.val);inOrder(root.right);}

中序遍历的结果为 4 2 5 1 3 6 7 。具体的实现图像可以参考上面的标准大家自己画一个

3.然后是后续遍历后续遍历的顺序是左子树 ，右子树，跟节点

publicvoidpostOrder(Noderoot){if(root==null){return;}postOrder(root.left);postOrder(root.right);System.out.println(root.val);}

后续遍历的结果是 4 5 2 6 7 3 1 。

4.最后是层序遍历，层序遍历的时候我们要实现从上到下，从左到右的顺序实现，这和我们的队列（先进先出）很符合，为何说符合呢，第一层放进去后再将第二层的孩子放进去（第一层出），第二层的孩子在分别把他们的孩子放进去，这样的结构完全符合队列

publicvoidfloorOrder(Noderoot){if(root==null){return;}Queue<Node>quene=newLinkedList<>();quene.add(root);while(!quene.isEmpty()){Nodecur=quene.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(root==null){return0;}if(root.left==null&&root.right==null){return1;}return1+size(root.left)+size(root.right);}

2.获取叶子节点个数这个问题与问题一类似

publicstaticintgetLeafSize(Noderoot){if(root==null){return0;}//递归的终止条件，没有子树if(root.left==null&&root.right==null){return1;}returngetLeafSize(root.right)+getLeafSize(root.left);}

3.⼦问题思路-huoqu求叶⼦结点个数这个问题与前两个思路i类似

publicstaticintgetLeafSize(Noderoot){if(root==null){return0;}//递归的终止条件，没有子树if(root.left==null&&root.right==null){return1;}returngetLeafSize(root.right)+getLeafSize(root.left);}

4.获取第K层节点的个数这里任然使用递归的事项来实现

publicstaticintgetKsize(Noderoot,intk){if(k<=0){return0;}if(root==null){return0;}//递归的终止条件当k==1时返回1if(k==1){return1;}intval1=getKsize(root.left,k-1);intval2=getKsize(root.right,k-1);returnval1+val2;}

5.获取⼆叉树的⾼度这个和 1 2 3题类似

publicintheight(Noderoot){if(root==null){return0;}if(root.left==null&&root.right==null){return1;}return1+Math.max(height(root.left),height(root.right));}

6.检测值为value的元素是否存在

publicstaticNodefind(Noderoot,intval){if(root==null){returnnull;}if(root.val==val){returnroot;}Nodenode=find(root.left,val);if(node!=null){returnnode;}returnfind(root.right,val);}

7.判断⼀棵树是不是完全⼆叉树这个问题是一个比较复杂的问题，我们需要先考虑什么样的情况不是完全二叉树
代码中用一个引子来指示前面是否存在过没有子树的情况这里我们可以定义一个boolean pan；

publicstaticbooleanisCompleteTree(Noderoot){if(root==null){returntrue;}//将二叉树放进对列中，应为上下顺序和左右顺序易分辨//接下来写层序遍历的过程Queue<Node>queue=newLinkedList<>();queue.offer(root);//判断是否有空节点，使用pan来标记是否有空节点booleanpan=false;while(!queue.isEmpty()){Nodeval=queue.poll();//如果没遇见空节点if(!pan){//如果左子树为空右子树不为空，直接falseif(val.left==null&&val.right!=null){returnfalse;}//如果左子树不为空，则将左子树添加进队列中，否则开启二阶段(将pan变成true)if(val.left!=null){queue.offer(val.left);}else{pan=true;//这句的真实含义是将这个if语句终止掉，应为上面的!pan此时为false，直接进入下一个else}//同理子右子树不为空，则将右子树添加进队列中，否则开启二阶段(将pan变成true)if(val.right!=null){queue.offer(val.right);}else{pan=true;}}else{//此时后面的元数都必须是叶子节点，不允许有左.右子树if(val.left!=null||val.right!=null){returnfalse;}}}//循环结束后没有返回false说明没毛，直接truereturntrue;}