二叉树的基本操作（附代码）

拼搏现实的明天。 2022-11-13 11:23 166阅读 0赞

### 二叉树 的基本操作 ###

*  二叉树定义
 *   *  结点的定义：
     *  构建二叉树
     *  前、中、后序遍历
     *  遍历求结点的个数
     *  汇集思想求结点的个数
     *  遍历求叶子结点的个数
     *  汇集思想求叶子结点的个数
     *  求第k层结点个数
     *  求二叉树的高度
     *  是否存在结点为e的结点
     *  是否存在结点为e的结点，返回其结点位置
     *  判断 node 在不在以 root 为根的树中，node 一定不是 null

# 二叉树定义 #

详见我的上一篇博客：  
[初识二叉树][Link 1]

## 结点的定义： ##

结点的定义 有数值域，还有左孩子的引用和右孩子的引用，分别表示以左右孩子为根的左子树和右子树

public class TreeNode { 
        public int val;
        public TreeNode left;
        public TreeNode right;
    
        public TreeNode(int val) { 
            this.val = val;
            this.left = null;
            this.right = null;
        }
    
        @Override
        public String toString() { 
            return String.format("TreeNode{%c}", val);
        }
    }

## 构建二叉树 ##

我们先进行构建两棵二叉树，方便验证下面操作是否正确：

public class buildTree { 
        public static TreeNode buildTree1() { 
            // 让大家练习前中后序的树
            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');
            TreeNode h = new TreeNode('h');
            TreeNode i = new TreeNode('i');
            TreeNode j = new TreeNode('j');
            TreeNode k = new TreeNode('k');
            TreeNode l = new TreeNode('l');
            TreeNode m = new TreeNode('m');
            TreeNode n = new TreeNode('n');
            a.left = b; a.right = c;
            b.left = d; b.right = e; 
            c.left = f; c.right = g;
            d.right = h;
            f.left = i; f.right = j;
            g.right = k;
            h.right = l;
            j.left = m;
            m.left = n;
            return a;
        }
    
        public static TreeNode buildTree2() { 
            // 构建课件上的树
            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');
            TreeNode h = new TreeNode('h');
            a.left = b; a.right = c;
            b.left = d; b.right = e;
            c.left = f; c.right = g;
            e.right = h;
            return a;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]

## 前、中、后序遍历 ##

前、中、后序遍历主要就是头结点什么时候处理，我们可以利用递归的思想，简便的求解。

//前序遍历
        public static void preOrderTraversal(TreeNode root) { 
            if (root == null) { 
                return;
            }
            System.out.printf("%c ",root.val);
            preOrderTraversal(root.left);
            preOrderTraversal(root.right);
        }
    
        //中序遍历
        public static void inOrderTraversal(TreeNode root) { 
            if (root == null) { 
                return;
            }
            inOrderTraversal(root.left);
            System.out.printf("%c ",root.val);
            inOrderTraversal(root.right);
        }
    
        //后序遍历
        public static void posteOrderTraversal(TreeNode root) { 
            if (root == null) { 
                return;
            }
            posteOrderTraversal(root.left);
            posteOrderTraversal(root.right);
            System.out.printf("%c ",root.val);
        }

测试：

public static void main(String[] args) { 
            TreeNode root1 = buildTree.buildTree1();
            TreeNode root2 = buildTree.buildTree2();
            preOrderTraversal(root1);
            System.out.println();
            inOrderTraversal(root1);
            System.out.println();
            posteOrderTraversal(root1);
            System.out.println();
            System.out.println("================================");
            preOrderTraversal(root2);
            System.out.println();
            inOrderTraversal(root2);
            System.out.println();
            posteOrderTraversal(root2);
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]

## 遍历求结点的个数 ##

我们可以采用遍历的思想求出结点个数，需要定义一个size，记录节点个数

//遍历求结点的个数
        static int size = 0;
    
        public static void getSize1(TreeNode root) { 
            if (root == null) { 
                return;
            }
            size++;
            getSize1(root.left);
            getSize1(root.right);
        }

测试

//测试求解节点数
        public static void main(String[] args) { 
            TreeNode root1 = buildTree.buildTree1();
            TreeNode root2 = buildTree.buildTree2();
    
            getSize1(root1);
            System.out.println(size);
            getSize1(root2);
            System.out.println(size);
            System.out.println("===========");
            size=0;
            getSize1(root1);
            System.out.println(size);
            size=0;
            getSize1(root2);
            System.out.println(size);
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 2]  
我们会发现，结果出错？因为我们定义的size经过每个结点都会+1，但是不能清0，所以我们调用这个方法时，一定要将size=0；

## 汇集思想求结点的个数 ##

我们发现每个都是左子树+右子树+头结点，我们可以递归求解

// 汇集思想求结点的个数
        public static int getSize2(TreeNode root) { 
            if (root == null) { 
                return 0;
            }
            int left = getSize2(root.left);
            int right = getSize2(root.right);
            return left + right + 1;
        }

测试

public static void main(String[] args) { 
            TreeNode root1 = buildTree.buildTree1();
            TreeNode root2 = buildTree.buildTree2();
    
            System.out.println(getSize2(root1));
            System.out.println(getSize2(root2));
        }

![在这里插入图片描述][20210326174243601.png]

## 遍历求叶子结点的个数 ##

我们可以采用遍历的思想求出结点个数，需要定义一个leftSize，当结点左右子树都为null时，记录节点个数  
当然我们调用的时候也需要将leafSize=0；

// 遍历求叶子结点的个数
        static int leafSize = 0;
    
        public static void getLeafSize1(TreeNode root) { 
            if (root == null) { 
                return;
            }
            if (root.left == null && root.right == null) { 
                leafSize++;
            }
            getLeafSize1(root.left);
            getLeafSize1(root.right);
        }

测试

//求解叶子结点个数
        public static void main(String[] args) { 
            TreeNode root1 = buildTree.buildTree1();
            TreeNode root2 = buildTree.buildTree2();
            getLeafSize1(root1);
            System.out.println(leafSize);
            leafSize = 0;
            getLeafSize1(root2);
            System.out.println(leafSize);
        }

![在这里插入图片描述][20210326180214227.png]

## 汇集思想求叶子结点的个数 ##

我们发现叶子结点是左子树 为 null 和 右子树 为 null ，我们可以递归求解

// 汇集思想求叶子结点的个数
        public static int getLeafSize2(TreeNode root) { 
            if (root == null) { 
                return 0;
            }
            if (root.left == null && root.right == null) { 
                return 1;
            }
            int left = getLeafSize2(root.left);
            int right = getLeafSize2(root.right);
            return left + right;
        }

测试：

//求解叶子结点个数
        public static void main(String[] args) { 
            TreeNode root1 = buildTree.buildTree1();
            TreeNode root2 = buildTree.buildTree2();
            System.out.println(getLeafSize2(root1));
            System.out.println(getLeafSize2(root2));
    }

![在这里插入图片描述][20210326180438501.png]

## 求第k层结点个数 ##

递归求解：

// 求第k层结点个数
        public static int getLeavelSize(TreeNode root, int k) { 
            if (root == null) { 
                return 0;
            }
            if (k == 1) { 
                return 1;
            }
            int left = getLeavelSize(root.left, k - 1);
            int right = getLeavelSize(root.right, k - 1);
            return left + right;
        }

测试：

//求解二叉树第k层有几个结点
        public static void main(String[] args) { 
            TreeNode root1 = buildTree.buildTree1();
            TreeNode root2 = buildTree.buildTree2();
    
            System.out.println(getLeavelSize(root1,2));
            System.out.println(getLeavelSize(root1,4));
            System.out.println(getLeavelSize(root2,1));
            System.out.println(getLeavelSize(root2,3));
            System.out.println(getLeavelSize(root2,4));
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 3]

## 求二叉树的高度 ##

左子树和右子树中较大的为二叉树高度：

// 求二叉树的高度
        public static int getHeight(TreeNode root) { 
            if (root == null) { 
                return 0;
            }
            int left = getHeight(root.left);
            int right = getHeight(root.right);
            return Integer.max(left, right) + 1;
        }

测试:

//二叉树高度
        public static void main(String[] args) { 
            TreeNode root1 = buildTree.buildTree1();
            TreeNode root2 = buildTree.buildTree2();
            System.out.println(getHeight(root1));
            System.out.println(getHeight(root2));
        }

![在这里插入图片描述][20210326185143944.png]

## 是否存在结点为e的结点 ##

//是否存在结点为e的结点
        public static boolean contains(TreeNode root, int e) { 
            if (root == null) { 
                return false;
            }
            if (root.val == e) { 
                return true;
            }
            if (contains(root.left, e)) { 
                return true;
            }
            return contains(root.right, e);
        }

//是否存在结点为e的结点
        public static void main(String[] args) { 
            TreeNode root1 = buildTree.buildTree1();
            TreeNode root2 = buildTree.buildTree2();
    
            System.out.println(contains(root1,'1'));
            System.out.println(contains(root1,'c'));
            System.out.println(contains(root1,'z'));
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 4]

## 是否存在结点为e的结点，返回其结点位置 ##

//是否存在结点为e的结点，返回其结点位置
        public static TreeNode nodeOf(TreeNode root, int e) { 
            if (root == null) { 
                return null;
            }
            if (root.val == e) { 
                return root;
            }
            TreeNode r = nodeOf(root.left, e);
            if (r != null) { 
                return r;
            }
            return nodeOf(root.right, e);
        }

//是否存在结点为e的结点，返回其结点位置
        public static void main(String[] args) { 
            TreeNode root1 = buildTree.buildTree1();
    
            System.out.println(nodeOf(root1,'1'));
            System.out.println(nodeOf(root1,'c'));
            System.out.println(nodeOf(root1,'e'));
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 5]

## 判断 node 在不在以 root 为根的树中，node 一定不是 null ##

public static boolean containsNode(TreeNode root, TreeNode node) { 
            if (root == null) { 
                return false;
            }
            if (root == node) { 
                return true;
            }
            boolean r = containsNode(root.left, node);
            if (r) { 
                return true;
            }
            return containsNode(root.right, node);
        }

// 判断 node 在不在以 root 为根的树中，node 一定不是 null
        public static void main(String[] args) { 
            TreeNode root1 = buildTree.buildTree1();
            TreeNode root2 = buildTree.buildTree2();
            TreeNode node1 = new TreeNode('a');
            System.out.println(containsNode(root1, root1));
            System.out.println(containsNode(root1, root2));
            System.out.println(containsNode(root1, node1));
            System.out.println(containsNode(root2, node1));
            System.out.println(containsNode(node1, node1));
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 6]

[Link 1]: https://blog.csdn.net/weixin_52142731/article/details/115220279
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]: /images/20221022/f4e0ba3130884f41941967a9e922266d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210326172048589.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210326173710210.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ==,size_16,color_FFFFFF,t_70
[20210326174243601.png]: https://img-blog.csdnimg.cn/20210326174243601.png
[20210326180214227.png]: https://img-blog.csdnimg.cn/20210326180214227.png
[20210326180438501.png]: https://img-blog.csdnimg.cn/20210326180438501.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2021032618493335.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ==,size_16,color_FFFFFF,t_70
[20210326185143944.png]: https://img-blog.csdnimg.cn/20210326185143944.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/202103261911255.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20210326191436528.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20210326192014237.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ==,size_16,color_FFFFFF,t_70