数据结构专题（四）—— 树

小咪咪 2022-03-18 14:10 207阅读 0赞

树在计算机中占着举足轻重的地位，目前计算机中的文件系统，程序开发中的XML与HTML等都是树这一数据结构的运用。甚至包括英雄联盟的匹配系统也采用了树，这章内容重点讨论树结构，并使用Java对一些常见的面试问题做个总结。由于关于树的问题众多，所以我准备分两部分进行整理。

**什么是树？树的深度，高度，根节点，父节点，子节点等概念一张图即可说明清楚**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMjM4ODYz_size_16_color_FFFFFF_t_70][]  
关于树的编程问题有很多变形，但经过研究发现大部分解决思路的核心是递归思想

## **1. 树的创建初始化** ##

## **2. 求二叉树的最大深度** ##

## **3. 求二叉树的最小深度** ##

## **4. 求二叉树中节点的个数** ##

## **5. 求二叉树中叶子节点的个数** ##

## **6. 求二叉树中第K层节点个数** ##

## **7. 判断二叉树是否为平衡二叉树** ##

## **8. 判断二叉树是否为完全二叉树** ##

## **9. 判断一个二叉树是否为镜像** ##

## **10. 求一个二叉树的镜像** ##

## **11. 求两个二叉树最低公共祖先节点** ##

## **12. 前序中序后序遍历二叉树** ##

此处使用Java语言完成对上列各种问题的编程实现。

**1.树的创建初始化**

//1. 树的初始化
    
    class TreeNode{
    
        int value;
        TreeNode left;
        TreeNode right;
    
        public TreeNode(int value){
            this.value = value;
        }
    }

## **2. 求二叉树的最大深度   ** ##

public int searchMaxDepth(TreeNode node){
    
        if(node == null){
            return 0;
        }
        
        int leftDepth = searchMaxDepth(node.left);
        int rightDepth = searchMaxDepth(node.right);
        
        return (leftDepth >= rightDepth ? leftDepth : rightDepth) + 1;
    }

## 3. 求二叉树的最小深度 ##

public int searchMinDepth(TreeNode node){
    
            if(node == null){
                return 0;
            }
    
            if(node != null && node.left == null && node.right == null){
                return 1;
            }
    
            //若左节点为空那么就返回右边节点的深度
            if(node.left == null){
                return searchMinDepth(node.right) + 1;
            }
    
            if(node.right == null){
                return searchMinDepth(node.left) + 1;
            }
    
            //若左右两边都存在节点则进入下一层进行比较
            int leftDepth = searchMinDepth(node.left);
            int rightDepth = searchMinDepth(node.right);
    
            return (leftDepth <= rightDepth ? leftDepth : rightDepth) + 1;
    
    }

## 4.求二叉树中节点的个数     ##

//思路：使用一种遍历方式，创建一个计数器去统计
        public int nodeNum(TreeNode node){
    
            int count = 0;
            if(node == null){
                return 0;
            }
    
            //此处采用BFS的方式去遍历，并且把节点存储到一个队列中
            Queue<TreeNode> list = new LinkedList<TreeNode>();
            list.add(node);
    
            while(!list.isEmpty()){
    
                if(node.left != null){
                    list.add(node.left);
                }
    
                if(node.right != null){
                    list.add(node.right);
                }
    
                list.poll();
                count++;
                node = list.peek();
            }
    
            return count;
        }

## 5. 求二叉树中叶子节点的个数 ##

//思路：采用BFS遍历树，对每个节点的状态进行判断
        
        public int leafNum(TreeNode node){
    
            int count = 0;
    
            if(node == null){
                return 0;
            }
    
            if(node != null && node.left == null && node.right == null){
                return 1;
            }
    
            //遍历的同时对每个节点的左右进行判断
            Queue<TreeNode> list = new LinkedList<TreeNode>();
            list.add(node);
    
            while(!list.isEmpty()){
    
                if(node.left != null){
                    list.add(node.left);
                }
    
                if(node.right != null){
                    list.add(node.right);
                }
    
                if(list.peek().left == null && list.peek().right == null){
                    count++;
                }
    
                list.poll();
                node = list.peek();
            }
            return count;
        }

## 6.求二叉树第K层节点的个数 ##

//思路：递归 K其实可以理解为递归K次，node才得以从root更新到第K层的节点
    
        public int KlevelNodeNum(TreeNode node, int k){
    
            //若该节点不存在或者K不符合条件则返回0
            if(node == null || k <= 0){
                return 0;
            }
    
            if(node != null && k == 1){
                return 1;
            }
    
            //要想得到第K层的节点数目就必须先知道第K-1层的节点是什么状态（即是否含有左右节点）
            return KlevelNodeNum(node.left, k - 1) + KlevelNodeNum(node.right, k - 1);
    
        }

## 7.判断二叉树是否为平衡二叉树（AVL树） ##

//首先什么条件下的二叉树才是平衡二叉树？二叉树中每个节点的左右子树深度相差不超过1
    //可以利用递归求每个节点的深度，将求得的深度进行比较即可
    
        public boolean isBalanced(TreeNode node){
    
            if(node == null){
                return true;
            }
    
            int leftDepth = searchDepth(node.left);
            int rightDepth = searchDepth(node.right);
    
            if(Math.abs(leftDepth - rightDepth) > 1){
                return false;
            }
    
            boolean leftBalanced = isBalanced(node.left);
            boolean rightBalanced = isBalanced(node.right);
    
            return leftBalanced && rightBalanced;
    
        }
    
    
        public int searchDepth(TreeNode node){
    
            if(node == null){
                return 0;
            }
    
            if(node != null && node.left == null && node.right == null){
                return 1;
            }
    
            int leftDepth = searchDepth(node.left);
            int rightDepth = searchDepth(node.right);
    
            return (leftDepth >= rightDepth ? leftDepth : rightDepth) + 1;
        }

## 8.判断二叉树是否为完全二叉树（CBT Complete binary tree） ##

//什么是完全二叉树？若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大数，
    //第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
    
        public boolean isCBT(TreeNode node){
    
            //通过BFS逐层遍历树，使用队列进行存储，对队列中的每个节点进行判断
    
            //空树也可以属于完全二叉树
            if(node == null){
                return true;
            }
    
            Queue<TreeNode> list = new LinkedList<TreeNode>();
            list.add(node);
    
            while(!list.isEmpty()){
                if(node.left != null){
                    list.add(node.left);
                }
    
                if(node.right != null){
                    list.add(node.right);
                }
    
                //若左节点为空，右节点不为空，直接判定不是完全二叉树
                if(node.left == null && node.right != null){
                    return false;
                }
    
                //如果有左节点但没有右节点，那么该节点的所有子节点必须为叶子节点，即该节点的子节点左右都为空
                if(node.left != null && node.right == null){
                    if(node.left.left != null || node.left.right != null){
                        return false;
                    }
                }
    
                list.poll();
                node = list.peek();
            }
            return true;
        }

## 9. 判断一棵二叉树是否为镜像 ##

//思路：判断方法其实是判断二叉树的子树是否为镜像，可以使用递归的方式进行求解
    
        /*
        算法思想是：首先判断这棵树是否为空树，如果空树则直接返回true
    
        如果不为空，则在进行分类：
        case1：节点的左右子树为空，则直接返回true
        case2：节点的左右子树有一个为空，则直接返回false
        case3：节点的左右子树均不为空，则判断节点的左右子节点的值是否相等
               并且判断左节点的子左节点和右节点的右子节点是否对称
               还有左节点的右子节点和右节点的左子节点是否对称
        */
    
        public boolean isSymmetric(TreeNode node){
    
            if(node == null){
                return true;
            }
    
            if(node.left == null || node.right == null){
                return false;
            }
    
            //判断两棵子树是否对称
            return symmetric(node.left, node.right);
        }
    
        //比较两棵树是否是镜像的
        public boolean symmetric(TreeNode left, TreeNode right){
    
            //case 1
            if(left == null && right == null){
                return true;
            }
    
            //case 2
            if(left == null || right == null){
                return false;
            }
    
            //case 3
            return left.value == right.value && symmetric(left.left, right.right) && symmetric(left.right, right.left);
        }

## 10.给出一个二叉树，求解其镜像。 ##

//思路：递归交换子树的节点
        public void mirror(TreeNode node){
    
            if(node == null){
                return;
            }
    
            //进行交换节点操作
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
    
            mirror(node.left);
            mirror(node.right);
        }

## 11. 求二叉搜索树最低公共祖先节点 lowest common ancestor(LCA) ##

//如果是二叉搜索树，递归判断
    
        //case 1 如果两个节点分别在根节点的左右，那么该根节点就是所求节点
    
        //case 2 两个节点在根节点的同侧，进行递归搜索同侧的树
    
        public TreeNode findLCA(TreeNode node, TreeNode p, TreeNode q){
    
            if(node == null){
                return null;
            }
    
            if(node.value == p.value || node.value == q.value){
                return node;
            }
    
            //当节点分别在node左右两侧，那么根节点就是低公共祖先节点
            if(p.value < node.value && q.value > node.value){
                return node;
            }
    
            TreeNode treenode = null;
            //若两节点均小于node，说明两个节点都是位于左子树，同理两节点都大于node，那么就说明两节点都位于右子树
            if(p.value < node.value && q.value < node.value){
                treenode = findLCA(node.left, p, q);
            }
    
            if(p.value >= node.value){
                treenode = findLCA(node.right, p, q);
            }
    
            return treenode;
        }

## 12. 前序中序后序遍历二叉树 pre-order in-order post-order ##

//pre-order: root left right
        public void preorder(TreeNode node){
    
            if(node == null){
                return;
            }
    
            if(node != null){
                System.out.println(node.value);
                preorder(node.left);
                preorder(node.right);
            }
        }
    
    
        //inorder: left root right
        public void inorder(TreeNode node){
            
            if(node == null){
                return;
            }
    
            if(node != null){
                inorder(node.left);
                System.out.println(node.value);
                inorder(node.right);
            }
        }
    
        //post-order: left right root
        public void postorder(TreeNode node){
    
            if(node == null){
                return;
            }
    
            if(node != null){
                postorder(node.left);
                postorder(node.right);
                System.out.println(node.value);
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMjM4ODYz_size_16_color_FFFFFF_t_70]: /images/20220318/bab0485637e8430dbd17bcc49863d08d.png