[数据结构]二叉树(JAVA)_java 二叉树

二： 两种特殊的二叉树

1. 满二叉树:

2. 完全二叉树:

三：二叉树重要的性质

四：二叉树的简单代码模拟实现

public class BinaryTree {
    //孩子结点表示法
    static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;
 
        public TreeNode(int value) {
            this.value = value;
        }
    }
 
    public TreeNode root;
 
    public void createTree() {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node5.right = node8;
        node3.left = node6;
        node3.right = node7;
        root = node1;
    }
    public TreeNode createTree(LinkedList<Integer> list){
        //含参的创建方法
        TreeNode root=null;
        if(list==null||list.isEmpty()){
            return null;
        }
        Integer value=list.removeFirst();
        if(value!=null){
            root=new TreeNode(value);
            root.left=createTree(list);
            root.right=createTree(list);
        }
        return root;
    }
   //前序遍历
    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.value + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
   //中序遍历
   
    public void midOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        midOrder(root.left);
        System.out.print(root.value + " ");
        midOrder(root.right);
     }
    //后序遍历
 
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.value + " ");
    }
 
    //层序遍历
    void levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) {
            queue.offer(root);
        }
        while (!queue.isEmpty()) {
            root = queue.peek();
            if (root.left != null) {
                queue.offer(queue.peek().left);
            }
            if (root.right != null) {
                queue.offer(queue.peek().right);
            }
            System.out.print(queue.poll().value + " ");
        }
        System.out.println();
    }
    
 
    // 获取树中节点的个数
    int size(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + size1(root.left) + size1(root.right);
    }
 
    // 获取叶子节点的个数
    int getLeafNodeCount1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount1(root.left) + getLeafNodeCount1(root.right);
 
    }
 // 获取第K层节点的个数
    int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null || k == 0) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
    }
  // 获取二叉树的高度
    int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }
  // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.value == val) {
            return root;
        }
        TreeNode rootLeft = find(root.left, val);
        TreeNode rootRight = find(root.right, val);
        if (rootLeft != null) {
            return rootLeft;
        }
        if (rootRight != null) {
            return rootRight;
        }
        return null;
    }