【Java】二叉树

清疚 2023-10-13 12:42 46阅读 0赞

### 文章目录 ###

*  一、树形结构
 *  二、认识二叉树
 *   *  2.1 二叉树的概念
     *  2.2 二叉树的性质
     *  2.3 二叉树的存储
 *  三、二叉树的实现
 *   *  3.1 二叉树的创建
     *  3.2 二叉树的遍历方法
     *  3.3 二叉树的常见操作
 *  四、二叉树的应用场景
 *   *  4.1 检查两颗树是否相同
     *  4.2 寻找最近公共祖先
     *  4.3 另一颗树的子树
     *  4.4 对称二叉树的判断

--------------------

# 一、树形结构 #

树形结构是一种常见的数据结构，它由节点（Node）和节点之间的关系构成。在树中，一个节点可以有零个或多个子节点，但每个节点只有一个父节点，除了根节点外。根节点是树的顶部节点，没有父节点。

树形结构有许多应用，例如：

1.  文件系统：文件系统可以用树来表示，每个文件夹是一个节点，文件夹之间的层次关系形成树的结构。
2.  组织架构：企业的组织架构可以用树来表示，每个部门是一个节点，部门之间的关系形成树的结构。
3.  分类和层级结构：树可以用于表示分类和层级结构，例如产品分类、科学分类等。

树形结构的基本术语如下：

1.  节点（Node）：树中的每个元素称为节点，每个节点包含数据和指向其子节点的链接。
2.  根节点（Root）：树的顶部节点称为根节点，它没有父节点。
3.  子节点（Child）：一个节点的直接下级节点称为子节点。
4.  父节点（Parent）：一个节点的直接上级节点称为父节点。
5.  叶节点（Leaf）：没有子节点的节点称为叶节点或终端节点。
6.  兄弟节点（Sibling）：具有相同父节点的节点称为兄弟节点。
7.  深度（Depth）：从根节点到某个节点的路径上经过的边的数量，也可以理解为该节点所在的层级。
8.  高度（Height）：从某个节点到其最远叶节点的路径上经过的边的数量，也可以理解为该节点所在子树的最大深度。

树形结构的具体实现方式有多种，例如二叉树、多叉树、平衡树、B树等。每种实现方式都有自己的特点和适用场景。

树形结构提供了一种有效的组织和管理数据的方式，可以进行高效的搜索、插入和删除操作。在算法和数据结构中，树形结构也是一个重要的主题，具有广泛的应用。

# 二、认识二叉树 #

## 2.1 二叉树的概念 ##

二叉树（Binary Tree）是一种常见的树形结构，它由节点（Node）和节点之间的关系构成。每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树中的每个节点可以为空（null）。

![6953523de2c941129843d7b0be525ec5.png][]

## 2.2 二叉树的性质 ##

二叉树（Binary Tree）具有一些重要的性质，这些性质对于理解和操作二叉树非常有帮助。下面是二叉树的一些常见性质：

1.  每个节点最多有两个子节点：每个节点最多有一个左子节点和一个右子节点。这意味着一个节点的度数（Degree）最大为2。
2.  左子树和右子树的顺序是固定的：在二叉树中，左子树位于父节点的左侧，右子树位于父节点的右侧。改变左右子树的顺序将产生不同的二叉树。
3.  节点的度数：节点的度数是指该节点的子节点数量。二叉树中，节点的度数最大为2，即一个节点最多有两个子节点。
4.  叶节点（叶子节点）：叶节点是没有子节点的节点，也可以称为终端节点。
5.  节点的层级（Level）：根节点的层级为1，其余节点的层级为其父节点的层级加1。
6.  树的高度（Height）：树的高度是从根节点到最远叶节点的最长路径上的边数。叶节点的高度为0，空树的高度为-1。
7.  完全二叉树（Complete Binary Tree）性质：在完全二叉树中，除了最后一层外，其他层的节点都是满的，且最后一层的节点都尽量靠左排列。
8.  满二叉树（Full Binary Tree）性质：在满二叉树中，除了叶节点外，每个节点都有两个子节点。
9.  二叉搜索树（Binary Search Tree）性质：二叉搜索树是一种特殊的二叉树，它满足以下性质：对于树中的每个节点，其左子树中的所有节点都小于该节点的值，而其右子树中的所有节点都大于该节点的值。
10. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i-1) (i > 0)个结点。
11. 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 2^k - 1 (k>=0)。
12. 对任何一棵二叉树, 如果其叶结点个数为 n0，度为2的非叶结点个数为 n2，则有 n0 ＝ n2 ＋ 1。
13. 具有n个结点的完全二叉树的深度k为log2 (n + 1) 上取整。
14. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为 i 的结点有：
    
     *  若 i > 0，双亲序号：(i - 1) / 2；i = 0，i 为根结点编号，无双亲结点。
     *  若 2i + 1< n，左孩子序号：2i + 1，否则无左孩子。
     *  若 2i + 2 < n，右孩子序号：2i + 2，否则无右孩子。

## 2.3 二叉树的存储 ##

二叉树可以使用不同的数据结构进行存储。以下是几种常见的二叉树存储方式：

1.  链式存储（Linked Storage）：使用节点对象和指针来表示二叉树的结构。每个节点对象包含存储的数据以及指向左子节点和右子节点的指针。这种存储方式可以直观地表示树的结构，适用于任意形状的二叉树。Java中常用的LinkedList数据结构可以用来实现二叉树的链式存储。
2.  数组存储（Array Storage）：使用数组来表示二叉树的结构。可以使用一维数组或二维数组来存储节点的数据。通过数组的索引关系来表示节点之间的父子关系。这种存储方式可以节省存储空间，但适用于完全二叉树或满二叉树等具有规律结构的二叉树。
3.  堆存储（Heap Storage）：使用堆（Heap）数据结构来存储二叉树。堆是一种特殊的完全二叉树，通常使用数组来实现。在堆存储中，节点的位置是通过数组的索引来确定的。堆存储常用于实现优先队列等应用。

# 三、二叉树的实现 #

## 3.1 二叉树的创建 ##

二叉树节点定义：

class TreeNode {
        
        public char val;
        public TreeNode left;  // 左孩子引用
        public TreeNode right; // 右孩子引用
    
        public TreeNode(char val) {
        
            this.val = val;
        }
    }

这是一个常见的二叉树节点类定义。每个节点包含一个字符值（val）和左右孩子的引用（left 和 right）。

手动创建二叉树需要逐个节点地创建，并为每个节点设置左子节点和右子节点的引用。这种方法适用于树的结构较小或特定形状的情况。例如，创建以下二叉树：

A
        / \
       B   C
      / \   \
     D   E   F

TreeNode root = new TreeNode('A');
    root.left = new TreeNode('B');
    root.right = new TreeNode('C');
    root.left.left = new TreeNode('D');
    root.left.right = new TreeNode('E');
    root.right.right = new TreeNode('F');

## 3.2 二叉树的遍历方法 ##

二叉树的遍历是指按照一定的顺序访问树中的所有节点。常见的遍历方式包括前序遍历、中序遍历、后序遍历和层序遍历。

假设有一个二叉树如下所示：

A
        / \
       B   C
      / \   \
     D   E   F

1.  前序遍历（Preorder Traversal）：先访问根节点，然后按照左子树、右子树的顺序递归遍历子树。
    
    遍历结果：A -> B -> D -> E -> C -> F
2.  中序遍历（Inorder Traversal）：先按照左子树、根节点、右子树的顺序递归遍历子树。
    
    遍历结果：D -> B -> E -> A -> C -> F
3.  后序遍历（Postorder Traversal）：先按照左子树、右子树的顺序递归遍历子树，最后访问根节点。
    
    遍历结果：D -> E -> B -> F -> C -> A
4.  层序遍历（Level Order Traversal）：从上到下逐层遍历二叉树的节点。
    
    遍历结果：A -> B -> C -> D -> E -> F

实现这些遍历方式的代码可以使用递归或迭代的方式来实现，以下是递归方式的示例代码：

class TreeNode {
        
        char val;
        TreeNode left;
        TreeNode right;
        
        TreeNode(char val) {
        
            this.val = val;
        }
    }
    
    public class BinaryTreeTraversal {
        
        public static void preorderTraversal(TreeNode root) {
        
            if (root == null) {
        
                return;
            }
            System.out.print(root.val + " ");
            preorderTraversal(root.left);
            preorderTraversal(root.right);
        }
    
        public static void inorderTraversal(TreeNode root) {
        
            if (root == null) {
        
                return;
            }
            inorderTraversal(root.left);
            System.out.print(root.val + " ");
            inorderTraversal(root.right);
        }
    
        public static void postorderTraversal(TreeNode root) {
        
            if (root == null) {
        
                return;
            }
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            System.out.print(root.val + " ");
        }
    
        public static void levelOrderTraversal(TreeNode root) {
        
            if (root == null) {
        
                return;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
        
                TreeNode node = queue.poll();
                System.out.print(node.val + " ");
                if (node.left != null) {
        
                    queue.offer(node.left);
                }
                if (node.right != null) {
        
                    queue.offer(node.right);
                }
            }
        }
    
        public static void main(String[] args) {
        
            TreeNode root = new TreeNode('A');
            root.left = new TreeNode('B');
            root.right = new TreeNode('C');
            root.left.left = new TreeNode('D');
            root.left.right = new TreeNode('E');
            root.right.right = new TreeNode('F');
    
            System.out.print("Preorder Traversal: ");
            preorderTraversal(root);
           
    
    		inorderTraversal(root);
            System.out.println();
    
            System.out.print("Postorder Traversal: ");
            postorderTraversal(root);
            System.out.println();
    
            System.out.print("Level Order Traversal: ");
            levelOrderTraversal(root);
            System.out.println();
        }
    }

这样就可以通过调用相应的遍历函数来遍历二叉树并输出结果。请注意，在实际代码中，可以根据具体的需求，将节点的值打印、保存到集合中或执行其他操作。

## 3.3 二叉树的常见操作 ##

// 获取树中节点的个数
        public static int nodeSize = 0;
    
        public int size(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            }
            nodeSize++;
            size(root.left);
            size(root.right);
    
            return nodeSize;
        }
    
        public int size2(TreeNode root) {
        
            if (root == null)
                return 0;
            return size2(root.left) + size2((root.right)) + 1;
        }
    
        // 获取叶子节点的个数
        public int getLeafNodeCount(TreeNode root) {
        
            if (root == null)
                return 0;
            if (root.left == null && root.right == null)
                return 1;
    
            return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
        }
    
        // 获取第K层节点的个数
        // 相对于根节点，就是获取左数的第K-1层 + 右数的第K-1层
        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;
            }
            return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
        }
    
        // 检测值为value的元素是否存在
        public TreeNode find(TreeNode root, int val) {
        
    
            if (root == null)
                return null;
    
            if (root.val == val) {
        
                return root;
            }
    
            TreeNode ret1 = find(root.left, val);
            if (ret1 != null) {
        
                return ret1;
            }
            TreeNode ret2 = find(root.right, val);
            if (ret2 != null) {
        
                return ret2;
            }
    
            return null;
        }
    
    
        // 判断一棵树是不是完全二叉树
        public boolean isCompleteTree(TreeNode root) {
        
            Queue<TreeNode> queue = new LinkedList<>();
    
            if (root == null) {
        
                return true;
            }
    
            queue.offer(root);
    
            while (!queue.isEmpty()) {
        
                TreeNode node = queue.poll();
                if (node != null) {
        
                    queue.offer(node.left);
                    queue.offer(node.right);
                } else {
        
                    break;
                }
            }
    
            // 判断剩下的值是否有不为空的
            while (!queue.isEmpty()){
        
                if(queue.poll() != null){
        
                    return false;
                }
            }
    
            return true;
        }

# 四、二叉树的应用场景 #

## 4.1 检查两颗树是否相同 ##

OJ链接：[检查两颗树是否相同][Link 1]

class Solution {
        
        public boolean isSameTree(TreeNode p, TreeNode q) {
        
            if(p == null && q == null){
        
                return true;
            }
            
            if (p == null || q == null){
        
                return false;
            }
            
            if(q.val == p.val){
        
                return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
            }
            
            return false;
        }
    }

## 4.2 寻找最近公共祖先 ##

OJ链接：[寻找最近公共祖先][Link 2]

class Solution1 {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
    
            Stack<TreeNode> stackP = new Stack<>();
            Stack<TreeNode> stackQ = new Stack<>();
    
            if(!getPath(root, p, stackP) || !getPath(root, q, stackQ)){
        
                return null;
            }
            
            int size1 = stackP.size();
            int size2 = stackQ.size();
            
            int df = size1 - size2;
            if(df > 0){
        
                int cnt = df;
                while (cnt != 0){
        
                    stackP.pop();
                    cnt--;
                }
            } else {
        
                int cnt = -df;
                while (cnt != 0){
        
                    stackQ.pop();
                    cnt--;
                }
            }
            
            while (!stackQ.isEmpty()){
        
                TreeNode node1 = stackP.pop();
                TreeNode node2 = stackQ.pop();
                if(node1 == node2){
        
                    return node1;
                }
            }
            
            return null;
        }
    
        private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
        
            if(root == null || node == null){
        
                return false;
            }
    
            stack.push(root);
            if(node == root){
        
                return true;
            }
    
            boolean flag1 = getPath(root.left, node, stack);
            if(flag1){
        
                return true;
            }
    
            boolean flag2 = getPath(root.right, node, stack);
            if(flag2){
        
                return true;
            }
    
            stack.pop();
            return false;
        }
    }
    
    
    class Solution {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
    
            if(root == null){
        
                return null;
            }
    
            if(p == root || q == root){
        
                return root;
            }
    
            TreeNode leftTree = lowestCommonAncestor(root.left, p, q);
            TreeNode rightTree = lowestCommonAncestor(root.right, p, q);
    
            if (leftTree != null && rightTree != null){
        
                return  root;
            } else if (leftTree != null){
        
                return leftTree;
            } else if (rightTree != null) {
        
                return rightTree;
            } else {
        
                return null;
            }
        }
    }

## 4.3 另一颗树的子树 ##

OJ链接：[另一颗树的子树][Link 3]

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
    
        // 判断两棵树是否相同
        private boolean isSameTree(TreeNode p, TreeNode q){
        
            if(p == null && q == null){
        
                return true;
            }
            
            if(p == null || q == null) {
        
                return false;
            }
            
            if(q.val == p.val) {
        
                return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
            }
            
            return false;
        }
        public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        
            if(subRoot == null)
                return true;
            
            if(root == null){
        
                return false;
            }
            
            return isSameTree(root, subRoot) ||
                   isSubtree(root.left, subRoot) ||
                   isSubtree(root.right, subRoot);
        }
    }

## 4.4 对称二叉树的判断 ##

OJ链接：[对称二叉树的判断][Link 4]

class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        
            if(root == null )
                return true;
            return _isSymmetric(root.left, root.right);
        }
    
        private boolean _isSymmetric(TreeNode leftTree, TreeNode rightTree){
        
            if(leftTree == null && rightTree == null)
                return true;
            if(leftTree == null || rightTree == null)
                return false;
            
            if(leftTree.val != rightTree.val){
        
                return false;
            }
            
            return _isSymmetric(leftTree.left, rightTree.right) &&
                    _isSymmetric(leftTree.right, rightTree.left);
        }
    }

[6953523de2c941129843d7b0be525ec5.png]: https://img-blog.csdnimg.cn/6953523de2c941129843d7b0be525ec5.png
[Link 1]: https://leetcode.cn/problems/same-tree/
[Link 2]: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
[Link 3]: https://leetcode.cn/problems/subtree-of-another-tree/
[Link 4]: https://leetcode.cn/problems/symmetric-tree/