蓝桥杯|二叉树(1)-------数据结构蓝桥杯|职场和发展

1.递归复习函数自己调用自己的过程就叫做递归，每一次函数调用，都会在栈里面开辟一块空间；递归都是有跳出条件的，每一次递归自己调用自己的时候在无限地接近跳出条件
写一段C代码:

#include
Int main(){
printf("hh");
main();
return 0;
}
这个过程中程序就会一直循环打印hh,知道程序挂掉，在这个过程中会出现栈溢出
练习题1:接收到一个整型，按照它的顺序打印它的每一位;
void print(int n)
{
if(n>9)//1234
{print(n/10); //123
}
printf("%d",n%10);
}

void print(int n)
{
if(n>9)
{print(n/10); //12
}
printf("%d",n%10);
}

void print(int n)
{
if(n>9)
{print(n/10);
}
printf("%d",n%10); 此时传过来的是1
}
1)当我们首次调用print函数的时候，首先我们传入的是1234，先进入到if语句里面，发现1234>9，会再次调用print函数，不会执行到下面的printf打印函数，此时主要做的是执行if语句里面的print函数；
2)第二次调用print函数的时候，传过去的实参是123，在这个print函数里面，会再次遇到一个if语句，123>9会执行到if语句，在if语句里面又会调用一次print函数，而此时代码还是一样不会继续向下执行到打印语句，而是会执行我们第三次调用的print函数，传过去的实参是12
3)当我们第三次调用print函数的时候，还是会进入到if语句执行我们的第四次print函数，一样不会打印
4)打给我们第四次调用print函数的时候，发现if语句进不去，这是终于执行if语句下面的打印语句printf了; 此时我们的第四个print函数在第三个print函数里面的if语句调用完了，此时就会执行第三个print函数的打印语句循环往复。。。。

2.二叉树---子树是不相交的,0,1,2个孩子，不存在度大于2的节点

通常情况下:第一层有2^0个节点，第二层有2^1个节点，第三层有2^2个节点，那么第N层有2^(N-1)个节点,一共有2^N-1个节点
1)结点的度:一个节点所拥有子树的个数称为该结点的度；
2)树的度:一棵树中,最大结点的度称为树的度，一个节点如果没有子树，那么他的度就是0；
3)叶子节点或终端节点:度为0的节点称之为叶子节点，即没有做孩子又没有右孩子；
4)满二叉树:每一层的节点数都达到了最大值，每一个节点任意一个节点都有左孩子和右孩子；
5)完全二叉树:不存在一个节点只有右孩子而不存在左孩子,每一层都放满
6)对于任意一棵二叉树，如果它的叶子节点个数是n0,度为2的非叶子节点的个数是n2，那么n0=n2+1，度为0的节点比度为2的节点多1；
7)如果规定根节点的层数是1，那么一个非空二叉树的第i层上面最多有2^(i-1)个节点
8)具有N个节点的完全二叉树的深度为log2(N+1)取整
9)
例1：某二叉树一共有399个节点，其中有199个度为2的节点，那么该二叉树中的叶子结点个数为199+1=200个；
例2:具有2n个节点的完全二叉树中，叶子节点的个数是n;
第一种方法:当n=1,n=2,n=3带进去算一算叶子结点的个数
第二种方法:既然它是一棵二叉树，那么他既有可能有偶数个节点，也有可能有奇数个节点；
既然有偶数个节点；
如果有偶数个节点，那么它还是一棵完全二叉树，那么它的度为1的节点只有一个；
如果有奇数个节点，那么它还是一颗完全二叉树，那么它的度为1的节点只有0个；
例3:一个具有767个结点的完全二叉树，它的叶子节点个数是384；
2n-1=767
例4:一颗完全二叉树的节点数是531个，那么这颗树的高度为10

3.二叉树的遍历 1)前序遍历:先打印根节点,在打印它的左子树,最后打印它的右子树(如果说左子树下面有节点或者说右子树下面有节点,那么不能直接进行打印),因为它的左子树的子节点很有可能是下一棵树的根节点

A BC DNullEF NullNullNullNullNullNullNullNull

1)我们现在从根节点开始进行前序遍历,current指向的结点不是空,那么打印A结点的数值;
2)接下来我们打印A的左树,但是我们此时发现A的左树又一大陀节点,所以说我们先要把A的作书上面的所有节点(B,D)都打印完成,才可以打印A的右边
3)我们接下来再次从向左走,遇到根节点B,打印B,此时我们应该打印B的左树了,但是这时,B又发现B的左树又是一大堆,在向左边走(current=current.left)
4)走到D节点之后,先打印根节点,再次尝试打印D的左节点,发现左节点为空,不打印,尝试打印D的右节点,发现也为空;
5)此时我们就把B的左边打印成功了,现在我们想尝试打印B的右边,发现B的右边为空节点,不进行打印
6)此时我们就发现A的左子树已经打印完成了
7)现在我们尝试打印A的右边(右子树)
8)我们先走到C的位置,是根节点,进行打印C里面的数值; 再去尝试打印C的左边,发现C的左边有一大陀,现在我们继续向左走,走到E,发现E为根节点,进行打印,再走到E的左边,发现为空,不打印,走到E的右边,发现为空,不进行打印;
9)此时我们已经把C的左边打印完成了,尝试打印C的右边
10)走到F位置,打印F,走到F的左边,发现为空,不进行打印,右边为空,不进行打印;
A B D C E F

2)中序遍历:先打印左子树,在打印根节点,再进行打印右子树;

1)现在我们从根节点进行遍历,一开始current指向的节点是A,那么我们现在可以一开始就打印A吗?这是不行的,因为先要打印A的左树(一大坨节点),才可以进行打印A;
2)那么现在我们向A的左边走,走到B节点,此时我们可以打印B了吗?还是不可以,因为B虽然是A的左孩子节点,但是必须B是它下面的子树的根节点,所以说还是不可以进行打印
3)在向B的左边走,我们来到了D,此时还是不可以直接打印D的,而是先要打印D的左子树,发现为空,不会进行打印,此时D的左节点已经完成,先在打印根节点D,再去打印D的右边,发现为空,不进行打印;
4)此时B的左边的全部树节点已经打印完成,现在尝试打印根节点B,再去打印B的右子树,发现为空,不会进行打印
5)此时A的左边已经打印完成了,先把在打印根节点A,再去尝试打印A的右边,现在走到了C节点的位置,不能打印C,先走到C的左边,是E,E也是不能打印,先打印E的左边,为null,E的左边打印完成,打印E,再去打印E的右边,为空,不打印
6)此时C的左边已经打印完成,此时打印根节点C,再去尝试打印C的右边
7)现在走到F节点,但是此时还是不可以打印F节点,先尝试打印F的左边,为空,不进行打印,打印F,再去尝试打印F的右边,为空,不打印
打印结果为:DBAECF

3.后序遍历:先打印左子树,再进行打印右子树,在进行打印根节点;
DBEFCA
4.层序遍历:从所在二叉树的根节点进行出发,首先访问第一层的数根节点,再次从第二层左向右访问根节点,从上到下,从左到右;
4.三种遍历方式的代码(进行宏观理解) 1.前序遍历:先走完所有结点的左边,再进行打印对应的根节点,再去走所有右边的节点

public void preprint(Node root) { if (root == null) { return; } System.out.println(root.data); preprint(root.left); preprint(root.right)

文章图片

1) 我们现在使用一个栈来进行辅助理解,当我们进行遍历到A的时候,将A入栈(啥时候我们把A的左边和右边都打印完成了才可以进行出栈),我们先要打印A的data,再去打印他的左节点(11),左节点打印完成了,再去打印右节点(12)
2)左节点发现是B,我们打印B的data,将B入栈,现在我们再去尝试打印B的左节点(21),再去打印右节点(22)
3)B的左节点是D,我们进行打印D的data,将D入栈,再去尝试打印D的左边,为空,再去打印D的右边,也为空,此时我们将D出栈;
4)此时的栈顶元素是B,B已经打印完成了B的左边,再去执行22操作,发现B的右边为空,B这个节点已经完工了,此时就将B进行出栈
5)A的左边已完成,进行A的右边........

练习题1
写一个代码实现前序遍历

class Solution { List list=new ArrayList<>(); public List preorderTraversal(TreeNode root) { if(root==null) { return list; } list.add(root.val); preorderTraversal(root.left); preorderTraversal(root.right); return list; } }

public List preorderTraversal(TreeNode root) { List list=new ArrayList<>(); if(root==null) { return list; } list.add(root.val); List list1= preorderTraversal(root.left); List list2= preorderTraversal(root.right); list.addAll(list1); list.addAll(list2); return list; }

1)这里面要注意,这里面的返回值是List,所以说当root为空的时候,直接返回list即可
2)我们保证,在进行每一次递归的过程中,要保证List只有一份;

常见笔试题:
1)已知某完全二叉树(同一层从左到右)层序遍历的序列是ABCDEFGH,那么该二叉树的前序序列为? ABDHECFG
2)已知二叉树的前序遍历是EFHIGJK,它的中序遍历是HFIEJKG,那么这个二叉树的根节点是
(已知)前序遍历和中序遍历我们要知道根据一棵树的某一个遍历,是不能够完全确定一棵二叉树的
前序遍历是根左右,中序遍历是左右根,我们定义一个i下标,从前序遍历的结果开始向后走,例如说i走到了E,那么在中序遍历的结果找E,此时把中序遍历的结果分成两部分,E的左,E的右; 此时就可以画出完整的二叉树;
3)已知二叉树的中序遍历结果是BADCE,后序遍历结果为BDECA,那么前序遍历的二叉树序列为abcde
先遍历后序遍历的序列,从最后一个元素位置出发; 然后再拿这个元素找到该根,然后再从中序遍历的结果找到该根,根的左边是左子树,右边是右子树
接下来继续遍历后序遍历的序列,此时再次拿到的根就是这棵树的右子树;
1)从后序遍历的结果根是A,因为后序遍历的最后一个位置一定是根节点;
2)我们从中序遍历(左右根)的结果找A的位置,分成左右两个部分,然后中序遍历向回走找到C,C此时一定是A的右边(因为先打印右边再进行打印根位置),那么再往前走,e一定是c的右边;
【蓝桥杯|二叉树(1)-------数据结构】4)如果某一个二叉树的后序遍历结果和中序遍历结果是相同的,都是ABCDEF,那么依次按层输出的(同一层从左到右的序列)是FEDCBA
此时如果说已知前序序列和后序序列是不可以创建出一棵完全二叉树的