二叉树

一.基本概念

1. 概念
   一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
2. 特点：

• 每个结点最多有两棵子树，即二叉树不存在度大于 2 的结点。
• 二叉树的子树有左右之分，其子树的次序不能颠倒，因此二叉树是有序树。

3**.五种基本形态**

• 一棵空树
• 只有一个节点
• 只有头节点和左子树
• 只有根和右子树
• 根节点、左子树、右子树

二.特殊的俩种二叉树

1. 满二叉树
   一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。

2. 完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

三.二叉树的存储方式

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

3.1常用的链式存储

//孩子表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
public Node(char val) {
        this.val = val;
    }
}

// 孩子双亲表示法
class Node {
int val; // 数据域
Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
Node parent; // 当前节点的根节点
public Node(char val) {
        this.val = val;
    }
}

四.二叉树的三种遍历方式

• 前序遍历(NLR):顺序：根节点–》根的左子树–》根的右子树

//前序遍历
    void preOrderTraversal(Node root){
        if (root == null)return;//如果树为空树，直接就退出；
        //到这一步说明树不是空树，那么就可以打印根节点；
        System.out.println(root.val+" ");
        
        preOrderTraversal(root.left);
        //右子树和左子树同样的道理；
        preOrderTraversal(root.right);
    }

• 中序遍历(LNR):顺序：根的左子树–》根节点–》根的右子树

 //中序遍历
    void inOrderTraversal(Node root){
        if (root == null)return;
        inOrderTraversal(root.left);
        System.out.println(root.val+" ");
        inOrderTraversal(root.right);
    }

• 后序遍历(LRN):顺序：根的左子树–》根的右子树–》根节点

//后序遍历
    void postOrderTraversal(Node root){
        if (root == null)return;
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.println(root.val+" ");
    }

五.基本操作（重点）

• 求节点个数

//遍历思路求树的节点个数(按照前序遍历的顺序)
    static int size = 0;
    void getSize1(Node root){
        if (root == null)return;
        size++;
        getSize1(root.left);
        getSize1(root.right);
    }

    //子问题思想，求节点个数（先算左边，在算右边，最后加起来在加根节点的一）
    int getSize2(Node root){
        if (root == null)return 0;
        int left = getSize2(root.left);
        int right = getSize2(root.right);
        return left+right+1;
    }

• 求叶子节点个数（度为0的是叶子节点）

//遍历思路
    static int leafsize = 0;
    public void getLeafSize1(Node root){
        if (root == null) return;
        if (root.left == null && root.right == null)
            leafsize++;
        getLeafSize1(root.left);
        getLeafSize1(root.right);
    }

//子问题思路--求叶子节点的个数
    public int getLeafSize2(Node root){
        if (root == null)return 0;
        if (root.left == null && root.right == null)
            return 1;
        return getLeafSize2(root.left)+getLeafSize2(root.right);
    }

• 求第k层的节点个数

//子问题思路--求第k层的节点个数
    int getLevelSize (Node root,int k){
        if (root == null)return 0;
        if (k == 1)return 1;
        return getLevelSize(root.left,k-1)+getLevelSize(root.right,k-1);
    }

• 求树的深度（左子树和右子树深度的最大值，再加上根节点的1）

//子问题思路--求树的深度
    int getHeight(Node root){
        if (root == null)return 0;
        
        return Math.max(getHeight(root.left),getHeight(root.right))+1;
    }

• 查找 val 所在节点

    Node find(Node root, int val){
        if (root == null)return null;
        if (root.val == val)return root;
        Node newroot =find(root.left,val);
        if (newroot != null){
        return newroot;}
        Node newroot1 = find(root.right,val);
        if (newroot1 != null){
            return newroot1;
        }
        return null;
    }

完整运行代码

import java.lang.Math;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Node {
    char val;
    Node left;
    Node right;
    //构造方法
    public Node(char val) {
        this.val = val;
    }
}
public class BinaryTree {
    //构造一颗树
    public  Node createTree(){
          Node A = new Node('A');
          Node B = new Node('B');
          Node C = new Node('C');
          Node D = new Node('D');
          Node E = new Node('E');
          Node F = new Node('F');
          Node G = new Node('G');
          Node H = new Node('H');
          A.left = B;
          A.right = C;
          B.left = D;
          B.right = E;
          E.right = H;
          C.left = F;
          C.right = G;
          return A;
      }
  
    //前序遍历
    void preOrderTraversal(Node root){
        if (root == null)return;
        System.out.print(root.val+" ");
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }
    //中序遍历
    void inOrderTraversal(Node root){
        if (root == null)return;
        inOrderTraversal(root.left);
        System.out.print(root.val+" ");
        inOrderTraversal(root.right);
    }
    //后序遍历
    void postOrderTraversal(Node root){
        if (root == null)return;
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.print(root.val+" ");
    }


    static int size = 0;
    //子问题思想，求节点个数（先算左边，在算右边，最后加起来在加根节点的一）
    int getSize2(Node root){
        if (root == null)return 0;
        int left = getSize2(root.left);
        int right = getSize2(root.right);
        return left+right+1;
    }

    //遍历思路求节点个数
    void getSize1(Node root){
        if (root == null)return;
        size++;
        getSize1(root.left);
        getSize1(root.right);

    }


    //子问题思路--求叶子节点的个数
    public int getLeafSize2(Node root){
        if (root == null)return 0;
        if (root.left == null && root.right == null)
            return 1;
        return getLeafSize2(root.left)+getLeafSize2(root.right);
    }

    //遍历思路
    static int leafsize = 0;
    public void getLeafSize1(Node root){
        if (root == null) return;
        if (root.left == null && root.right == null)
            leafsize++;
        getLeafSize1(root.left);
        getLeafSize1(root.right);
    }

    //子问题思路--求第k层的节点个数
    int getLevelSize (Node root,int k){
        if (root == null)return 0;
        if (k == 1)return 1;
        return getLevelSize(root.left,k-1)+getLevelSize(root.right,k-1);
    }

    //子问题思路--求树的深度
    int getHeight(Node root){
        if (root == null)return 0;
        
        return Math.max(getHeight(root.left),getHeight(root.right))+1;
    }
    
    Node find(Node root, int val){
        if (root == null)return null;
        if (root.val == val)return root;
        Node newroot =find(root.left,val);
        if (newroot != null){
        return newroot;}
        Node newroot1 = find(root.right,val);
        if (newroot1 != null){
            return newroot1;
        }
        return null;
    }

//测试类
class TestDemo{
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();//创建对象
        Node root = binaryTree.createTree();//构造一棵树，通过调用BinaryTree类里面的createTree()方法
        System.out.print("前序遍历:");
        binaryTree.preOrderTraversal(root);
        System.out.println();
        System.out.print("中序遍历:");
        binaryTree.inOrderTraversal(root);
        System.out.println();
        System.out.print("后序遍历:");
        binaryTree.postOrderTraversal(root);
        System.out.println();

        binaryTree.getSize1(root);
        System.out.println("树的节点个数:"+binaryTree.size);
        System.out.println("树的节点个数:"+binaryTree.getSize2(root));
        System.out.println();
        binaryTree.getLeafSize1(root);
        System.out.println("叶子节点个数:"+binaryTree.leafsize);
        System.out.println("叶子节点个数:"+binaryTree.getLeafSize2(root));
        System.out.println();
        System.out.println("第k层的节点个数:"+binaryTree.getLevelSize(root, 3));
        System.out.println();

        System.out.println("树的深度:"+binaryTree.getHeight(root));
        System.out.println();
        Node root1 = binaryTree.find(root, 'A');
        System.out.println(root1.val);
        Node root2 = binaryTree.find(root, 'H');
        System.out.println(root2.val);
        Node root3 = binaryTree.find(root, 'l');
        if (root3 == null){
            System.out.println(root3);
        }else{
            System.out.println(root.val);
        }
        }
        }

结果

前序遍历:A B D E H C F G 
中序遍历:D B E H A F C G 
后序遍历:D H E B F G C A 
树的节点个数:8
树的节点个数:8

叶子节点个数:4
叶子节点个数:4

第k层的节点个数:4

树的深度:4

A
H
null