二叉树的基本概念及运用

二叉树的概念：一棵二叉树是结点的一个有限集合，该集合：

1.或者为空

2.或者是由一个根节点加上两棵别称为为左子树和右子树的二叉树组成。

2.2：两种特殊的二叉树：

1.满二叉树：一课二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。

2.完全二叉树：除了最底层，其他层的结点必须是满的，即每层的结点数都达到最大值。同时，最后一层的结点必须从左到右连续排列，可能没有填满，但不能有空缺。

2.3. 二叉树的一些基本性质：

1.若规定根结点的层数为1,则规定非空二叉树的第i层有 2^i-1 个结点.

2.若规定只有根结点的二叉树深度为1，则深度为k的二叉树的最大结点为2^k-1.

3.对于任意一棵二叉树，如果其叶结点的个数为n0,度为2的非叶结点个数为n2,则n0 = n2 + 1;

4.具有n个结点的完全二叉树的深度k为log2(n+1) 取整。

2.4：二叉树的存储：

二叉树的存储结构分为：顺序存储和类似于链表的链式存储。

我们主要介绍链式存储：

二叉树的链式存储主要是通过一个一个的结点引用起来的，具体表示如下：

//孩子表示法：
    class Node {
        int val; //数据域
        Node left; //左孩子的引用,代表左孩子为根的整棵左子树
        Node right; //右孩子的引用,代表右孩子为根的整棵右子树
    }

    //孩子双亲表示法
    class Node {
        int val; //数据域
        Node left; //
        Node right;
        Node parent; //当前结点的根节点
    }

2.5：二叉树的基本创作：

2.5.1：二叉树的简单速成创建（非正式）：

//二叉树的速成简单创建
      public class BinaryTree {
        public static class BTNode {
            BTNode left;   //左孩子引用
            BTNode right;   //右孩子引用
            int value;    //值得大小

            public BTNode(int value) { //构造方法
                this.value = value;  //值得赋值
            }
        }

        private BTNode root; //根节点

        public void creatBinaryTree() {
            BTNode node1 = new BTNode(1);
            BTNode node2 = new BTNode(2);
            BTNode node3 = new BTNode(3);
            BTNode node4 = new BTNode(4);

            root = node1;//根节点的赋值
            node1.left = node2; //将node2赋值给node1的左节点
            node2.left = node3; //node3赋值给node2的左节点
            node1.right = node4; //node4为node1的右节点
        }
    }

2.5.2：二叉树的遍历：

所谓遍历，是指沿着某条搜索路线，依次对树中每个节点均做一次且仅做一次访问。

访问结点所进行的操作依赖具体的问题。

前序遍历： ---- 访问根结点---> 根的左子树------> 根的右子树

以上图为例，1为根结点，按照根节点--> 左子树---> 右子树方式进行递归：

递归后的顺序为：123456

具体代码如下：

public void preOrder (Node root){
        if(root == null){
            return;
        }
        System.out.println(root.val+" "); //打印根节点
        preOrder(root.left); //遍历左子树
        preOrder(root.right); //遍历右子树


    }

中序遍历：---- 根的左子树----> 根节点-----> 根的右
子树

以图为例，按照左子树--> 根节点---> 右子树的方式进行递归

递归后结果： 321546

具体代码如下：

后序遍历：---- 根的左子树-----> 根的右子树 ---->根结点

按照左子树 ---> 右子树---> 根结点进行递归后：

递归结果: 325641

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

二叉树的基本操作：

1.size():获取树结点的个数jinjin

判断当前节点是否为空，不为空，nodeSize++,同时分别遍历左右树。

size2: 省去了nodeSize++,返回值直接+1

 public static int nodeSize = 0;
//获取树中结点的个数
  public void size( Node root){
       if(root == null){
           return ;
       }
       //分别左右树遍历，遍历之前都将nodeSize++
       nodeSize++;
       size(root.left);
       size(root.right);
  }
  public int size2(Node root){
      if(root == null){
          return 0;
      }
      return size2(root.left)+size2(root.right)+1;
  }

2.获取叶子节点个数：

何为叶子节点？当前节点没有左子树和右子树。

判断当前节点是否为空，不为空，判断当前节点的左子树和右子树是否同时为空，为空，将leafsize++；

随后递归遍历左右子树

public static int leafSize;
       public void getLeafSize(Node root){
           //判断根结点是否为空
           if(root ==null){
               return  ;
           }
           //叶子结点：当前结点无左结点和右结点
           if(root.left == null && root.right == null){
               leafSize++;
           }

3.获取第k层节点的个数：

判断当前节点是否为空。（root是否为null）

2.判断k是否为1，为1，即为根节点，return1即可

3。未达到目标层数，通过递归查找root的左右子树，同时每次递归时k-1，代表进入下一层级

 public int getKLevelNodeCount(Node root,int k){
           if(root == null){
               return 0;
           }
           if(k == 1){
               return 1;
           }
           return getKLevelNodeCount(root.left,k-1)+ getKLevelNodeCount(root.right,k-1);

    }

4.获取二叉树的高度：

优先递归遍历左子树，再从下往上遍历右子树

以上图为例，遍历左子树至D，D!=null, 遍历D的左子树，返回0，再遍历右子树，也返回零，此时

判断左子树>右子树，是的话，返回left+1，否则返回right+1. 依次从往上递归

 //获取二叉树的高度：
     public int getHeight(Node root){
           if(root == null){
               return 0;
           }
           //
           int leftHeight = getHeight(root.left); //递归遍历得到左子树高度，变量存储在leftHeight中
            int rightHeight = getHeight(root.right); //递归遍历得到右子树高度，变量存储在rightHeight中


           return leftHeight>rightHeight ?  leftHeight+1 : rightHeight+1; //+1原因： 将当前结点的高度保留在内

     }

5.找到树里对应的值：

判断当前节点是否为空，不为空，判断root.val是否 == val ，

若不等，递归遍历左树查找对应的值，创建新树left来接受每次递归的树，递归结束若左树最终不为空，返回左树，右数同理。

    public Node finalVal(Node root,int val){
           if(root == null){
               return null;
           }
           //根节点 == val
        if(root.val == val){
            return root;
        }
        Node leftNode = finalVal(root.left,val);//遍历左子树查找对应的值
        if(leftNode != null){
            return leftNode;
        }

        Node rightNode = finalVal(root.right,val); //遍历右子树
        if(rightNode != null){
            return rightNode;
        }
        //如果左右树都没有遍历到：
        return null;

    }

}

今天的代码就到这里了，喜欢的老铁来个三连吧！