当前位置：首页 > article >正文

数据结构（Java）——二叉树

article 2025/1/25 3:47:09

1.概念

二叉树是一种树形数据结构，其中每个节点最多有两个子节点，通常被称为左子节点和右子节点。二叉树可以是空的（即没有节点），或者由一个根节点以及零个或多个左子树和右子树组成，其中左子树和右子树也分别是二叉树。

2. 基本术语

根节点（Root）：树的起始节点。
子节点（Children）：每个节点可以有零个、一个或两个子节点，分别称为左子节点和右子节点。
父节点（Parent）：一个节点的直接上层节点。
兄弟节点（Siblings）：具有相同父节点的节点。
叶子节点（Leaf Nodes）：没有子节点的节点。
内部节点（Internal Nodes）：非叶子节点，即至少有一个子节点的节点。
深度（Depth）：从根节点到某个节点的最长路径上的边数。
高度（Height）：从某个节点到其最远叶子节点的最长路径上的边数。根节点的高度是整个树的高度。

3. 类型

满二叉树（Full Binary Tree）：每个节点要么是叶子节点，要么恰好有两个子节点。
完全二叉树（Complete Binary Tree）：除了最后一层外，每一层都是满的，并且最后一层的节点都靠左对齐。
平衡二叉树（Balanced Binary Tree）：一个二叉树的每个节点的两个子树的高度差不会超过1。
搜索二叉树（Binary Search Tree, BST）：每个节点的值都大于其左子树所有节点的值，小于其右子树所有节点的值。

4. 操作

4.1 构建二叉树

代码示例：

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

        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode createBinaryTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        return A;
    }

4.2 遍历

4.2.1 前序遍历

原理：根节点 -> 左子树 -> 右子树（根左右）

代码示例：

    //前序排列
    public void preOrder(TreeNode root){
        if(root == null){
            return ;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

运行结果如下：

4.2.2 中序遍历

原理：左子树 -> 根节点 -> 右子树（左根右）

代码示例：

    // 中序遍历
    public void inOrder(TreeNode root){
        if(root == null){
            return ;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

运行结果如下：

4.2.3 后序遍历

原理：左子树 -> 右子树 -> 根节点（左右根）

代码示例：

    // 后序遍历
    public void postOrder(TreeNode root){
        if(root == null){
            return ;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

运行结果如下：

4.2.4 层序遍历

原理：按层次从上到下、从左到右遍历节点。

代码示例：

   //层序遍历
    public  void levelOrder(TreeNode root){
        if(root == null)
            return;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode node=  queue.poll();
            System.out.print(node.val+" ");
            if(temp.left != null)
                queue.add(node.left);
            if(temp.right != null)
                queue.add(node.right);
        }
    }

运行结果如下：

4.3 其他方法

代码示例：

    // 获取树中节点的个数
   public int size(TreeNode root){
        if(root == null){
            return 0;
        }
        return size(root.left) + size(root.right) + 1;
    }
    // 获取叶子节点的个数
    int getLeafNodeCount(TreeNode root){
        if(root == null){
            return 0;
        }
        if(root.right == null&&root.left == null){
            return 1;
        }
        return  getLeafNodeCount(root.left) 
              + getLeafNodeCount(root.right);
    }

    // 获取第K层节点的个数
    public int getKLevelNodeCount(TreeNode root,int k){
        if(root == null){
            return 0;
        }
        if(k == 1){
             return 1;
        }

        return getKLevelNodeCount(root.left,k - 1)
             + getKLevelNodeCount(root.right,k -1);
    }
    // 获取二叉树的高度
    public int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return leftHeight > rightHeight?leftHeight + 1:rightHeight+1;
    }

    // 检测值为value的元素是否存在
    public TreeNode find(TreeNode root, char val){
        if(root == null){
            return null;
        }
        if(root.val == val){
            return root;
        }
        TreeNode ret = find(root.left,val);
        if(ret!= null){
            return ret;
        }
        ret  = find(root.right,val);
        if(ret!= null){
            return ret;
        }
        return null;
    }

运行结果如下：