【前言】

你有没有想过，电脑里的文件分类、通讯录的层级关系，其实都藏着“树”的影子？树形结构是数据结构里最像“现实家族关系”的存在，而二叉树更是其中的“明星选手”——它规则清晰、操作灵活，是很多复杂数据处理的基础。这篇文章会从树形结构的概念入手，一步步拆解二叉树的类型、性质、存储和操作，帮你把这些抽象的结构变成能上手用的知识~

一、树形结构

1.树形结构的概念

树是一种非线性的数据结构，它模拟了自然界中树的结构。树形结构由若干个节点(node)组成，这些节点之间存在明确的层次关系。

• ==树是递归定义的==
• ==结点的度==：⼀个结点含有⼦树的个数称为该结点的度；
• 树的度：⼀棵树中，所有结点度的最⼤值称为树的度；
• ==叶⼦结点或终端结点==：度为0的结点称为叶结点；
• ==双亲结点或⽗结点==：指向其他节点的节点
• ==孩⼦结点或⼦结点==：被其他节点指向的节点
• ==根结点==：每个树形结构有一个根节点(root)，它是树的起点 ；
• ⾮终端结点或分⽀结点：度不为0的结点；
• ==兄弟结点==：具有相同⽗结点的结点互称为兄弟结点；
• 堂兄弟结点：双亲在同⼀层的结点互为堂兄弟；

2.树的表示形式

双亲表⽰法，孩⼦表⽰法、孩⼦双亲表⽰法、孩⼦兄弟表⽰法…

 class Node {
      int value;       //数据域                        
      Node firstChild; //第一个孩子               
      Node nextBrother;//下一个兄弟              
}

二、二叉树

1.概念

二叉树是一种非线性数据结构，其中每个节点最多有两棵树，分别称为左子树和右子树。

2.二叉树类型

二叉树分为两种：==满二叉树和完全二叉树==

2.1 满二叉树

• 定义：==每个节点都有0个或2个子节点 ==
• 特点：没有只有1个子节点的节点

2.2 完全二叉树

• 定义：==除最后一层外，所有层都完全填满，且最后一层节点尽可能靠左 ==
• 应用：常用于堆的实现

3.二叉树的性质

• 若规定根结点的层数为1，则⼀棵⾮空⼆叉树的第i层上最多==有2^(i-1)== 个结点(i>0)
• 若规定只有根结点的⼆叉树的深度为1，则深度为K的⼆叉树的最⼤结点数==是（2^k)-1== (k>=0)
• 对任何⼀棵⼆叉树,如果其叶结点个数为n0,度为2的⾮叶结点个数为n2,则有==n0＝n2＋1==
• 具有n个结点的完全⼆叉树的==深度k为log(n+1)==上取整
• 对于具有n个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的顺序对所有节点从0开始编号，则对于序号为i的结点有：

若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，⽆双亲结点
若2i+1<n，==左孩⼦序号：2i+1==，否则⽆左孩⼦
若2i+2<n，==右孩⼦序号：2i+2==，否则⽆右孩⼦

4.二叉树的存储

⼆叉树的存储结构分为：顺序存储和类似于链表的链式存储。
⼆叉树的链式存储是通过⼀个⼀个的节点引⽤起来的，常⻅的表⽰⽅式有⼆叉和三叉表⽰⽅式

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

5.二叉树的基本操作

5.1手动创建二叉树

 public static class Node {
        public char val;
        public Node left;
        public Node right;

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

    //根节点
    public Node creatTree() {
        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;
    }

5.2 二叉树的遍历

1.前序遍历

访问顺序：==根节点 → 左子树 → 右子树==

//前序遍历
    public void preOrder(Node root){
        if(root == null){
            return ;
        }
        System.out.println(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

2.中序遍历

访问顺序：==左子树 → 根节点 → 右子树==

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

3.后序遍历

访问顺序：==左子树 → 右子树 → 根节点==

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

5.3 二叉树操作方法实现

 //节点个数
    public static int count = 0;
    //获取节点个数
    public void size(Node root){
        if(root == null){
            return ;
        }
        count++;
        size(root.left);
        size(root.right);
    }
    //获取节点个数
    public int size2(Node root){
        if(root == null){
            return 0;
        }
        return size2(root.right)+size2(root.left)+1;
    }
    //获取叶子节点个数
    public int getleafNodeCount(Node root){
        if(root == null){
            return 0;
        }
        if(root.left == null&&root.right == null){
            return 1;
        }
        return getleafNodeCount(root.left)+getleafNodeCount(root.right);
    }
    //获取第k层节点个数
    public int getLevelNodeCount(Node root,int k){
        if(root == null){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        return getLevelNodeCount(root.left,k-1)+getLevelNodeCount(root.right,k-1);
    }
    //获取二叉树高度
    public int getHight(Node root){
        if(root == null){
            return 0;
        }
        int leftH = getHight(root.left);
        int rightH = getHight(root.right);
        return Math.max(leftH,rightH)+1;
    }
    //找val元素是否存在
    public Node find(Node root,char val){
        if(root == null){
            return null;
        }
        if(root.val != val ){
            return root;
        }
        Node ret = find(root.left,val);
        if(ret != null){
            return ret;
        }
        Node ret1 = find(root.right,val);
        if(ret != null){
            return ret1;
        }
        return null;
    }
}

三、总结

树形结构是一种“一对多”的层级数据组织方式，而二叉树作为它的特殊形式（每个节点最多俩孩子），凭借满二叉树、完全二叉树等细分类型，以及明确的性质（比如节点数和层数的关系），成了实际开发中常用的结构。我们可以用不同方式存储二叉树，也能通过前/中/后序遍历“逛遍”树里的每个节点——掌握这些内容，不仅能理解数据的组织逻辑，也能为后续学更复杂的树结构（比如红黑树）打牢基础。