二叉树(1)——-数据结构

一)递归的常见习题复习:

public class UserController {
    public static void run(int a){
        if(a==1){
            return;
        }
        System.out.println(a);
        run(a-1);
    }
    public static void main(String[] args) {
           run(10);
    }
}

1)每一次递的时候，这个函数只执行了一部分，就接着去执行另一个函数一部分了

2)归的时候，会把方法的剩余部分执行完毕

3)递的次数和归的次数是一样的

 public static int run(int n){
         if(n==1){
             return 1;
         }
         return n*run(n-1);
    }
    public static void main(String[] args) {
        System.out.println(run(3));
    }

1)在我们的方法进行调用的时候，就有一个栈，这样的内存空间就描述了当前的调用关系，称之为调用栈

2)每一次方法的调用都称之为是一次栈祯，这个栈争就包含了这一次调用的参数有哪些，返回到那里执行等信息，我们可以借助idea来进行观看；

练习1:按照顺序打印一个数字的每一位，比如说1234，最后打印1,2,3,4

1)一个数字的每一位怎么拿到？

123%10=3

123/10=12

2)1-9之间的数字直接进行打印即可

 public static void run(int n){
         if(n<10){
             System.out.println(n);
             return;
         }
       System.out.println(n%10);
         run(n/10);
    }

练习2:递归求出:1+2+3+4+5+6+…100

  public static int sum(int n){
        if(n==1){
            return 1;
        }
        return n+sum(n-1);
    }

练习三:计算一个数字的每一位之和:

  public static int sum(int n){
        if(n<10){
            return n;
        }
        int temp=n%10;
        return temp+sum(n/10);
    }
  

假设输入123，第一次是3+12的余数

树是一种非线性的数据结构，它是由N个有限节点组成的一个具有层次关系的集合，把他作为树是因为它看起来像是一颗倒挂着的树，也就是说他是根朝上，叶子朝下的

二)二叉树的概念以及性质:

1)根节点是没有前驱结点的

2)每一棵子树的根节点只有一个前驱，但是可以有0个或者多个后继

3)树型结构中，子树不能有交集，否则就不是树形结构

树的应用主要应用于文件管理系统，树形结构

4)除了根节点之外，其余结点被分成M个互不相交的集合T1，T2，T3，T4，Tm，其中每一个集合又是一颗于树类似的子树，每一棵树的子树的根节点有且只有一个前驱，可以有0个或者多个后继节点

5)除了根节点之外，每一个结点有且只有一个父亲节点

6)一颗N个节点的树有N-1条边

1)结点的度:一个节点所拥有子树的个数称为该结点的度；

2)树的度:一棵树中，最大结点的度称为树的度，一个节点如果没有子树，那么他的度就是0；(所有树的结点的度的最大值)，所有节点的度的最大值称之为该节点的度

3)叶子节点或终端节点:度为0的节点称之为叶子节点，即没有左孩子又没有右孩子；

4)结点的层次:根节点是第一层，在向下是第二层，以此类推

5)树的高度或者深度:

树的高度是整棵树的高度，而深度要针对某一个节点来说，最大的深度才等于树的高度

6)叶子节点就是终端结点

7)非终端结点:度不为0的结点

8)兄弟结点:相同父亲的节点

9)节点的层次:从根开始定义起，根为第一层，根的子节点是第二层，以此类推

10)双亲节点或者是父亲节点:如果一个节点具有子节点，那么这个节点称之为是其子节点的父亲节点

11)孩子节点或者是子节点:一个节点含有的子树的根节点称之为该节点的子节点

12)堂兄弟节点:双亲在在同一层上面的节点互为堂兄弟节点

13)节点的祖先:从根到该节点所经分支上面的所有节点，根节点是所有节点的祖先

14)森林:由m颗互不相交的树组成的集合叫做森林

1)一棵二叉树是结点的一个有限集合，该集合或者为空，或者有一个根节点加上两棵称为左子树和右子树的二叉树组成

2)子树是不相交的，二叉树不存在度大于2的节点

3)二叉树的每一个节点，要么有0个孩子，要么有两个孩子，要么有1个孩子

4)一棵树如果是二叉树，那么他的每一棵子树都必须是二叉树，二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树(先后顺序) ；

5)通常情况下:第一层有2^0个节点，第二层有2^1个节点，第三层有2^2个节点，那么第N层有2^(N-1)个节点，一共有2^N-1个节点(N表示有几层)

1)已知一颗完全二叉树的第三层(设根节点是第一层)有两个叶子节点，那么这颗完全二叉树的节点最多有_个

2)设F是T1，T2，T3三棵树组成的森林，与F相对应的二叉树是B，T1，T2，T3的节点数分别是n1，n2，n3，那么二叉树B对应的根节点左子树的个数是:

3)设森林F对应的二叉树是B，他由m个节点，B的根为p，p的右子树的结点个数是N，森林F的第一课数的节点的个数是

4)设顺序表的长度是N，那么顺序查找的成功的平均比较次数是

5)假设有100个元素，用折半查找法进行查找的时候，最大，最小比较次数是

二分查找因为每次都是从中间点开始查找，所以最坏情况是目标元素存在于最边缘的情况，log2(N)向上取整

三)常见的二叉树以及习题

一.满二叉树:

1)如果说这一棵树的每一层的节点数都达到了最大值，每一个节点任意一个节点都有左孩子和右孩子，左孩子和右孩子都是一棵二叉树如果说一颗二叉树的层数是K，况且他的节点总数是2^K-1，那么这棵树就是满二叉树；

2)为什么满二叉树的节点总数是2^K-1呢?

这个二叉树第一层一定是2^0个结点，第二层一定是有2^1个节点，那么第K层一定是有2^k-1个结点

那么这个时候的满二叉树的总结点是：等比数列求和结果为(2^k)-1，下面这一棵树就是满二叉树，比如说k==4，那么一共就是有15个节点

3)第k层的节点数是2^(k-1)个节点数

4)那么已知总结点数是N，那么2^k-1=N，那么满二叉树节点数是N的层数是log2(N+1)

二.完全二叉树:不存在一个节点只有右孩子而不存在左孩子，满二叉树也是一种完全二叉树

 满二叉树也是一种特殊的完全二叉树

三.对于任意一棵二叉树，如果它的总叶子节点(没有子树)个数是n0，度为2的非叶子节点的个数是n2，那么n0=n2+1，度为0的节点比度为2的节点多1；

推倒:假设二叉树有N个结点，有n0个叶子节点(也就是说有N0个度为2的结点)，n1个只有一个叉的节点，n2个有两个叉的结点

N=N0+N1+N2;

已知任意一个二叉树有N个结点，又因为一个二叉树，有N-1条边；

一个有N个节点的树，有N-1条边

度为0的结点，有N0个，能够产生多少条边？0条边

度为1的结点，有N1个，能产生多少条边？产生N1条边

度为2的结点，有N2个，能产生多少条边？产生2*N2条边

N-1=0+N1+2*N2

根据等式连立可得:对于所有的二叉树来说，度为0的叶子节点个数比度为2的节点节点个数多一个

四:如果我们规定根节点的层数是1，那么一颗非空完全二叉树的第i层最有多少节点？

第一层有2^0个节点，第二层有2^1个节点，第三层有2^2，第i层有2^i-1次方个节点

五:如规定只有根节点的二叉树的深度是1，那么深度是K的二叉树的最大节点数是(2^k)-1(等比数列求和)

2^0+2^1+2^2+2^3

六:对于任何一颗二叉树，如果他的叶子节点是N0，那么度为2的非叶子节点个数是N2，那么N0=N2+1

一:假设任何一棵二叉树有N个节点，又因为一棵二叉树，都是由N0个度为0的节点，有N1个度为1的结点，N2个度为2的结点构成的
N总(总结点数)=N0+N1+N2
二:对于任意一棵树来说
如果有N个节点,那么就会产生N-1条边
N0:度为0的结点，向下只能产生0条边，有N0个结点，向下就只能产生0条边
N1:度为1的结点，向下只能产生1条边，有N1个结点，向下就只能产生N1条边
N2:度为2的结点，向下只能产生两条边，有N2个结点，向下就可以产生2*N2条边
得到:

N-1=0+N1+2*N2

1)如果规定根节点的层数是1，那么一个非空二叉树的第i层上面最多有2^(i-1)个节点

2)具有N个节点的完全二叉树的深度为log2(N+1)向上取整

(分奇数个节点的二叉树和偶数个节点的二叉树)

3)如果规定只有根节点的二叉树的深度是1，那么高度为K二叉树的最大节点个数是2^k-1

4)那么假设总结点数是N，那么高度k=等于log2(N+1)向上取整

5)对于任意一颗二叉树来说，如果叶子节点的个数是N0，度为2的非叶子节点的个数是N2，那么N0=N2+1

例1：某二叉树一共有399个节点，其中有199个度为2的节点，那么该二叉树中的叶子结点个数为多少？

199+1=200个；

例2:具有2n个节点的完全二叉树中，叶子节点的个数是(N);

A N    B   N+1     C   N-1     D  N/2

第一种方法:当n=1，n=2，n=3带进去算一算叶子结点的个数，当我的根节点是两个结点的时候，发现叶子节点是1个

当我发现一共有四个结点的时候，叶子节点是两个

当我发现一共有六个结点的时候，叶子节点有三个

第二种方法:既然它是一棵完全二叉树，那么他既有可能有偶数个节点，也有可能有奇数个节点；

既然是一棵二叉树，那么假设度为0的节点有N0个，度为1的结点有N1个，度为2的节点有N2个

1)如果完全二叉树有偶数个节点，那么它还是一棵完全二叉树，那么它的度为1的节点存在况且只有一个；

1+N0+N2=2N

N0=N2+1

假设叶子结点是X个，2X=2N—>N=X

2)如果完全二叉树有奇数个节点，那么它还是一颗完全二叉树，那么它的度为1的节点有0个；

0+N0+N2=2N(上面说了)这个压根就不成立

当一颗完全二叉树有偶数个结点的时候，那么它是会存在度为1的结点，况且只存在一个

当一颗完全二叉树有奇数个结点的时候，那么它是不会存在度为1的节点，也就是说具有奇数结点的完全二叉树没有度为1的结点

4)有奇数个结点N的完全二叉树的叶子节点个数是(N+1)/2

5)有偶数个结点N的完全二叉树的叶子节点个数是N/2

例3:一个具有767个结点的完全二叉树，它的叶子节点个数是384；

2n-1=767

例4:一颗完全二叉树的节点数是531个，那么这颗树的高度为10

log2(531+1)=9.几几，向上取整变成10

例5:一颗完全二叉树的节点个数是10个，那么这颗完全二叉树的高度是

假设这颗完全二叉树的高度是K，那么我们就可以列出公式2^K-1=10，最后K=log2(10+1)，本质上K=3点几几，最后向上取整变成了4

对于具有N个结点的完全二叉树，如果按照从上到下从左到右的顺序对所有节点从0开始进行编号，那么对于序号为i的结点有:

1)如果i大于0，那么他的双亲结点就是(i-1)/2(向下取整)，i=0的节点是根节点，他是没有双亲结点的

2)如果说2i+1<n，那么左孩子序号是2*i+1，否则没有左孩子(2i+1>n)

3)如果说2*i+1<n，那么右孩子的序号就是2*i+2，否则没有右孩子(2*i+2>n)

四)二叉树的存储:

对于我们二叉树的存储来说，二叉树的存储结构分为顺序存储(堆)+链式存储(类似于链表式的存储)

1)顺序存储适用于二叉树的形态和大小不发生剧烈变化的情况，顺序存储可以使用一维数组进行实现，通过数组元素的下标作为索引，随机存取二叉树的节点。链式存储则是构造链表，每一个节点中都包含着其他节点的地址信息，只能通过迭代以此访问元素。

2)咱们二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉(孩子父亲表示法)和三叉(孩子双亲表示法)表示法:

孩子表示法:

class TreeNode{
     private char val;
     private TreeNode left;
     private TreeNode right;
//构造方法
     }

孩子双亲表示法:

class TreeNode{
    private char ch;
    private TreeNode left;
    private TreeNode right;
    private TreeNode parent;
    }

五)二叉树的遍历

遍历就是说沿着某一条搜索路线，依次对树中的每一个节点均作一次且做一次访问

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

                                         A
                   B                                         C
      D                      Null                     E                F
Null       Null        Null          Null      Null       Null   Null      Null

              

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.层序遍历:从所在二叉树的根节点进行出发,首先访问第一层的数根节点,再次从第二层左向右访问根节点,从上到下,从左到右;

六)三种遍历方式的代码(进行宏观理解)

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的右边……..

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

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

1)这里面要注意，这里面的返回值是List<Integer>，所以说当root为空的时候，直接返回list即可

  List<Integer> list=new ArrayList<>();
  list.addAll(null);
这样的代码会出现空指针异常,所以咱们的AddAll里面不可以为空

2)我们保证，二叉树的每一棵子树都对应着一个ArrayList

1)为什么不能共用同一个ArrayList?

2)为什么返回值不能是一个空？

1)已知某完全二叉树(同一层从左到右)层序遍历的序列是ABCDEFGH，那么该二叉树的前序序列为? ABDHECFG

2)已知二叉树的前序遍历是EFHIGJK,它的中序遍历是HFIEJKG,那么这个二叉树的根节点是

(已知)前序遍历和中序遍历,我们要知道根据一棵树的某一个遍历,是不能够完全确定一棵二叉树的

前序遍历是根左右，中序遍历是左右根，所以我们可以直接判断出E就是根节点，我们定义一个i下标，从前序遍历的结果开始向后走，例如说i走到了E，那么在中序遍历的结果找E，此时把中序遍历的结果分成两部分，E的左，E的右，此时就可以画出完整的二叉树;

他的后序遍历的结果是:H，I，F，K，J，G，E

3)已知二叉树的中序遍历结果是BADCE,后序遍历结果为BDECA,那么前序遍历的二叉树序列为abcde

先遍历后序遍历的序列，从最后一个元素位置出发，然后再拿这个元素找到该根，然后再从中序遍历的结果找到该根，根的左边是左子树，右边是右子树

接下来继续遍历后序遍历的序列，此时再次拿到的根就是这棵树的右子树；

1)从后序遍历的结果根是A,因为后序遍历的最后一个位置一定是根节点;

2)我们从中序遍历(左右根)的结果找A的位置,分成左右两个部分,然后中序遍历向回走找到C,C此时一定是A的右边(因为先打印右边再进行打印根位置),那么再往前走,e一定是c的右边;

4)如果某一个二叉树的后序遍历结果和中序遍历结果是相同的，都是ABCDEF，那么依次按层输出的(同一层从左到右的序列)是FEDCBA

1)此时如果说已知前序序列和后序序列是不可以创建出一棵完全二叉树的，因为现在拿到的都是一堆根，只是知道根是不能确定左子树和右子树的，一定要有中序遍历，这样子才能确定左右子树，否则搞不定

2)我们的中心思想是先找到每一个节点的根，再去中序遍历中找到左子树和右子树

今天的文章二叉树(1)——-数据结构分享到此就结束了，感谢您的阅读。