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

入门数据结构JAVA DS——二叉树的介绍 (构建,性质,基本操作等) (1)

news 2024/11/13 11:16:55

前言

二叉树的概念和性质

二叉树的基本概念

二叉树的种类

二叉树的性质

二叉树的构建存储与遍历

存储

构建

遍历

前序遍历

后序遍历

中序遍历

层序遍历

二叉树的基本操作

获取树中结点个数

获取叶子结点个数

获取第K层结点的个数

获取二叉树的高度

检测值为value的元素是否存在

判断两棵树是否相同

需要笔者的代码请点击链接,都在github里了

MyJava/JavaDS2/src/tree at main · calljsh/MyJava (github.com)

前言

说实话,笔者在之前没有系统学习过数据结构之前,看到二叉树是有点害怕的,这也是我写下博客的原因之一,笔者想要告诉大家,它没有这么可怕,只要系统的学习过,有代码底子,是可以入门的,笔者将从如何构建二叉树,二叉树的性质,常见的操作等方面为主,以介绍一部分OJ题目为辅, 希望对你们有帮助

当然了,学习二叉树也需要你对于递归,搜索等算法思维有基础.

本文大致分成这个几个部分

1.二叉树的概念和性质

2.二叉树的构建存储与遍历

3.二叉树的基本操作

各位读者选择自己需要的部分查看即可

二叉树的概念和性质

二叉树（Binary Tree）是树形结构的一种特殊形式，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树是一种非常常用的数据结构，在计算机科学中被广泛应用于各种算法和数据存储方式。

二叉树的基本概念

根节点：二叉树的顶点称为根节点（Root Node），它没有父节点。
子节点：每个节点可以有两个子节点，分别是左子节点和右子节点。
叶子节点：没有任何子节点的节点称为叶子节点（Leaf Node）。
父节点：某个节点的上一级节点称为父节点。
兄弟节点：同一个父节点下的两个子节点互称兄弟节点。
深度：从根节点到当前节点的路径长度称为该节点的深度。
高度：从当前节点到叶子节点的最长路径长度称为该节点的高度。
层次：二叉树中节点所在的层，根节点为第1层，子节点为第2层，依次类推。

二叉树的种类

满二叉树：在满二叉树中，每一层的节点数都达到了最大值，即每个非叶子节点都有两个子节点。
完全二叉树：完全二叉树的每一层节点都是从左到右排列，只有最后一层的节点可以不满，但必须从左到右紧密排列。
平衡二叉树（AVL Tree）：一种高度平衡的二叉树，其左右子树的高度差不超过1。
二叉搜索树（Binary Search Tree, BST）：一种特殊的二叉树，满足左子树所有节点的值小于根节点，而右子树所有节点的值大于根节点。

二叉树的性质

二叉树有很多已经被研究出来的性质,笔者在此做一个小汇总

当然了,性质这种东西看看就好了,反正笔者是不能完全记住的

二叉树的构建存储与遍历

存储

存储有链式存储和顺序存储,本文介绍链式存储

首先我们要知道,二叉树也是一个一个结点穿起来的,对于一个结点来说,除了存储结点的值以外,也需要存储两个"孩子"的地址,也就是左子树地址和右边子树地址,如果用JAVA代码来写,就是这样写的

   static class BTNode{BTNode left;BTNode right;int value;BTNode(int value) {this.value = value;}}

可以看到,二叉树的存储和前面的链表并无本质区别,所以只要前面基础打得好,其实不难的.

构建

其实二叉树的构建也是一个可以细说的点,笔者大致把他分成这两类

1.直接手动构建顾名思义,就是自己动手把所有结点连接起来

2.告诉你遍历顺序,通过递归构建

第二类是有专门的OJ题目的,链接在下面

106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

10.黄金树 - 蓝桥云课 (lanqiao.cn)

这三题都是很典型的题目,笔者可以自己去写.

为了能介绍如何遍历,我们使用"最轮椅"的第一种方法,手动创建一颗二叉树

    private BTNode root;public BTNode createBinaryTree() {BTNode node1 = new BTNode(1);BTNode node2 = new BTNode(2);BTNode node3 = new BTNode(3);BTNode node4 = new BTNode(4);BTNode node5 = new BTNode(5);BTNode node6 = new BTNode(6);BTNode node7 = new BTNode(7);BTNode node8 = new BTNode(8);root = node1;node1.right=node2;node1.left=node3;node2.left=node4;node2.right=node8;node3.right=node5;return node1;}

画图能发现长成这样

一颗很普通的二叉树,不是满二叉树,也不是完全二叉树

遍历

我们通过这棵树讲遍历

前序遍历

前序遍历的顺序是：根节点 -> 左子树 -> 右子树。

步骤：

访问根节点。
前序遍历左子树。
前序遍历右子树。

我们采取递归的方法,先根,然后左子树,然后右子树

 public void preorder(BTNode root)// 前序遍历{if (root == null) {return;}System.out.print(root.value + " ");preorder(root.left);preorder(root.right);}

效果如下

1 3 5 2 4 8

后序遍历

后序遍历的顺序是：左子树 -> 右子树 -> 根节点。

步骤：

后序遍历左子树。
后序遍历右子树。
访问根节点。

代码如下

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

效果如下

5 3 4 8 2 1

中序遍历

中序遍历的顺序是：左子树 -> 根节点 -> 右子树。

步骤：

中序遍历左子树。
访问根节点。
中序遍历右子树。

代码如下

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

效果如下

3 5 1 4 2 8

对于刚刚入门二叉树的朋友,鄙人的建议是多画图,多调试,让你的大脑多跟着代码的逻辑跑一跑,就能看懂代码了

层序遍历

层序遍历（Level Order Traversal）和广度优先搜索（BFS, Breadth-First Search实际上是相似的概念，特别是在树的遍历中，层序遍历就是BFS的应用。

BFS怎么写可以看

经典bfs模板分享-长草以及类似模板题-扩散_bfs模版题-CSDN博客

填坑-bfs解决扩散.-CSDN博客

二叉树的层序就更赤裸裸了

102. 二叉树的层序遍历 - 力扣（LeetCode）

 public void levelOrder(BTNode root){if (root == null){return;  // 如果根节点为空，直接返回}Queue<BTNode> queue = new LinkedList<>();queue.offer(root);  // 将根节点加入队列while(!queue.isEmpty()){BTNode temp=queue.poll();System.out.print(temp.value+" ");if(temp.left!=null)queue.offer(temp.left);if(temp.right!=null)queue.offer(temp.right);}}

效果如下

1 3 2 5 4 8

二叉树的基本操作

笔者主要想介绍的是这么几个基本操作

部分操作,笔者会介绍两种写法,二者思路完全一致,只是代码风格不一样.

1. 获取树中节点的个数

2.获取叶子节点的个数

3.获取第 K 层节点的个数

4. 获取二叉树的高度

5.检测值为 value 的元素是否存在

6.判断两棵树是否相同

获取树中结点个数

获取树中的结点个数,只需要在遍历的基础上加上计数器即可,不管是前序后序中序层序.

代码如下

  public int treesize(BTNode root)// 节点个数{size1 = 0;dfs2(root);return size1;}private void dfs2(BTNode root) {if (root != null) {size1++;dfs2(root.left);dfs2(root.right);} else {return;}}

获取叶子结点个数

获取叶子结点个数,同样需要遍历我们的整棵树,但是我们需要判断条件了,如果一个结点既没有左子树也没有右子树,那么他就是一个叶子结点,

基于这个思路,我们给出如下代码

    private int sum;  // 用来存储叶子节点的数量public int leafsize(BTNode root) {sum = 0;  // 初始化sumdfs(root);  // 启动DFSreturn sum;  // 返回叶子节点的总数}private void dfs(BTNode node) {// 进入节点 nodeif (node == null) {return;}if (node.left == null && node.right == null) {// 如果是叶子节点，更新sumsum++;return;}// 递归处理左子树和右子树dfs(node.left);dfs(node.right);// 离开节点 node}

我大致阐述一下思路,如果你看不懂,说明你不适合学计算机或者你基础不好,需要多调试代码

进入搜索方法,首先判断这个结点是不是空,不是空,继续,判断是不是叶子结点, 是,就可以返回了,如果上述条件都不符合,就继续搜索,知道无法搜索为止(空或者是叶子结点)

也有更EZ的版本,就是递归,代码如下

        public int leafsize(BTNode root)// 叶子节点{if (root == null) {return 0;}if (root.left == null && root.right == null) {return 1;}return leafsize(root.left) + leafsize(root.right);}

二者的思路基本一致,只是风格不一样.

获取第K层结点的个数

代码如下

 public int getKLevelNodeCount(TreeNode root, int k) {// 如果节点为空，返回 0if (root == null) {return 0;}// 如果 k == 1，说明当前节点是第 k 层的节点if (k == 1) {return 1;}// 否则，继续递归查找左子树和右子树第 k-1 层的节点数量int leftCount = getKLevelNodeCount(root.left, k - 1);int rightCount = getKLevelNodeCount(root.right, k - 1);// 返回左右子树中第 k-1 层节点的数量之和return leftCount + rightCount;}

思路就是找到K-1层,进而算出第K层的数量,如果能看懂前面的,这个笔者相信你们也可以

获取二叉树的高度

获取高度,本质上还是遍历我们的树,只不过,我们需要一个值,去存储目前已知的最大高度而已

    public int max;public int getHeight(BTNode root) {if (root == null) {return 0;}max = 1;DFS(root, 1);return max;}private void DFS(BTNode root, int num) {if (root.left == null && root.right == null) {max = Math.max(num, max);return;}if (root.left != null) {int num1 = num + 1;DFS(root.left, num1);}if (root.right != null) {DFS(root.right, num + 1);}}

依旧是遍历树,然后,如果发现该结点已经是叶子结点,通过 max去存储最大高度,max默认为1,因为一颗树的最低高度就是1

检测值为value的元素是否存在

如果你还能看到这里,不用我说你也应该知道思路,还是遍历!!!核心问题就是,为了减少对于性能的消耗,一旦找到了,我们就应该终止方法.但这毕竟不是简单的循环,只靠一个break就可以了,因此,笔者又引入了一个变量,如果找到了,我们通过修改变量达到目的

以下是笔者觉得最容易理解的风格了

 BTNode btNode;int pd = 0;BTNode find(BTNode root, int val) {Dfs(root, val);if (pd == 1)return btNode;elsereturn null;}private void Dfs(BTNode root, int val){if (pd == 1 || root == null) {return;}if (root.value == val) {btNode = root;pd = 1;}Dfs(root.right, val);Dfs(root.left, val);}

可以看到,笔者用了变量pd来判断,肯定有更好的方法,但笔者觉得这个最好理解

判断两棵树是否相同

这个操作笔者觉得,很重要,学会了这个,你就可以判断一棵树是否含有某棵子树了,因此笔者列出来

思路与 检测值为value的元素是否存在 有异曲同工之妙

先给你们看看代码

    public int PD = 0; // 标志位，表示是否发现不相同public boolean ans = true; // 存储结果，默认是相同public boolean isSameTree(BTNode  p, BTNode  q) {dfs(p, q);return ans;}private void dfs(BTNode  p, BTNode  q) {if (PD == 1) {return; // 如果已经发现不同，直接返回}if (p == null && q == null) {return; // 如果两个节点都为空，继续递归}if (p == null || q == null || p.value != q.value) {PD = 1; // 如果只有一个节点为空或者值不同，标记为不同ans = false;return;}// 递归检查左右子树dfs(p.left, q.left);dfs(p.right, q.right);}

本质上就是不断的搜索,找有没有不同的点,找到了,立马改变判断变量,返回

那么,怎么算不同呢?如果都是空,那肯定是一样的,如果不是,就有三种情况,A空,B空,AB都不空,但是值不一样,我们就这样不断去找,找到了不同处就可以证明是不同的