• 【数据结构】二叉树


    💐1.树形结构

    💐1.1 概念(了解)

    hello 大家好,今天将讲解一种新的数据结构,这也是所有数据结构中最难的一个——树形数据结构

    在生活中,不管你是城里人儿, 还是村儿里人,相信大家都见过树,在树上面可以看到许多的分支,而一个小分支又衍生出了许多的更小的分支,最后直到开花结果,而接下来要讲的树形的数据结构也是这样的;
    在这里插入图片描述

    树:是一种非线性的数据结构,由n个有限的节点组成的一个具有层次关系(因为他们是一层一层的)的集合,为什么要把这一种数据结构叫做呢?因为阿,这种结构看起来像是一颗根朝上,叶子朝下的倒挂树;就像下面这样
    在这里插入图片描述

    1.在树中,有一个特殊的节点,称为根节点,根节点的上面不会再有节点;

    2.从根节点衍生出了m (m>0) 个子节点,而每一个子节点也都是一个集合,其中每一个子节点又作为一个根节点衍生出了m个子节点,也称为一颗子树,每棵子树的根节点上面只有一个节点,下面可以有多个或者0个子节点;

    3.树与非树的区别

    1.子树之间不能相交,每棵子树都是独立存在的

    2.每棵子树只能由一个父节点

    在这里插入图片描述

    3.一棵有n个节点的树有n-1条边;

    在这里插入图片描述

    💐1.2 概念(重点)

    在这里插入图片描述

    节点的度:一个节点含有子树的个数,如 B 的度为2,E 的度为1, F 的度为0;

    树的度:一棵树中,所有节点的度的最大值,如图:B 和 D 节点的度最大,因此树的度为2;

    叶子节点或终端节点:度为0的节点称为叶子节点,如图:J , K,L,M;

    双亲节点或父节点:若一个节点含有子节点,则该节点称为子节点的父节点或双亲节点;

    孩子节点或子节点:如果一个节点含有的子树,则子树的根节点称为该节点的子节点,如图 E 是 B的子节点, J 是E的子节点;

    根节点:一棵树中,没有父节点的节点称为根节点,如 A

    节点的层次:从根节点开始,根为第一层,根的子节点为第二层,以此类推;

    树的高度和深度:树中节点的最大层次;如上图,树的高度或深度为4;

    以上的概念需要重点理解;

    以下的概念了解即可;

    兄弟节点:具有相同父节点的节点称为兄弟节点,如图:E 和 F 就是兄的节点;

    堂兄弟节点:父节点在同一层的节点称为堂兄弟节点;如图:E 和 G

    子孙:以某节点为根的子树中,任意一个节点都称为该节点的子孙;如图 E 、F、J 是B的子孙;

    💐树的应用

    但是光说这些树的结构是非常抽象的,这些树在具体都在哪些方面用到了呢?下面举一个常见的例子:

    在电脑中的文件夹管理就是一种树的结构,比如在一个文件夹中,有m个文件夹,而在这m个文件夹中,又有许多个文件夹,直到最后的具体文件;

    然而,在树形结构中,又分为以下几种树:**二叉树、二叉搜索树、字典树、B树、B+树、val树、红黑树等;**接下来我会针对二叉树进行一个详细的讲解;
    在这里插入图片描述

    💐2.二叉树(重点)

    上面介绍过了树的结构,那么什么又是二叉树呢?就像下面这样:

    在这里插入图片描述
    在这里插入图片描述

    从上图可以看出:

    1.一个节点下面只能有一个或两个节点或者没有节点(度不能大于2);

    2.二叉树的子树有左右之分,次序不能弄颠倒,它可以有左右子树,或者只有左子树,或者只有右子树,或者是空树都可以,但是就是不能出现第三棵树;

    大自然的奇观:
    在这里插入图片描述

    💐2.1 两种特殊的二叉树

    满二叉树:对于每一层的节点,每个节点都有左右子节点或者都没有左右子节点,也就是每一层的节点数量都达到了最大值,比如第三层的节点数量最多只能有4个;如果一个二叉树的层数为K,则二叉树节点的总数为:
    2 k − 1 2^k-1 2k1
    在下图中,二叉树的层数为4层,总节点数就是15;

    在这里插入图片描述

    完全二叉树 :完全二叉树是由满二叉树引申出来了,假设有n个节点的二叉树,并且给二叉树的每个节点都编写一个下标,每一个节点都是紧挨着放置的,在两个节点之间不会有空位置,这样的二叉树称为完全二叉树,与满二叉树相比,完全二叉树最后一层的节点数量不用达到最大值;所以满二叉树也是一种特殊的完全二叉树;

    在这里插入图片描述

    💐2.2 二叉树的性质

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

    2.若规定根节点的二叉树的深度为1, 则深度为k的二叉树的最大的节点数是 (2^k) -1(k >=0)

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

    4.具有n个节点的完全二叉树的深度k 为log2 (n + 1) 向上取整

    在这里插入图片描述

    5.对于一个具有n个节点的完全二叉树,如果按照从上到下,从左到右的顺序给每个节点进行编号,对于序号为i的节点有以下两种种性质:

    性质1 :若 i > 0 , 求父节点:(i - 1 ) / 2;

    性质2 : 若 2i + 1 < n, 左孩子序号为: 2i + 1; 若 2i + 2 < n, 右孩子序号:2i + 2;

    💐2.3 二叉树的存储方式

    二叉树的存储方式分为链式存储顺序存储,本篇文章主要讲解链式存储,至于顺序存储会在优先队列中讲解,关于链式存储,它的存储方式最常用的有孩子表示法孩子双亲表示法,下面将讲解孩子表示法,孩子双亲表示法将在平衡树中讲解;

    首先,一棵二叉树是由n个节点组成的,而每一个节点中也是存储了一些数据,至于都是哪些数据呢?我们回忆一下链表,链表它不是顺序存储模式,链表中的每个节点除了存储数据以外,还存储了一个地址,为了能够根据这个地址找到下一个节点,同理,二叉树也是一样的,只不过节点里面会存储两个地址,一个是左子节点,一个是右子节点,那么下面结合这张图为大家介绍孩子表示法:

    在这里插入图片描述

        //孩子表示法
       class TreeNode{
           private int val;//数据域
           TreeNode left;//左孩子引用,代表以左孩子节点为根的左子树
           TreeNode right;//右孩子引用,代表以右孩子节点为根的右子树
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
        //孩子双亲表示法
       class TreeNode{
           private int val;//数据域
           TreeNode left;//左孩子引用,代表以左孩子节点为根的左子树
           TreeNode right;//右孩子引用,代表以右孩子节点为根的右子树
            TreeNode parent; //当前节点的根节点
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    💐二叉树的遍历方式

    1.前中后序遍历

    如果想要玩转二叉树,其实就是在玩二叉树的遍历,包括leetcode上的题,都是在遍历的基础上增加了一些条件,所以在二叉树的遍历这里,我们更因该熟读于心,首先,遍历的意思就是一条路走到黑,而对于遍历二叉树中每一个节点来讲,按照某种遍历方式一直走,走到不能再走了,然后再掉头返回;而二叉树的遍历方式也有三种:

    前序遍历: 先访问根节点 –> 根的左子树 –> 根的右子树

    中序遍历: 先访问左子树 –> 根节点 –> 根的右子树

    后序遍历: 先访问左子树 –> 右子树 –> 根

    以下图的前序遍历为例:

    在这里插入图片描述

    中序遍历结果:A B D G H E C F I

    中序遍历结果:G D H B E A F I C

    后序遍历结果:G H D E B I F C A

    前 中 后 序遍历过程中,经过每一个节点的路线都是一样的,只不过访问每一个节点的时机不一样

    2.层序遍历

    层序遍历就是从第一层的根节点开始访问, 然后再从第二层的由左至右进行遍历,然后再第三层由左至右进行遍历,依次类推,自上而下,自左至右进行遍历

    在这里插入图片描述

    💐3.二叉树的基本操作

    public class BinaryTree {
        //孩子表示法
       static class TreeNode{
            public char val;//数据域
           TreeNode left;//左孩子引用,代表以左孩子节点为根的左子树
           TreeNode right;//右孩子引用,代表以右孩子节点为根的右子树
            public TreeNode(char val) {
                this.val = val;
            }
        }
    
       //使用穷举的方式创建二叉树
        public TreeNode createTree() {
            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;
            D.left = H;
            return A;
        }
    
       //前序遍历
        public void preOrder(TreeNode root) {
            if(root == null) return;
            System.out.print(root.val+" ");
            preOrder(root.left);
            preOrder(root.right);
        }
    
        //中序遍历
        public void inorder(TreeNode root) {
           if(root == null) return;
           inorder(root.left);
            System.out.print(root.val + " ");
            inorder(root.right);
        }
    
        //后序遍历
        public void postOrder(TreeNode root) {
            if(root == null) return;
           postOrder(root.left);
           postOrder(root.right);
            System.out.print(root.val + " ");
        }
    
        // 获取树中节点的个数
        private int size = 0;
       //方法一:定义全局变量
        public int size(TreeNode root) {
           if(root == null) return 0;
           size++;
           size(root.left);
           size(root.right);
           return size;
        }
        //方法二:递归
        public int size1(TreeNode root) {
            if(root == null) return 0;
            int left = size1(root.left);
            int right = size1(root.right);
            return left+right+1;
        }
        // 获取叶子节点的个数
        public int getLeafNodeCount(TreeNode root) {
            if(root == null) return 0;
            if(root.left == null && root.right == null) {
                return 1;
            }
            int left = getLeafNodeCount(root.left);
            int right = getLeafNodeCount(root.right);
           return left+right;
        }
        //获取叶子节点
        public void getLeafNode(TreeNode root, List<Character> list) {
            //List l = new ArrayList<>();
            if(root == null) {
                return;
            }
            if(root.left == null && root.right == null) {
                list.add(root.val);
            }
            getLeafNode(root.left, list);
            getLeafNode(root.right, list);
        }
    // 获取第K层节点的个数
        public int getKLevelNodeCount(TreeNode root,int k) {
            if(root == null) return 0;
            if(k == 1) {
                return 1;
            }
            int left = getKLevelNodeCount(root.left, k-1);
            int right = getKLevelNodeCount(root.right, k-1);
            return left+right;
        }
        //获取第k层节点
        public void getKLevelNode(TreeNode root, int k, List<Character> list) {
            if(root == null) return;
            if(k == 1) {
                list.add(root.val);
            }
            getKLevelNode(root.left, k-1, list);
            getKLevelNode(root.right, k-1, list);
        }
        // 获取二叉树的高度
        int getHeight(TreeNode root) {
            if(root == null) return 0;
            int left = getHeight(root.left);
            int right = getHeight(root.right);
           return Math.max(left, right)+1;
        }
        // 检测值为value的元素是否存在
        TreeNode find(TreeNode root, char val) {
            if(root == null) {
                return null;
            }
            //找到val值直接返回
            if(root.val == val) {
                return root;
            }
            TreeNode left = find(root.left, val);
            //进行剪枝,如果找到了下面就不用再递归右子树
            if(left != null) {
                return left;
            }
            TreeNode right = find(root.right, val);
            if(right != null) {
                return right;
            }
           return null;
        }
        //层序遍历
        public void levelOrder(TreeNode root) {
            Deque<TreeNode> deque = new ArrayDeque<>();
            deque.offer(root);
            while(!deque.isEmpty()) {
                //计算每一层节点的数量
                int size = deque.size();
                //输出每一层的节点
                for(int i = 0; i<size; i++) {
                    TreeNode cur = deque.poll();
                    if(cur == null) {
                        continue;
                    }
                    if(cur.left != null) {
                        deque.offer(cur.left);
                    }
                    if(cur.right != null) {
                        deque.offer(cur.right);
                    }
                    System.out.print(cur.val+" ");
                }
                System.out.println();
            }
        }
        // 判断一棵树是不是完全二叉树
        boolean isCompleteTree(TreeNode root) {
            Queue<TreeNode> deque = new LinkedList<>();
            deque.offer(root);
            boolean flag = false;
            while(!deque.isEmpty()) {
                TreeNode cur = deque.poll();
                if(cur == null) {
                    break;
                }
                deque.offer(cur.left);
                deque.offer(cur.right);
            }
    		//循环退出后分为两种情况
            //1.队列为空
            //2.遇见了null
            while(!deque.isEmpty()) {
                TreeNode cur = deque.poll();
                if(cur != null) {
                    return false;
                }
            }
    
           return true;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
  • 相关阅读:
    如何5分钟快速上手SpringMVC
    FlinkSQL自定义UDTF使用的四种方式
    httplib库的安装以及使用
    内容创作者抖音直播涨粉变现7个小技巧
    【C++】BMI身体质量指数计算工具
    《QEMU/KVM源码分析与应用》读书笔记2 —— 第一章 QEMU与KVM概述
    谷粒商城 (五) --------- 人人开源搭建后台系统
    Unity BatchRendererGroup 在低端设备上也实现高帧率
    【PCB学习】几种接地符号
    vue2中,vue-easytable组件的使用(一)——简介和基本使用
  • 原文地址:https://blog.csdn.net/Shine0115/article/details/132898496