• 二叉树知识点及各种遍历方式

    假装努力只会欺骗我们自己、拥有短暂的欣慰和感动，然而这个被金钱和物质所溢满的世界、一地鸡毛，它不会对我们任何人仁慈，认真努力吧！我们已不再年轻！！！

                                                                                     ——致不在年少的我自己、与屏幕前的你

    前言

    本文详细记录一些关于二叉树的基础知识和各种遍历方式，后续会持续加入新的知识点。

    一、什么是树？为什么会有数这种结构呢？包含哪些数结构呢？

    1，什么是树呢？

    树状图是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

    它具有以下的特点：每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树；

    树结构是一种非线性存储结构，存储的是具有“一对多”关系的数据元素的集合。

    2，要了解为什么会有数结构呢？首先我们分析下我们学过的两种基础结构：

    数组存储方式的分析：

    优点：通过下标方式访问元素，速度快。对于有序数组，还可以使用二分查找提高检索速度。

    缺点：如果要检索某个具体的值，或者插入值（按一定顺序）会整体移动，效率较低。

    链式存储方式的分析：

    优点：在一定程度上对数组存储方式有优化（比如：插入一个数值节点，只需要将插入节点，链接到链表中即可，删除的效率也很好）。

    缺点：在进行检索时，效率仍然较低，比如（检索某个值，需要从头节点开始遍历）。

    树存储方式的分析：

    能提高数据存储，读取的效率，比如利用二叉排序树（binary sort tree），既可以保证数据的检索速度，同时也可以保证数据的插入、删除、修改的速度。（这似乎与哈希表的特点相似，但是二叉树查找速度没有哈希表块，二叉树只是每次减半遍历，而哈希表直接不遍历，精确查找，那如果这么说，二叉树就没有啥意义了，有哈希表，还用他干嘛，不是这样的，万事万物各有所长，各有所短，实际应用中还是要看具体情况的，根据实际情况选择结构）；

    综上：实际树就是结合了数组和链表的优点，从而形成的一种新的数据结构；

    3，有哪些数结构呢？

    常见的有，红黑树，二叉树，完全二叉树，搜索二叉树，满二叉树，平衡二叉树，有序树、无序树等、

    二、二叉树概念

    1)树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
    2)二叉树的子节点分为左子节点和右子节点

     示意图：

    满二叉树：

    如果该二叉树的所有叶子节点都在最后一层，并且结点总数=2^n-1,n为层数，则我们称为满二叉树。

    完全二叉树：

    如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树

    如何判断是不是完全二叉树呢？

            完全二叉树有以下特点，宽度遍历二叉树，

    1，当遇见第一个没有左右子节点的节点后，其余后面的所有节点都是叶子结点（没有左右节点）

    2，如果遍历到某个节点，他有右子节点但是没有左子节点，该数也不是完全二叉树。

    1. public static boolean isCBT(Node2 head) {
    2.         if (head == null) {
    3.             return true;
    4.         }
    5.         LinkedList queue = new LinkedList<>();
    6.         //定义一个标记，标记是否遇到左右子节点不全的节点,初始化为false
    7.         boolean leaf = false;
    8.         Node2 l = null;
    9.         Node2 r = null;
    10.         queue.add(head);
    11.         while (!queue.isEmpty()) {
    12.             head = queue.poll();
    13.             l = head.left;
    14.             r = head.right;
    15.             if (
    16.                     (leaf && (l != null || r != null))
    17.                             ||
    18.                             (l == null && r != null)
    19.             ) {
    20.                 return false;
    21.             }
    22.             if (l != null) {
    23.                 queue.add(l);
    24.             }
    25.             if (r != null) {
    26.                 queue.add(r);
    27.             }
    28.             if (l == null || r == null) {
    29.                 leaf = true;
    30.             }
    31.         }
    32.         return true;
    33.     }

     搜索二叉树：（有以下特点：）

    1，任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
    2，若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；

    3，任意节点的左、右子树也分别为二叉查找树；

    4，没有键值相等的节点。

    如何判断是否是二叉树？

    1.  private static int preValue = Integer.MIN_VALUE;
    2. //定义一个变量来存储上一个节点的值，用来和下一个节点的值进行比较
    3.     public static boolean cheakBST(Node2 head) {
    4.         if (head == null) {
    5.             return true;
    6.         }
    7.         boolean isLeftcheakBST = cheakBST(head.left);
    8.         if (!isLeftcheakBST) {
    9. //如果左数都不是搜索二叉树，那么整个数都不是搜索二叉树了，直接return false；；
    10.             return false;
    11.         }
    12.         if (head.value <= preValue) {
    13.             return false;
    14. //如果当前节点的值小于上一个节点的值，那么就不是搜索二叉树，直接return false；
    15.         } else {
    16.             preValue = head.value;//如果是，更新prevalue;
    17.         }
    18.         return cheakBST(head.right);
    19.     }

    三、二叉树的遍历：

    递归方式，二叉树先序、中序、后序遍历：

    什么是先序中序、后序呢？就是父节点相对于左右子节点遍历的先后顺序：

    先序（递归方式）：

    1. //前序输出
    2.     public void preorder() {
    3.         System.out.println(this);
    4.         if (this.left != null) {
    5.             this.left.preorder();
    6.         }
    7.         if (this.right != null) {
    8.             this.right.preorder();
    9.         }
    10.     }

    中序（递归方式）：

    1. //中序输出二叉树
    2.     public void infixorder() {
    3.         if (this.left != null) {
    4.             this.left.infixorder();
    5.         }
    6.         System.out.println(this);
    7.         if (this.right != null) {
    8.             this.right.infixorder();
    9.         }
    10.     }

    后序（递归方式）：

    1. //后序输出二叉树
    2.     public void lastorder() {
    3.         if (this.left != null) {
    4.             this.left.lastorder();
    5.         }
    6.         if (this.right != null) {
    7.             this.right.lastorder();
    8.         }
    9.         System.out.println(this);
    10.     }

    采用非递归方式先中后序遍历二叉树：

    先序（非递归方式）：

    1.     //使用非递归方式来先序遍历二叉树
    2.     public static void preorderUnRecur(Node1 head) {
    3.         if (head == null) {
    4.             return;
    5.         }
    6.         System.out.println("preorderUnRecur:");
    7.         Stack s1 = new Stack<>();
    8.         s1.push(head);
    9.         while (!s1.isEmpty()) {
    10.             head = s1.pop();
    11.             System.out.println(head);
    12.             if (head.right != null) {
    13.                 s1.push(head.right);
    14.             }
    15.             if (head.left != null) {
    16.                 s1.push(head.left);
    17.             }
    18.         }
    19.         System.out.println();
    20.     }

    中序（非递归方式）：

    1.  //使用非递归方式来中序遍历二叉树
    2.     public static void infixorderUnRecur(Node1 head) {
    3.         System.out.println("infixorderUnRecur:");
    4.         if (head != null) {
    5.             Stack s1 = new Stack<>();
    6.             while (!s1.isEmpty()||head!=null) {
    7.                 if (head!= null) {
    8.                     s1.push(head);
    9.                     head = head.left;
    10.                 } else {
    11.                     head=s1.pop();
    12.                     System.out.println(head);
    13.                     head=head.right;
    14.                 }
    15.             }
    16.             System.out.println();
    17.         }
    18.     }

    在infixorderUnRecur中，参数Node node它本身就是一个辅助指针（这点很重要），并且这个方法中在while之前，head还没有提前入栈（这不同于先序和个后序），这是中序遍历的关键处。

    在while条件中的第二条件，原因是在按序取4、2、5、1之后3、6、7都还没有入栈，然而此时栈已经空了，如果此时退出while循环的话，就无法实现完整遍历二叉树了，如何解决呢？正好、此时的head还不为空。3、6、7都还没有入栈，当这两个条件完全满足之后就可以退出了，也实现了完整遍历。

    后序（非递归方式）：

    1.   //使用非递归方式来后序遍历二叉树
    2.     public static void lastorderUnRecur(Node1 node1) {
    3.         System.out.println("lastorderUnRecur:");
    4.         if (node1 == null) {
    5.             return;
    6.         }
    7.         Node1 head;
    8.         Stack s1 = new Stack<>();
    9.         Stack s2 = new Stack<>();
    10.         s1.push(node1);
    11.         while (!s1.isEmpty()) {
    12.             head = s1.pop();
    13.             s2.push(head);
    14.             if (head.left != null) {
    15.                 s1.push(head.left);
    16.             }
    17.             if (head.right != null) {
    18.                 s1.push(head.right);
    19.             }
    20.         }
    21.         while (!s2.isEmpty()) {
    22.             head = s2.pop();
    23.             System.out.println(head);
    24.         }
    25.         System.out.println();
    26.     }

     后序遍历的底层借助了前序遍历，只是left和right入栈s1的先后顺序不同。 

     四、二叉树宽度、深度遍历：

    宽度遍历：

    1. public static void levelOrderTraversal(Node2 head) {
    2.         System.out.println("levelOrderTraversal：");
    3.         if (head == null) {
    4.             return;
    5.         }
    6.         Queue node2s = new LinkedList<>();
    7.         node2s.add(head);
    8.         while (!node2s.isEmpty()) {
    9.             Node2 poll = node2s.poll();
    10.             System.out.println(poll.toString());
    11.             if (poll.left != null) {
    12.                 node2s.add(poll.left);
    13.             }
    14.             if (poll.right != null) {
    15.                 node2s.add(poll.right);
    16.             }
    17.         }
    18.         System.out.println();
    19.     }

    深度遍历：（实际就是中序遍历）

    1. public static void DepthTraversal(Node2 head) {
    2.         System.out.println("DepthTraversal:");
    3.         if (head == null) {
    4.             return;
    5.         }
    6.         Stack s2 = new Stack<>();
    7.         while (!s2.isEmpty() || head != null) {
    8.             if (head != null) {
    9.                 s2.push(head);
    10.                 head = head.left;
    11.             } else {
    12.                 Node2 pop = s2.pop();
    13.                 System.out.println(pop.toString());
    14.                 head = pop.right;
    15.             }
    16.         }
    17.         System.out.println();
    18.     }

    五、二叉树的顺序存储：

    基础概念： 

    二叉树的顺序存储就是用一组连续的存储单元来存放二叉树的数据元素。

     顺序存储二叉树步骤：

            首先要对树中的每个结点进行编号，编号顺序就是结点在顺序表中的存储顺序。编号方法是：按照完全二叉树的形式，根结点的编号为1（放到数组中索引为0），然后按照层次从上到下、每层从左到右的顺序对每个结点进行编号。

            当某结点是编号为i，那么它的左孩子的编号应为2i，当他是右孩子时编号则为2i+1。将二叉树存到数组中，那么下标为n的元素的左子节点索引就是2*n+1,右子节点的索引就是2*n+2；第n个元素的父节点就是(n-1) /2;

    代码实现：

    1. public class ArrBinaryTreeDemo {
    2.     public static void main(String[] args) {
    3.         int[] arr = {1, 2, 3, 4, 5, 6, 7};
    4.         ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
    5.         System.out.println("前序遍历：");
    6.         arrBinaryTree.preOrder();
    7.         System.out.println();
    8.         System.out.println("中序遍历：");
    9.         arrBinaryTree.middleOrder();
    10.         System.out.println();
    11.         System.out.println("后序遍历：");
    12.         arrBinaryTree.lastOrder();
    13.     }
    14. }
    15.  
    16. class ArrBinaryTree {
    17.     private int arr[];
    18.  
    19.     public ArrBinaryTree(int[] arr) {
    20.         this.arr = arr;
    21.     }
    22.  
    23.     //为了是有方便，重载方法preOrder
    24.     public void preOrder() {
    25.         this.preOrder(0);
    26.     }
    27.  
    28.     //为了是有方便，重写middleOrder
    29.     public void middleOrder() {
    30.         this.middleOrder(0);
    31.     }
    32.  
    33.     //为了是有方便，重载方法preOrder
    34.     public void lastOrder() {
    35.         this.lastOrder(0);
    36.     }
    37.  
    38.  
    39.     //顺序存储二叉树前序遍历,根左右
    40.     public void preOrder(int rootNode) {
    41.         //先输出根
    42.         System.out.println(arr[rootNode]);
    43.  
    44.         //递归遍历左子树
    45.         //为防止数组的越界
    46.         if ((2 * rootNode + 1) <= arr.length - 1) {
    47.             preOrder(2 * rootNode + 1);
    48.         }
    49.  
    50.         //递归遍历右子树
    51.         if ((2 * rootNode + 2) <= arr.length - 1) {
    52.             preOrder(2 * rootNode + 2);
    53.         }
    54.     }
    55.  
    56.     //顺序存储二叉树中序遍历 左根右
    57.     public void middleOrder(int rootNode) {
    58.  
    59.         //递归遍历左子树
    60.         //为防止数组的越界
    61.         if ((2 * rootNode + 1) <= arr.length - 1) {
    62.             middleOrder(2 * rootNode + 1);
    63.         }
    64.         //输出根
    65.         System.out.println(arr[rootNode]);
    66.  
    67.         //递归遍历右子树
    68.         if ((2 * rootNode + 2) <= arr.length - 1) {
    69.             middleOrder(2 * rootNode + 2);
    70.         }
    71.     }
    72.  
    73.     //顺序存储二叉树后序遍历 左右根
    74.     public void lastOrder(int rootNode) {
    75.  
    76.         //递归遍历左子树
    77.         //为防止数组的越界
    78.         if ((2 * rootNode + 1) <= arr.length - 1) {
    79.             lastOrder(2 * rootNode + 1);
    80.         }
    81.         //递归遍历右子树
    82.         if ((2 * rootNode + 2) <= arr.length - 1) {
    83.             lastOrder(2 * rootNode + 2);
    84.         }
    85.         //输出根
    86.         System.out.println(arr[rootNode]);
    87.     }
    88.  
    89. }

    代码结果：

    六，线索化二叉树：

    首先我们引入一个概念：前驱以及后继

    给一个数组arr={1,2,3,4,5}；对应在数组arr中3的前驱就是2,3的后继就是4；

     为什么需要线索二叉树？

    从上图中我们可以看到。二叉树中的8,10,14以及6节点中都有未完全利用的空指针，比如8的left和right都指向null；这也就造成了指针的浪费，我们将这些节点重复利用起来就是下面要说的——线索化二叉树 ；

    上面我们概述了“前驱”和“后继”的概念，那么我们就可以把二叉树看作一个链表结构，从而可以像遍历链表那样来遍历二叉树，进而提高效率。那么就会有三种遍历方式前序、后序、中序线索化二叉树；

    什么是线索化二叉树？

            对一棵二叉树中所有节点的空指针域按照某种遍历方式加线索的过程叫作线索化，被线索化了的二叉树称为线索二叉树。

    如何线索化二叉树

    这里例举了中序线索二叉树的方法：一个二叉树通过如下的方法“串起来”：

    所有原本为空的右(孩子)指针改为指向该节点在中序遍历后得到的数组中他的后继，所有原本为空的左(孩子)指针改为指向该节点的中序遍历后得到的数组中他的前驱。 

    对上面的二叉树进行线索化得到的结果图： 

    详细介绍和代码查看请参考：

    线索化二叉树的那些事儿_南斋孤鹤的博客-CSDN博客线索化二叉树的那些事儿https://blog.csdn.net/m0_64231944/article/details/127130203?spm=1001.2014.3001.5502

    总结

    以上就是今天要讲的内容，本文仅仅简单介绍了二叉树的基本概念，没记完，但是后续会持续更新；

  • 相关阅读:
    高通开发系列 - ALSA声卡驱动中tinymix返回时间过慢
    redis学习笔记
    TerraNoise for 3dMax插件教程
    C++项目实战——基于多设计模式下的同步&异步日志系统-⑦-日志输出格式化类设计
    case when 结合sum()函数使用
    Flutter高仿微信-第23篇-支付-设置金额
    如何在jupyter notebook中添加目录（全）
    基于YOLO算法与intel深度相机三维测量（工件尺寸和物体尺寸）
    Java实现管线拓扑关系连通性分析
    基于JavaSwing开发登录计算器 课程设计 大作业
  • 原文地址：https://blog.csdn.net/m0_64231944/article/details/127066338