本文撇开一些非常苦涩难以理解的概念来讲讲二叉树, 仅入门观看(或复习)....
首先, 我们来讲讲什么是树:
树是一种非线性的数据结构, 相对于线性的数据结构 (链表数组) 而言, 树的平均运行时间更短(往往与树相关的排序时间复杂度都不会高)
在现实生活中, 我们一般的树长这个样子的:
但是在编程的世界中, 我们一般把树倒过来看, 这样容易我们分析:
一般的树是有很多很多个分支的, 分支下又有很多很多个分支, 如果在程序中研究这个会非常麻烦因为本来树就是非线性的, 而我们计算机的内存是线性存储的, 太过复杂的话我们无法设计出来的
因此, 我们先来研究简单又经常用的 ---> 二叉树
1.1 树的一些概念
我就拿上面的图来进行画来讲解了:
二叉树的意思就是说: 每个节点不能多于有两个儿子, 上面的图就是一颗二叉树
一棵树至少会有一个节点(根节点)
树由节点组成, 每个节点的数据结构是这样的:
因此, 我们定义树的时候往往是 ->定义节点 ->节点连接起来就成了树, 而节点的定义就是: 一个数据两个指针(如果有节点就指向节点没有节点就指向 null)
1.2 静态创建二叉树
上面说了, 树是由若干个节点组成, 节点连接起来就成了树, 而节点由一个数据两个指针组成
因此, 创建树实际上就是创建节点, 然后连接节点
首先, 使用 Java 类定义节点:
- public class TreeNode {
- // 左节点(儿子)
- private TreeNode lefTreeNode;
- // 右节点(儿子)
- private TreeNode rightNode;
- // 数据
- private int value;
- }
下面我们就拿这个二叉树为例来构建吧:
为了方便构建, 我就给了它一个带参数的构造方法和 setget 方法了:
- public TreeNode(int value) {
- this.value = value;
- }
那么我们现在就创建了 5 个节点:
- public static void main(String[] args) {
- // 根节点 -->10
- TreeNode treeNode1 = new TreeNode(10);
- // 左孩子 -->9
- TreeNode treeNode2 = new TreeNode(9);
- // 右孩子 -->20
- TreeNode treeNode3 = new TreeNode(20);
- //20 的左孩子 -->15
- TreeNode treeNode4 = new TreeNode(15);
- //20 的右孩子 -->35
- TreeNode treeNode5 = new TreeNode(35)
- }
它们目前的状态是这样子的:
于是下面我们去把它连起来:
- // 根节点的左右孩子
- treeNode1.setLefTreeNode(treeNode2);
- treeNode1.setRightNode(treeNode3);
- //20 节点的左右孩子
- treeNode3.setLefTreeNode(treeNode4);
- treeNode3.setRightNode(treeNode5);
连接完之后, 那么我们的树就创建完成了
1.3 遍历二叉树
上面说我们的树创建完成了, 那怎么证明呢?? 我们如果可以像数组一样遍历它(看它的数据), 那就说明它创建完成了~
值得说明的是: 二叉树遍历有三种方式
中序遍历
先访问根节点, 然后访问左节点, 最后访问右节点 (根 -> 左 ->右)
先序遍历
先访问左节点, 然后访问根节点, 最后访问右节点 (左 -> 根 ->右)
后序遍历
先访问左节点, 然后访问右节点, 最后访问根节点 (左 -> 右 ->根)
以上面的二叉树为例:
如果是中序遍历: 10->9->20->15->35
如果是先序遍历: 9->10->15->20->35
可能需要解释地方: 访问完 10 节点过后, 去找的是 20 节点, 但 20 下还有子节点, 因此先访问的是 20 的左儿子 15 节点由于 15 节点没有儿子了所以就返回 20 节点, 访问 20 节点最后访问 35 节点
如果是后序遍历: 9->15->35->20->15
可能需要解释地方: 先访问 9 节点, 随后应该访问的是 20 节点, 但 20 下还有子节点, 因此先访问的是 20 的左儿子 15 节点由于 15 节点没有儿子了所以就去访问 35 节点, 由于 35 节点也没有儿子了, 所以返回 20 节点, 最终返回 10 节点
一句话总结: 中序 (根 -> 左 ->右), 先序 (左 -> 根 ->右), 后序 (左 -> 右 ->根)如果访问有孩子的节点, 先处理孩子的, 随后返回
无论先中后遍历, 每个节点的遍历如果访问有孩子的节点, 先处理孩子的(逻辑是一样的)
因此我们很容易想到递归
递归的出口就是: 当没有子节点了, 就返回
因此, 我们可以写出这样的先序遍历代码:
- /**
- * 中序遍历
- * @param rootTreeNode 根节点
- */
- public static void inTraverseBTree(TreeNode rootTreeNode) {
- if (rootTreeNode != null) {
- // 访问根节点
- System.out.println(rootTreeNode.getValue());
- // 访问左节点
- preTraverseBTree(rootTreeNode.getLefTreeNode());
- // 访问右节点
- preTraverseBTree(rootTreeNode.getRightNode());
- }
- }
结果跟我们刚才说的是一样的:
我们再用先序遍历调用一遍吧:
- /**
- * 中序遍历
- * @param rootTreeNode 根节点
- */
- public static void preTraverseBTree(TreeNode rootTreeNode) {
- if (rootTreeNode != null) {
- // 访问左节点
- preTraverseBTree(rootTreeNode.getLefTreeNode());
- // 访问根节点
- System.out.println(rootTreeNode.getValue());
- // 访问右节点
- preTraverseBTree(rootTreeNode.getRightNode());
- }
- }
结果跟我们刚才说的是一样的:
有意思的是: 通过先序和中序或者中序和后序我们可以还原出原始的二叉树, 但是通过先序和后续是无法还原出原始的二叉树的
也就是说: 通过中序和先序或者中序和后序我们就可以确定一颗二叉树了!
二动态创建二叉树
上面我们是手动创建二叉树的, 一般地: 都是给出一个数组给你, 让你将数组变成一个二叉树, 此时就需要我们动态创建二叉树了
二叉树中还有一种特殊的二叉树: 二叉查找树(binary search tree)
定义: 当前根节点的左边全部比根节点小, 当前根节点的右边全部比根节点大
明眼人可以看出, 这对我们来找一个数是非常方便快捷的
往往我们动态创建二叉树都是创建二叉查找树
2.1 动态创建二叉树体验
假设我们有一个数组:
int[] arrays = {3, 2, 1, 4, 5};
那么创建二叉树的步骤是这样的:
首先将 3 作为根节点
随后 2 进来了, 我们跟 3 做比较, 比 3 小, 那么放在 3 的左边
随后 1 进来了, 我们跟 3 做比较, 比 3 小, 那么放在 3 的左边, 此时 3 的左边有 2 了, 因此跟 2 比, 比 2 小, 放在 2 的左边
随后 4 进来了, 我们跟 3 做比较, 比 3 大, 那么放在 3 的右边
随后 5 进来了, 我们跟 3 做比较, 比 3 大, 那么放在 3 的右边, 此时 3 的右边有 4 了, 因此跟 4 比, 比 4 大, 放在 4 的右边
那么我们的二叉查找树就建立成功了, 无论任何一颗子树, 左边都比根要小, 右边比根要大
2.2 代码实现
我们的代码实现也很简单, 如果比当前根节点要小, 那么放到当前根节点左边, 如果比当前根节点要大, 那么放到当前根节点右边
因为是动态创建的, 因此我们得用一个类来表示根节点
- public class TreeRoot {
- private TreeNode treeRoot;
- public TreeNode getTreeRoot() {
- return treeRoot;
- }
- public void setTreeRoot(TreeNode treeRoot) {
- this.treeRoot = treeRoot;
- }
- }
比较与根谁大, 大的往右边, 小的往左边:
- /**
- * 动态创建二叉查找树
- *
- * @param treeRoot 根节点
- * @param value 节点的值
- */
- public static void createTree(TreeRoot treeRoot, int value) {
- // 如果树根为空(第一次访问), 将第一个值作为根节点
- if (treeRoot.getTreeRoot() == null) {
- TreeNode treeNode = new TreeNode(value);
- treeRoot.setTreeRoot(treeNode);
- } else {
- // 当前树根
- TreeNode tempRoot = treeRoot.getTreeRoot();
- while (tempRoot != null) {
- // 当前值大于根值, 往右边走
- if (value> tempRoot.getValue()) {
- // 右边没有树根, 那就直接插入
- if (tempRoot.getRightNode() == null) {
- tempRoot.setRightNode(new TreeNode(value));
- return ;
- } else {
- // 如果右边有树根, 到右边的树根去
- tempRoot = tempRoot.getRightNode();
- }
- } else {
- // 左没有树根, 那就直接插入
- if (tempRoot.getLefTreeNode() == null) {
- tempRoot.setLefTreeNode(new TreeNode(value));
- return;
- } else {
- // 如果左有树根, 到左边的树根去
- tempRoot = tempRoot.getLefTreeNode();
- }
- }
- }
- }
- }
测试代码:
- int[] arrays = {2, 3, 1, 4, 5};
- // 动态创建树
- TreeRoot root = new TreeRoot();
- for (int value : arrays) {
- createTree(root, value);
- }
- // 先序遍历树
- preTraverseBTree(root.getTreeRoot());
- System.out.println("--------------- 公众号: Java3y");
- // 中序遍历树
- inTraverseBTree(root.getTreeRoot());
- System.out.println("--------------- 公众号: Java3y");
三查询二叉查找树相关
3.1 查询树的深度
查询树的深度我们可以这样想: 左边的子树和右边的字数比, 谁大就返回谁, 那么再接上根节点 + 1 就可以了
- public static int getHeight(TreeNode treeNode) {
- if (treeNode == null) {
- return 0;
- } else {
- // 左边的子树深度
- int left = getHeight(treeNode.getLefTreeNode());
- // 右边的子树深度
- int right = getHeight(treeNode.getRightNode());
- int max = left;
- if (right> max) {
- max = right;
- }
- return max + 1;
- }
- }
3.1 查询树的最大值
从上面先序遍历二叉查找树的时候, 细心的同学可能会发现: 先序遍历二叉查找树得到的结果是排好顺序的~
那么, 如果我们的二叉树不是二叉查找树, 我们要怎么查询他的最大值呢?
可以这样:
左边找最大值 ->递归
右边找最大值 ->递归
- /**
- * 找出树的最大值
- *
- * @param rootTreeNode
- */
- public static int getMax(TreeNode rootTreeNode) {
- if (rootTreeNode == null) {
- return -1;
- } else {
- // 找出左边的最大值
- int left = getMax(rootTreeNode.getLefTreeNode());
- // 找出右边的最大值
- int right = getMax(rootTreeNode.getRightNode());
- // 与当前根节点比较
- int currentRootValue = rootTreeNode.getValue();
- // 假设左边的最大
- int max = left;
- if (right> max) {
- max = right;
- }
- if (currentRootValue> max) {
- max = currentRootValue;
- }
- return max ;
- }
- }
四最后
无论是在遍历树查找深度查找最大值都用到了递归, 递归在非线性的数据结构中是用得非常多的...
树的应用也非常广泛, 此篇简单地说明了树的数据结构, 高级的东西我也没弄懂, 可能以后用到的时候会继续深入...
来源: https://www.cnblogs.com/Java3y/p/8636522.html