【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)

本文涉及的产品
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
简介: 【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)

前言

终于到了之前C语言没有讲过的数据结构了,那就是二叉树了,关于二叉树的学习难度确实比前面学习的数据结构都要难一点,所以我们这个关于二叉树的博客大概率是有好几篇的。如有哪里出现错误也欢迎指出唔。

二叉树的概念



Java 中的二叉树是一种基础的数据结构,它是由节点组成的树形结构,其中每个节点最多有两个子节点,通常称为左子节点和右子节点。二叉树的节点通常包含三个部分:节点的数据域、指向左子节点的指针和指向右子节点的指针。


我们通常把没有父节点(双亲节点)的节点叫做根节点,平常说的”这个根“,”它的根“中的根就是值根节点。

比如上面的”1“为整个树的根节点,也可以说”4“是 5和6的根因为其实4,5,6也可以说其组成了一棵树,组成的这棵树我们叫做子树。


二叉树的性质:

定义性:二叉树是节点的集合,其中每个节点最多有两个子节点,通常称为左子节点和右子节点。

层级性:二叉树的节点按照层次排列,根节点位于第一层,其子节点位于第二层,以此类推。

有序性:在二叉搜索树(Binary Search Tree, BST)中,每个节点的值都大于(或等于)其左子树中所有节点的值,并且小于(或等于)其右子树中所有节点的值。

递归性:二叉树可以递归地定义为:一个节点(包含数据域和两个指向子树的指针域)或者为空。

树的深度:二叉树的深度是根节点到最远叶子节点的最长路径上的边数。

节点的度:一个节点的度是指该节点拥有的子节点数量。在二叉树中,节点的度最大为2。

树的广度:二叉树的广度是指树的层数。

叶子节点:二叉树中没有子节点的节点称为叶子节点或外部节点。

内部节点:至少有一个子节点的节点称为内部节点。

树的高度:二叉树的高度是从根节点到任意叶子节点的最长路径上的边数。

子树:任何一个节点及其所有后代构成的二叉树称为该节点的子树。

兄弟节点:具有相同父节点的节点称为兄弟节点。

祖先节点:从根到该节点所经过的节点序列称为该节点的祖先。

后代节点:以某节点为根的子树中的任一节点都称为该节点的后代。

若规定根结点的层数为1,则一棵非空二叉树的第i层上最多有 (i>0)个结点

若规定只有根结点的二叉树的深度为1,则深度为K的二叉树的最大结点数是 (k>=0)

对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0=n2+1

这些性质是理解和操作二叉树的基础,它们在算法设计和数据结构分析中扮演着重要角色。


比较需要注意的是第17点性质。

三种特殊的二叉树
  1. 完全二叉树:如果一个二叉树的所有层都被完全填满,除了最后一层,并且最后一层的节点尽可能地集中在左侧,这样的二叉树称为完全二叉树。


也就是说在如果最后一层在左边没有填满,右边就突然有一个节点,那么他就不是完全二叉树。如下就不是一棵完全二叉树:

  1. 满二叉树:如果一个二叉树的所有节点都恰好有两个子节点,这样的二叉树称为满二叉树。


  1. 平衡二叉树:如果二叉树的任何两个叶子节点的深度之差不超过1,这样的二叉树称为平衡二叉树。AVL树和红黑树是两种常见的自平衡二叉搜索树。

这里叶子节点有”9“,”15“,”7“,他们之间的深度之差都不超过1,所以它是一棵平衡二叉树。


二叉树的数据储存---链式储存

孩子表示法

class Node<E>{
    E val;    // 数据域
    Node left;  //左孩子的引用,常常代表左孩子为根的整棵左子树
    Node right; //右孩子的引用,常常代表左孩子为根的整棵左子树
    
 
}


孩子双亲表示法

class Node<E>{
    E val;    // 数据域
    Node left;  //左孩子的引用,常常代表左孩子为根的整棵左子树
    Node right; //右孩子的引用,常常代表左孩子为根的整棵左子树
    Node parent; //当前节点的根节点
    }


注:Java 标准库中包含了一些与二叉树相关的类,但它们并不是直接的二叉树实现,而是以不同的数据结构形式存在。

二叉树主要的三种遍历

前提准备:因为我们现在还没学习真正的创建一颗二叉树,所以我们先用一种笨的方法创建一棵二叉树,代码如下:

class BinaryTree{
    public static class BTNode{
        BTNode left;
        BTNode right;
        int value;
        BTNode(int value){
            this.value = value;
        }
    }
    private BTNode root;
    public void 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);
        root = node1;
        node1.left = node2;
        node2.left = node3;
        node1.right = node4;
        node4.left = node5;
        node4.right = node6;
    }
 }   

这样我们写了一个createBinaryTree()方法,用来创建我们的一颗二叉树,这棵二叉树是这样的:

那么接下来我们就来学习三种二叉树主流遍历方法

前序遍历

学习二叉树遍历通常都是学习其中一种就可以举一反三,很容易就会其它两种遍历了。我们现在学习的这种遍历方法有递归方法和非递归方法。前序遍历就是先遍历根然后打印,在遍历左节点,在遍历右节点。口诀:”左右根“

前序遍历结果:1 2 3 4 5 6

递归前序遍历代码如下:
void preOrder(BTNode root){
    if(root==null){
        return;
    }
 
    System.out.print(root.value+" ");
    preOrder(root.left);
    preOrder(root.right);
 
 
 
}


代码很简单,但是对于没学到的小伙伴可能就懵逼了。那我们就用图来详细解析一下这个递归的遍历方法

这一张图是总的二叉树前序遍历图,画出了递归和回退过程,对于有一点递归基础的应该是可以看懂的。


然后上面这两张图就是根节点的整个左子树的递归过程,也就是节点”1“,”2“,”3“节点的递归回退过程,后面就是到右子树的递归过程,右子树的递归过程我就不画了,思维和左子树是一样的。


非递归前序遍历方法
public void preOrderNor(TreeNode root) {
 
        if(root == null) return;
 
        Stack<TreeNode> stack = new Stack<>();
 
        TreeNode cur = root;
 
 
 
        while (cur != null || !stack.isEmpty()) {
 
            while (cur != null) {
 
                stack.push(cur);
 
                System.out.print(cur.val + " ");
 
                cur = cur.left;
 
            }
 
            TreeNode top = stack.pop();
 
            cur = top.right;
 
        }
 
    }

解析:

非递归的遍历,首先我们遍历是需要返回前一个节点的,所以我们必须用到一个栈来进行储存我们的节点,然后我们首先创建一个循环只要cur不等于null和栈不为空就进入循环,cur不为空是因为首次进入的时候栈是空的,为了保证刚开始能进入循环就加了这么个判断条件。然后在镶嵌一个循环,这个循环就是遍历左树的每遍历一个就进栈一个为了储存节点好让后面返回节点遍历右树,然后因为这是前序遍历,所以我们要先打印在 cur = cur.left; 然后除了第一个循环就可以开始遍历右树了,这时我们就需要先出栈来返回上一个节点。

中序遍历

中序遍历和前序遍历递归思维都是一样的,就不再画图给大家解析了。中序遍历就是先遍历完左节点在回退到根进行打印,在遍历右节点,回退过程中在打印口诀:”左右根“


中序遍历结果:3 2 1 5 4 6

递归前中遍历代码如下:
void inOrder(BTNode root){
    if(root==null){
        return;
    }
 
 
    inOrder(root.left);
 
    System.out.print(root.value+" ");
 
 
    inOrder(root.right);
 
 
 
}


非递归中序遍历方法
public void inOrderNor(TreeNode root) {
 
        if(root == null) return;
 
        Stack<TreeNode> stack = new Stack<>();
 
        TreeNode cur = root;
 
 
 
        while (cur != null || !stack.isEmpty()) {
 
            while (cur != null) {
 
                stack.push(cur);
 
                cur = cur.left;
 
            }
 
            TreeNode top = stack.pop();
 
            System.out.print(top.val + " ");
 
 
 
            cur = top.right;
 
        }
 
    }



这个中序遍历的非递归方法还是和前序遍历思路一样,也就是打印的语句不一样罢了,就不再次解析了,理解了前序,中序的这个方法肯定是会理解的。重点放在后序遍历的非递归方法。


后序遍历

后续遍历就是遍历完当前节点的左右子树后,才会打印这个节点口诀:”左右根“

中序遍历和前序遍历递归思维都是一样的,就不再画图给大家解析了。

后序遍历结果:3 1 5 6 4 1


递归后序遍历代码如下:
void inOrder(BTNode root){
    if(root==null){
        return;
    }
 
 
    inOrder(root.left);
 
    System.out.print(root.value+" ");
 
 
    inOrder(root.right);
 
 
 
}
非递归后序遍历方法
public void postOrderNor(TreeNode root) {
 
        if(root == null) return;
 
        Stack<TreeNode> stack = new Stack<>();
 
        TreeNode cur = root;
 
        TreeNode prev = null;
 
        while (cur != null || !stack.isEmpty()) {
 
            while (cur != null) {
 
                stack.push(cur);
 
                cur = cur.left;
 
            }
 
            TreeNode top = stack.peek();
 
            if (top.right == null || top.right == prev) {
 
                System.out.print(top.val + " ");
 
                stack.pop();
 
                prev = top;
 
            } else {
 
                cur = top.right;
 
            }
 
        }
 
    }

为什么说后续遍历的非递归方法需要注意呢?


因为只要稍微不注意代码就会进入死循环。那么容易死循环的地方在哪里呢?


很多人可能会仿照前序和中序的代码在进入右树后面的语句加个判断左右是否为空,然后进行打印,但是却不会想到打印完后,回退到父节点时,此时的父节点已经在之前遍历过了。比如如果二叉树加了一个节点:

这个图如果失去了top.right == prev;这个语句就会死循环,它会在3和13不断死循环,所以我们就得在遍历右树时加上top.right == prev;这样就不会回退到3时,在进入13了。


这篇文章的二叉树就到这结束了,这一篇注要讲如何遍历二叉树。【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)

目录
打赏
0
1
1
0
19
分享
相关文章
Java线程池ExecutorService学习和使用
通过学习和使用Java中的 `ExecutorService`,可以显著提升并发编程的效率和代码的可维护性。合理配置线程池参数,结合实际应用场景,可以实现高效、可靠的并发处理。希望本文提供的示例和思路能够帮助开发者深入理解并应用 `ExecutorService`,实现更高效的并发程序。
34 10
【潜意识Java】深度分析黑马项目《苍穹外卖》在Java学习中的重要性
《苍穹外卖》项目对Java学习至关重要。它涵盖了用户管理、商品查询、订单处理等模块,涉及Spring Boot、MyBatis、Redis等技术栈。
91 4
【潜意识Java】Java基础教程:从零开始的学习之旅
本文介绍了 Java 编程语言的基础知识,涵盖从简介、程序结构到面向对象编程的核心概念。首先,Java 是一种高级、跨平台的面向对象语言,支持“一次编写,到处运行”。接着,文章详细讲解了 Java 程序的基本结构,包括包声明、导入语句、类声明和 main 方法。随后,深入探讨了基础语法,如数据类型、变量、控制结构、方法和数组。此外,还介绍了面向对象编程的关键概念,例如类与对象、继承和多态。最后,针对常见的编程错误提供了调试技巧,并总结了学习 Java 的重要性和方法。适合初学者逐步掌握 Java 编程。
53 1
|
1月前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
49 12
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
46 10
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
52 2
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
Java 集合江湖:底层数据结构的大揭秘!
小米是一位热爱技术分享的程序员,本文详细解析了Java面试中常见的List、Set、Map的区别。不仅介绍了它们的基本特性和实现类,还深入探讨了各自的使用场景和面试技巧,帮助读者更好地理解和应对相关问题。
63 5
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法,包括先序、中序、后序的递归与非递归遍历方法。通过编程实践,加深对二叉树结构的理解,学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
131 4

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等