2.对于有n个结点的完全二叉树，如果按照从上到下，从左至右的顺序对所有的结点进行编号，则对于序号为i的结点：

一、二叉树的遍历

1. 二叉树的遍历可分为四种：

前序、中序和后序遍历均要用到栈。

前序遍历（preOrder）：给定一个二叉树，先访问根，再遍历左子树，最后再遍历右子树。，

public void preOrder(Node root) {
        if (root == null) {
            return;
        }
        System.out.println(root.val+"");
        preOrder(root.left);
        preOrder(root.ringt);
    }

中序遍历：先遍历左子树，再访问根，再遍历右子树。

     /**
     * 传入一个二叉树的根节点。根据中序遍历访问二叉树
     * 先左后根最后在右
     */
    public void inOrder(Node root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.println(root.val+"");
        inOrder(root.ringt);
    }

后序遍历：先遍历左子树，再遍历右子树，再访问根。

/**
     * 传入一个二叉树的根节点root，以后序遍历访问二叉树
     * 先左后右最后在根
     */
    public void postOrder(Node root) {
        if (root == null) {
            return;
        }
        preOrder(root.left);
        preOrder(root.ringt);
        System.out.println(root.val+"");
    }

层序遍历：按照从上到下、从左到右的次序进行遍历。先遍历完一层，再遍历下一层。该遍历要用到队列。

二、二叉树节点的性质

二叉树中有两种特殊的二叉树：

满二叉树：如果一个二叉树每一层的结点数都达到最大值，那么这个二叉树称为满二叉树。即一个二叉树的层数为k，且结点数为2^k - 1，则它为满二叉树。

完全二叉树：它是由满二叉树引出来的。如果有一个深度为k的，有n个结点的二叉树，当且仅当其中每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称其为完全二叉树。(堆就是一个完全二叉树）

1.二叉树的深度:是指所有结点中最深结点所在的层数。

具有n个结点的完全二叉树它的深度k为log2（n+1）上取整。

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) (i>0)个结点。

2.对于有n个结点的完全二叉树，如果按照从上到下，从左至右的顺序对所有的结点进行编号，则对于序号为i的结点：

若i>0，则父节点序号为（i-1）/ 2，若i=0，则其为根结点，没有父结点。

若2i+1<n，则左孩子序号为：2i+1，否则无右孩子。

若2i+2<n，则右孩子序号为：2i+2，否则无左右孩子。

package bin_tree;

public class MyBinaryTree {

    //孩子兄弟表示法
    private static class Node {
        private char val;
        private Node left;
        private Node ringt;

        public Node(char val) {
            this.val = val;
        }
    }

    public Node buildATree() {
        Node nodeA = new Node('A');
        Node nodeB = new Node('B');
        Node nodeC = new Node('C');
        Node nodeD = new Node('D');
        Node nodeE = new Node('E');
        Node nodeF = new Node('F');
        Node nodeG = new Node('G');
        Node nodeH = new Node('H');
        nodeA.left = nodeB;
        nodeA.ringt = nodeC;
        nodeB.left = nodeD;
        nodeB.ringt = nodeE;
        nodeE.left = nodeG;
        nodeG.ringt = nodeH;
        nodeC.ringt = nodeF;
        return nodeA;

    }

    //先序遍历
    //先根后左右
    public void preOrder(Node root) {
        if (root == null) {
            return;
        }
        System.out.println(root.val+"");
        preOrder(root.left);
        preOrder(root.ringt);
    }

    /**
     * 传入一个二叉树的根节点。根据中序遍历访问二叉树
     * 先左后根最后在右
     */
    public void inOrder(Node root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.println(root.val+"");
        inOrder(root.ringt);
    }

    /**
     * 传入一个二叉树的根节点root，以后序遍历访问二叉树
     * 先左后右最后在根
     */
    public void postOrder(Node root) {
        if (root == null) {
            return;
        }
        preOrder(root.left);
        preOrder(root.ringt);
        System.out.println(root.val+"");
    }

    /**
     * 传入一个二叉树的根节点，求该二叉树的节点个数
     * @param root 二叉树的根节点
     * @return
     */
    public int getNodeCount(Node root){
        if (root == null){
            return 0;
        }
        //已知根节点为一，剩下节点的个数等于左子树的节点的个数getNodeCount(root.left) +右子树的节点的个数 getNodeCount(root.ringt);
        return 1 + getNodeCount(root.left) + getNodeCount(root.ringt);
    }

    /**
     * 传入一个二叉树的根节点，就能求得二叉树叶子节点的个数
     * @param root 传入根节点
     * @return
     */
     public int getLeafNodeCount(Node root){
         //空树
        if (root == null){
            return 0;
        }
        //只有根节点
        if (root.left == null && root.ringt == null){
            return 1;
        }
        //此时二叉树不为空且有子树
        //此时二叉树的叶子节点的个数= 左树叶子节点的个数 + 右树叶子节点的个数
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.ringt);
     }

    /**
     * 传入一个二叉树的根节点，求二叉树的高度
     * @param root 传入二叉树的根节点
     * @return
     */
     private int heightTree(Node root){
         if (root == null){
             return 0;
         }
         //二叉树不为空
         return 1 + Math.max((heightTree(root.left)),(heightTree(root.ringt)));
     }

    /**
     * 传入一个二叉树的根节点，求指定val是否是二叉树的节点
     * @param root 根节点
     * @param val 指定元素
     * @return
     */
     private boolean contains(Node root,char val){
         if (root == null){
             return false;
         }
         if (root.val == val){
             return true;
         }
         return contains(root.left,val) || contains(root.ringt,val);
     }
     private int getLevelNode(Node root,int k){
         if (k <= 0|| root == null){
             return 0;
         }
         if (k == 1){
             return 1;
         }
         return getLevelNode(root.left,k-1) + getLevelNode(root.ringt,k-1);
     }

    public static void main(String[] args) {
        MyBinaryTree myBinaryTree = new MyBinaryTree();
        Node root = myBinaryTree.buildATree();
        System.out.println("先序遍历");
        myBinaryTree.preOrder(root);
        System.out.println();
        System.out.println("--------------------");
        System.out.println("中序遍历");
        myBinaryTree.inOrder(root);
        System.out.println();
        System.out.println("--------------------");
        System.out.println("后序遍历");
        myBinaryTree.postOrder(root);
        System.out.println("二叉树节点的个数");
        System.out.println(myBinaryTree.getNodeCount(root));
        System.out.println("二叉树叶子节点的个数");
        System.out.println(myBinaryTree.getLeafNodeCount(root));
        System.out.println("树的高度为");
        System.out.println(myBinaryTree.heightTree(root));
        System.out.println(myBinaryTree.contains(root,'A'));
        System.out.println(myBinaryTree.contains(root,'L'));
        System.out.println("二叉树第4层节点个数");
        System.out.println(myBinaryTree.getLevelNode(root,4));
    }
}

原文链接：https://blog.csdn.net/a1085653724/article/details/121667697