当前位置: 首页 > article >正文

Java Collection(3)——BinaryTree(二叉树)

前言

1.掌握树的基本概念
2.掌握二叉树概念及特性
3.掌握二叉树的基本操作
后面的优先级队列(大根堆,小根堆)也是基于二叉树实现的,所以理解好二叉树至关重要

1.树形结构

1.1描述

树是一种非线性的数据结构,它是由不为零个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上叶朝下

1.2特点

  1.  一棵树只有一个根节点,并且根节点没有前驱节点
    
  2.  除根结点外,其余节点分成n个(n>0)互不相交的集合,每个集合又是一颗与树类似的子树。每颗子树有且只有一个前驱节点,任意个后继节点
    
  3.  树是递归定义的
    

在这里插入图片描述

1.3概念(重要)

  1.  节点的度:一个节点拥有的子节点的数量就是该节点的度;例如A节点的度为2
    
  2.  树的度:该树种所有节点的度取**最大值**
    
  3.  叶子节点/终端节点:度为零的节点
    
  4.  双亲结点/父节点:一个节点拥有子节点,那么该节点就是其子节点的父节点
    
  5.  子节点:一个节点拥有父节点,那么该节点就是其父节点的子节点
    
  6.  根节点:没有父节点的节点
    
  7.  结点的层次:从根开始定义起,根为第1层,根的子结点为第2层,以此类推
    
  8.  树的高度/深度:该树中节点的层次取最大值
    

剩下的几个概念很少提及,知道即可
非终端结点或分支结点:度不为0的结点
兄弟结点:具有相同父结点的结点互称为兄弟结点
堂兄弟结点:双亲在同一层的结点互为堂兄弟
结点的祖先:从根到该结点所经分支上的所有结点;例如:D节点的祖先有A和B
子孙:以某结点为根的子树中任一结点都称为该结点的子孙;例如:以B为根节点,它的子孙有D和E

1.4表示方式

表示方式知道一个最常用的就好了:孩子兄弟表示法
在这里插入图片描述

1.5树的应用

文件系统管理(目录和文件)
在这里插入图片描述
将电脑的所有文件看成一棵树,这里的C盘就相当于根节点,C盘下有四个子节点(文件夹/目录),每个目录下又有n个子节点

2.二叉树

2.1概念:

树的度<=2的树形结构
在这里插入图片描述

2.2特点

由上图可知

  1.  二叉树不存在度大于2的结点
    
  2.  二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树
    

二叉树有以下几种情况
在这里插入图片描述

2.3两种特殊的二叉树

  1.  满二叉树: 一棵二叉树,如果每层的结点数都达到最大值,则这棵二叉树就是满二叉树。也就是说,如果一棵二叉树的层数为K,且结点总数是2^k - 1 ,则它就是满二叉树
    
  2.  完全二叉树: 对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树.
    

在这里插入图片描述

2.4二叉树的性质

  1. 若规定根结点的层数为1,则一棵非空二叉树的第i层上最多有 2^(i - 1)(i>0)个结点
  2. 若规定根结点的层数为1,则一棵深度为k非空二叉树的总结点数为(2^k) - 1
  3. 对任何一棵二叉树, 如果其**叶结点**个数为 n0, **度为2的非叶结点**个数为 n2,则有**n0=n2+1**
    
  4. 具有n个结点完全二叉树的深度k=log₂(n)向上取整

2.5完全二叉树的节点组成**(我自己总结的规律)

设总结点数N,度为1的节点数n1,度为2的节点数n2,度为1的节点数n0

  1.  完全二叉树中度为1的节点要么有一个,要么没有
    
  2.  当总结点数目为奇数时,没有度为1的节点,满足关系式N=n2+n0,且n2=n0-1;当总结点数为偶数时,有一个度为1的节点,满足关系式N=n2+n0+n1,且n2=n0-1
    

2.5二叉树的存储方式

二叉树的存储结构分为:顺序存储类似于链表的链式存储
下篇博文会在完全二叉树的基础上实现优先级队列/堆(顺序存储);本文模拟实现二叉树/(下篇博文的二叉搜索树)用类似链表的方式,非完全二叉树使用顺序存储会浪费空间。
二叉树的链式存储是通过一个一个的节点引用起来的,常见的表示方式有二叉和三叉表示方式

//二叉表示法
    public static class BTNode {
        BTNode left;//左孩子的引用
        BTNode right;//右孩子的引用
        int val;//数据域

        public BTNode(int val) {
            this.val = val;
        }
    }
//三叉表示法
    public static class BTNode {
        BTNode left;//左孩子的引用
        BTNode right;//右孩子的引用
        BTNode parent;//当前节点的根节点/父节点
        int val;//数据域

        public BTNode(int val) {
            this.val = val;
        }
    }

2.6二叉树的基本操作

2.6.1前置说明

学习二叉树的基本操作之前,首先得创建一颗二叉树,由于大家对于二叉树还不够了解,所以我先手动创建一颗二叉树,等熟悉二叉树的基本操作后再来研究二叉树真正的创建方式

public BTNode getRoot() {
        return root;
    }

    //二叉表示法
    public static class BTNode {
        BTNode left;//左孩子的引用
        BTNode right;//右孩子的引用
        int val;//数据域

        public BTNode(int val) {
            this.val = val;
        }
    }
    private BTNode root;
    //手动创建二叉树
    public void createBinaryTree(){
        BTNode btNode1 = new BTNode(1);
        BTNode btNode2 = new BTNode(2);
        BTNode btNode3 = new BTNode(3);
        BTNode btNode4 = new BTNode(4);
        BTNode btNode5 = new BTNode(5);
        BTNode btNode6 = new BTNode(6);
        BTNode btNode7 = new BTNode(7);
        BTNode btNode8 = new BTNode(8);
        btNode1.left = btNode2;
        btNode2.left = btNode4;
        btNode2.right = btNode5;
        btNode1.right = btNode3;
        btNode3.left = btNode6;
        btNode3.right = btNode7;
        btNode4.left = btNode8;
        root = btNode1;
    }

在这里插入图片描述

注意:上述代码并不是创建二叉树的方式,真正创建二叉树方式下篇博文讲到二叉搜索树再介绍

2.6.2二叉树的遍历

学习二叉树结构,最简单的方式就是遍历。所谓遍历,就是沿着某条搜索路线,对树中的每一个节点做一次且仅做一次访问操作,访问操作依赖于实际的应用场景(打印节点,节点+1)
对于二叉树来说,常用的遍历方式有四种(前序遍历,中序遍历,后序遍历,层序遍历),这里先介绍前三种

  1.  前序遍历(Preorder Traversal):访问根节点——>根的左子树——>根的右子树
    
  2.  中序遍历(Inorder Traversal):根的左子树——>根节点——>根的右子树
    
  3.  后序遍历(Postorder Traversal):根的左子树——>根的右子树——>根节点
    

这图是前序遍历的路径
在这里插入图片描述
以这张图片的二叉树为准,三种遍历方式的访问顺序如下
前序遍历:1->2->3->4->5->6
中序遍历:3->2->1->5->4->6
后序遍历:3->2->5->6->4->1

//前序遍历
    public void preOrder(BTNode root){
        if (root == null) return;
        //打印当前节点
        System.out.print(root.val+" ");
        //遍历左树
        preOrder(root.left);
        //遍历右树
        preOrder(root.right);
    }
    //中序遍历
    public void inOrder(BTNode root){
        if (root == null) return;
        //遍历左树
        inOrder(root.left);
        //打印当前节点
        System.out.print(root.val+" ");
        //遍历右树
        inOrder(root.right);
    }
    //后序遍历
    public void postOrder(BTNode root){
        if (root == null) return;
        //遍历左树
        postOrder(root.left);
        //遍历右树
        postOrder(root.right);
        //打印当前节点
        System.out.print(root.val+" ");
    }

2.6.3二叉树的基本操作

1.获取树中节点的个数

public int size(BTNode root){
        if (root == null) return 0;
        return (size(root.left) + size(root.right) + 1);
    }

2.获取叶子节点的个数

public int getLeafNodeCount(BTNode root){
        if (root == null) return 0;
        if( root.left == null && root.right == null) return  1;
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }

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

public int getKLevelNodeCount(BTNode root,int k){
        if (root == null) return 0;
        if (k == 1) return 1;
        return getKLevelNodeCount(root.left,k - 1) + getKLevelNodeCount(root.right,k - 1);
    }

4.获取二叉树的高度

public int getHeight(BTNode root){
        if (root == null) return 0;
        int countLeft = getHeight(root.left);
        int countRight = getHeight(root.right);
        return (countLeft >= countRight ? countLeft + 1 : countRight + 1);
    }

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

public Boolean findValue(BTNode root, int val){
        if (root == null) return false;
        if (root.val == val) return true;
        if(findValue(root.left,val)) return true;
        if(findValue(root.right,val)) return true;
        return false;
    }

6.层序遍历初阶

public void levelOrder(BTNode root){//两种
        if (root == null) return;
        Queue<BTNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            BTNode cur = queue.poll();
            System.out.print(cur.val+" ");
            if (cur.left != null){
                queue.offer(cur.left);
            }
            if (cur.right != null){
                queue.offer(cur.right);
            }
        }
    }

7.层序遍历进阶
在这里插入图片描述

public List<List<BTNode>> levelOrder2(BTNode root){//两种
        List<List<BTNode>> ret = new ArrayList<>();
        if (root == null) return ret;
        Queue<BTNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            List<BTNode> temp = new ArrayList<>();
            while (size != 0) {
                BTNode cur = queue.poll();
                temp.add(cur);
                size--;
                if (cur != null && cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur != null && cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            ret.add(temp);
        }
        return ret;
    }

8.判断完全二叉树

public Boolean isCompleteTree (BTNode root){
        if (root == null) return true;
        Queue<BTNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            BTNode cur = queue.poll();
            if (cur != null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        while (!queue.isEmpty()){
            BTNode cur = queue.poll();
            if (cur != null) return false;
        }
        return true;
    }

三.小结

至此,二叉树的基本操作已经介绍完毕了,下篇博文会在二叉树的基础上延伸出其他的结构,例如:二叉搜索树,优先级队列


http://www.kler.cn/a/586785.html

相关文章:

  • std::merge和std::inplace_merge对比分析
  • 谷歌云服务器:服务器怎么安装???
  • 车载Android音频系统 AudioService
  • 京瓷初期的按职能划分的组织
  • PHP语言的开源贡献
  • python函数式编程
  • 003_快乐数
  • 软件测试之单元测试unittest库使用、参数化、unittestteport
  • vivado ooc与global区别
  • 观成科技:​加密C2框架Platypus流量分析
  • DeepSeek-R1 面试 -—— GRPO
  • Spark 中explode用法
  • Android Dagger 2 框架的注解模块源码分析(一)
  • 【Linux】进程(1)进程概念和进程状态
  • 网络运维学习笔记(DeepSeek优化版) 016 HCIA-Datacom综合实验01
  • Go桌面端口开发方案
  • 操作系统-八股
  • Qt运行xxx.so can not open shared object file
  • C语言学习笔记:变量作用域、数组与字符串处理
  • 网页制作13-Javascipt时间特效の显示动态时间