二叉树数据结构知识点汇总系列文章

以你之姓@ 2023-09-26 20:38 78阅读 0赞

> 目标：
> 
>  *  什么是二叉树数据结构？
>  *  二叉树表示
>  *  二叉树的基本操作
>  *  二叉树的辅助操作

# 基础：关于树 #

*  树是一种流行的数据结构，本质上是`非线性`的。
 *  与数组、堆栈、队列和链表等本质上是线性的数据结构不同，树表示`层次结构`。
 *  树的排序信息并不重要。一棵树包含`节点和 2 个指针`。
 *  这两个指针分别是`父节点的左孩子和右孩子`。

> 了解树的术语

*  `根：`树的根是没有父节点的树的最顶层节点。每棵树中只有一个根节点。
 *  `父节点：`作为节点前身的节点称为该节点的父节点。 子节点：节点的直接后继节点称为该节点的子节点。
 *  `弟节点：`同一个父节点的子节点称为兄弟节点。
 *  `边：`边充当父节点和子节点之间的链接。
 *  `叶：`没有子节点的节点称为叶节点。它是树的最后一个节点。一棵树中可以有多个叶节点。
 *  `子树：`节点的子树是以该特定节点为根节点的树。
 *  `深度：`节点的深度是从根节点到该特定节点的距离。
 *  `高度：`节点的高度是该节点到该子树最深节点的距离。
 *  `树的高度：`树的高度是任何节点的最大高度。这与根节点的高度相同。
 *  `级别：`级别是树的给定节点对应的父节点的数量。
 *  `节点的度数：`节点的度数是其子节点的数量。
 *  `NULL：`二叉树中NULL节点的个数为(N+1)，其中N为二叉树的节点数。  
    ![在这里插入图片描述][a880575b9a0248daa600afcb72706530.png]

# 1. 二叉树数据结构 #

## 1)什么是二叉树数据结构？ ##

*  二叉树被定义为树数据结构，其中每个节点`最多有 2 个子节点`。
 *  由于二叉树中的每个元素只能有 2 个孩子，因此我们通常将它们命名为`左孩子和右孩子`。  
    ![在这里插入图片描述][ba53a8c800db433b990aac1c5c98874a.png]
 *  二叉树由指向树的最顶层节点（通常称为“根”）的指针表示。如果树为空，则根的值为 NULL。
 *  二叉树的每个节点包含以下部分：
    
     *  数据
     *  指向左孩子的指针
     *  指向右孩子的指针

class Node {
        
        int key;
        Node left, right;
      
        public Node(int item)
        {
        
            key = item;
            left = right = null;
        }
    }

## 2)为什么要使用树数据结构？ ##

1.  使用树的一个原因可能是因为您想存储自然形成层次结构的信息。例如计算机上的文件系统：  
    ![在这里插入图片描述][5d043aebe7c74fc297a98eb0df252767.png]
2.  树（有一些排序，例如 BST）提供适度的访问/搜索（`比链表快，比数组慢`）。
3.  树提供适度的插入/删除（比数组快，比无序列表慢）。
4.  与链表不同，与数组不同，树的节点数没有上限，因为节点是使用指针链接的。

## 3)二叉树的实现： ##

![在这里插入图片描述][c1a47e9d37974a768981a7d500192cf0.png]

class Node {
        
      
        int key;
      
        Node left, right;
       public Node(int item)
        {
        
            key = item;
            left = right = null;
        }
    }
      
      
    class BinaryTree {
        
        // 二叉树的根
        Node root;
        // 构造函数
        BinaryTree(int key) {
         root = new Node(key); }
        BinaryTree() {
         root = null; }
        public static void main(String[] args)
        {
        
            BinaryTree tree = new BinaryTree();
            // create root
            tree.root = new Node(1);
            /* 以下是上述语句后的树
               1
              / \
            null null */
      
            tree.root.left = new Node(2);
            tree.root.right = new Node(3);
            /* 2和3成为1的左右孩子
              1
             / \
            2   3
           / \ / \
      null null null null */
            tree.root.left.left = new Node(4);
            /* 4成为2的左孩子
            1
           / \
          2   3
         / \ / \
      4 null null null
        / \
      null null
            */
        }
    }

# 2.二叉树的类型 #

## 1)基于孩子数量的二叉树类型： ##

以下是基于孩子数量的二叉树类型：

*  `满二叉树`
 *  `退化二叉树`
 *  `倾斜的二叉树`

## 2)满二叉树 ##

*  如果每个节点都有 0 或 2 个子节点，则二叉树是一棵完整的二叉树。  
    ![在这里插入图片描述][775a9d6d08b74c33be0a123e14731933.png]
 *  以下是完整二叉树的示例。
 *  我们也可以说满二叉树是一棵二叉树，其中除叶节点外的所有节点都有两个孩子。
 *  完整的二叉树是一种特殊类型的二叉树，其中每个父节点/内部节点有两个或没有子节点。
 *  它也被称为适当的二叉树。

class Node {
        
      public int value;  // 节点存储的值
      public Node left;  // 节点的左子节点
      public Node right;  // 节点的右子节点
     
      public Node(int val) {
        
        value = val;
        left = null;
        right = null;
      }
    }
     
    class FullBinaryTree {
        
      public Node root;  // 二叉树的根节点
     
      public FullBinaryTree() {
        
        root = null;
      }
     
      // 将带有给定值的新节点插入二叉树中
      public void insert(int value) {
        
        Node new_node = new Node(value);
        if (root == null) {
        
          root = new_node;  // 如果树为空，将新节点设置为根节点
        } else {
        
          Node current_node = root;
          // 遍历树，直到找到一个具有空左子节点或右子节点的节点
          while (true) {
        
            if (current_node.left == null) {
        
              current_node.left = new_node;
              break;
            } else if (current_node.right == null) {
        
              current_node.right = new_node;
              break;
            } else {
        
              current_node = current_node.left;  // 如果左右子节点都存在，就走向左侧
            }
          }
        }
      }
    }
     
    class Main {
        
      public static void main(String[] args) {
        
        FullBinaryTree tree = new FullBinaryTree();
        tree.insert(1);
        tree.insert(2);
        tree.insert(3);
        tree.insert(4);
      }
    }

## 3）退化（或病态）树 ##

*  一棵树，其中每个内部节点都有一个子节点。这种树在性能方面与链表相同。
 *  `退化或病态树是一棵左或右只有一个孩子的树`。

![在这里插入图片描述][eba348e83336499a84aae537efa7694f.png]

## 4)倾斜的二叉树 ##

*  倾斜二叉树是一种病态/退化树，其中树要么由左节点支配，要么由右节点支配。
 *  因此，有两种类型的偏斜二叉树：左偏二叉树和右偏二叉树。  
    ![在这里插入图片描述][f15f363c03e34eea9461f76643aacb45.png]

## 5)平衡二叉树 ##

*  如果树的高度为 O(Log n)，其中 n 是节点数，则二叉树是平衡的。
 *  例如，AVL 树通过确保左右子树的高度之间的差异最多为 1 来保持 O(Log n) 高度。
 *  红黑树通过确保数量保持 O(Log n) 高度每个根到叶路径上的黑色节点的数量是相同的，并且没有相邻的红色节点。
 *  平衡二叉搜索树在性能方面表现良好，因为它们为搜索、插入和删除提供了 O(log n) 时间。
 *  它是一种二叉树，其中每个节点的左右子树的高度之差为 0 或 1。
 *  在上图中，值为 0 的根节点是不平衡的，深度为 2 个单位.

![在这里插入图片描述][4982d395c9fd4b69a8d9325e849399a9.png]

## 6)二叉树的重要特例： ##

![在这里插入图片描述][5a79af501111470c90d64bc105b2503d.png]

### (1)二叉搜索树 ###

*  `二叉搜索树`是一种`基于节点的二叉树数据结构`
 *  具有以下属性：
    
     *  节点的`左子树仅包含键小于节点键的节点。`
     *  节点的`右子树仅包含键大于节点键的节点。`
     *  `左子树和右子树也必须是二叉搜索树。`  
        ![在这里插入图片描述][a06fed3d9be04101b0a0a9bb67bf13a4.png]

### (2)AVL树 ###

*  AVL 树是一种`自平衡二叉搜索树 (BST)`
 *  其中`所有节点的左右子树的高度差不能超过一个`。
 *  AVL树的示例如下所示：  
    ![在这里插入图片描述][127621b6dcce42f7a4e05902faff74bb.png]
 *  下面的树是AVL，因为每个节点的左右子树的高度差小于等于1

### (3)红黑树 ###

*  红黑树是一种`自平衡二叉搜索树`，其中`每个节点都有一个额外的位`，该位通常被解释为颜色（红色或黑色）。
 *  这些颜色`用于确保树在插入和删除过程中保持平衡`。
 *  虽然树的平衡并不完美，但减少搜索时间并保持在 O(log n) 左右的时间就足够了，其中 n 是树中元素的总数。
 *  这棵树于 1972 年由 `Rudolf Bayer`发明。

### (4)B – 树 ###

*  B 树是一种`自平衡树数据结构`，`允许高效地访问、插入和删除数据项`。
 *  B 树通常用于`数据库和文件系统`，它们可以`高效地存储和检索大量数据。`
 *  B 树的特点是固定的最大度数（或阶数），它决定了一个父节点可以拥有的最大子节点数。
 *  B树中的每个节点可以有多个子节点和多个键，键用于索引和定位数据项。

### (5)B+树 ###

*  B+ 树是 B 树的变体，已`针对在文件系统和数据库中的使用进行了优化`。
 *  与 B 树一样，`B+ 树也有固定的最大度，允许高效地访问、插入和删除数据项。`
 *  但是，`在B+树中，所有数据项都存储在叶子节点中，而内部节点仅包含用于索引和定位数据项的键`。
 *  这种设计`允许更快地搜索和顺序访问数据项`，因为所有叶节点都在链表中链接在一起。

### (6)线段树 ###

*  在计算机科学中，线段树，也称为`统计树`，是一种`树状数据结构`，用于`存储有关区间或线段的信息`。
 *  它允许查询哪个存储段包含给定点。
 *  原则上，它是一个静态结构；也就是说，它是一个一旦构建就无法修改的结构。类似的数据结构是区间树。
 *  n 个间隔的集合 I 的线段树使用 O(n log n) 存储，并且可以在 O(n log n) 时间内构建。
 *  线段树支持搜索包含查询时间点 O(log n + k) 的所有区间，k 是检索到的区间或线段的数量。

# 3.二叉树的性质 #

![在这里插入图片描述][e7b241d8fafa4122b0c1c3d5bcd0bd57.png]

1.  二叉树第 l 层的最大节点数为 2l：  
    注：这里的level是从根到结点（包括根和结点）路径上的结点数。根级别为0 这可以通过归纳法证明：

> 对于root，l = 0，nodes = 20 = 1  
> 假设级别“l”上的最大节点数为 2l  
> 由于在二叉树中每个节点最多有 2 个子节点，下一层将有两个节点，即 2 \* 2l

1.  高度为“h”的二叉树中的最大节点数为 2h – 1：  
    注意：这里树的高度是根到叶路径上的最大节点数。具有单个节点的树的高度被认为是 1

> 这个结果可以从上面的第2点推导出来。如果所有级别都具有最大节点，则树具有最大节点。所以一棵高度为h的二叉树的最大节点数是1 + 2 + 4 + … + 2h-1。这是一个简单的几何级数，有 h 项，这个级数的和是 2h–1。 在一些书上，根的高度被认为是0。在这种约定下，上面的公式就变成了2h+1 – 1

1.  在具有 N 个节点的二叉树中，最小可能高度或最小层数为 Log2(N+1)： 每一层应该至少有一个元素，所以高度不能超过 N。高度为“h”的二叉树最多可以有 2^h - 1^ 个节点（上一个属性）。所以节点数会小于或等于这个最大值

二叉树的一些额外属性是：

> 二叉树

*  二叉树中的每个节点`最多可以有两个子节点`：
 *  在二叉树中，每个节点`可以有零个、一个或两个子节点`。
 *  如果一个节点`有零个子节点，则它被称为叶节点`。`如果一个节点有一个孩子，它被称为一元节点。`
 *  如果`一个节点有两个孩子`，则它被称为`二元节点`。
 *  `树顶部的节点称为根节点`：根节点是二叉树中的第一个节点，所有其他节点都连接到它。
 *  树中的所有其他节点都是根节点的子节点或后代节点。
 *  `没有任何子节点的节点称为叶节点`：叶节点是树的端点并且没有子节点。它们代表树的最终结果。

> 二叉树的高度

*  二叉树的高度定义为`从根节点到最深叶节点的边数`
 *  二叉树的高度是`从根节点到任何叶节点的最长路径的长度`。
 *  二叉树的高度也称为它的深度。

> 满二叉树

*  在`满二叉树`中，`除叶节点外的每个节点都恰好有两个子节点`
 *  在满二叉树中，`所有非叶节点都恰好有两个子节点`。
 *  这意味着在完整的二叉树中没有一元节点。

> 完全二叉树

*  在`完全二叉树`中，`除了最后一层外，树的每一层都被完全填充，可以部分填充`
 *  在完全二叉树中，树中除最后一层外的所有层都被完全填充。这意味着树中没有间隙，所有节点都连接到它们的父节点。

> 平衡二叉树

*  在`平衡二叉树`中，`每个节点的左右子树的高度最多相差1`
 *  在平衡二叉树中，每个节点的左右子树的高度相似。这确保了树是平衡的并且树的高度最小化。

> 树遍历方式

*  二叉树的`中序、前序和后序`遍历是三种常见的树遍历方式： 中序、前序和后序是三种不同的二叉树遍历方式。
    
     *  `中序遍历`访问`左子树，节点本身，然后是右子树`。
     *  `前序遍历`访问`节点本身，左子树，然后是右子树`。
     *  `后序遍历`访问`左子树、右子树，然后是节点本身`。

# 4. 二叉树（数组实现） #

*  给定一个表示树的数组，数组索引是树节点中的值，数组值给出该特定索引（或节点）的父节点。根节点索引的值将始终为 -1，因为根没有父节点。从这个给定的表示构造给定二叉树的标准链接表示。
 *  树可以用下面列出的两种方式表示：
    
     *  动态节点表示（Linked Representation）
     *  数组表示法（顺序表示法）

A(1)    
         /   \
        B(2)  C(3)  
      /   \      \
     D(4)  E(5)   F(7)

public class Tree {
        
     
      
        public static void main(String[] args)
        {
        
            Array_imp obj = new Array_imp();
    
            obj.Root("A");
            obj.set_Left("B", 0);
            obj.set_Right("C", 0);
            obj.set_Left("D", 1);
            obj.set_Right("E", 1);
            obj.set_Right("F", 2);
            obj.print_Tree();
        }
    }
     
    class Array_imp {
        
     
        // 该类的成员变量
        static int root = 0;
        static String[] str = new String[10];
     
        // 创建根节点
        public void Root(String key) {
         str[0] = key; }
     
        // 创建 root 的左子树
        public void set_Left(String key, int root)
        {
        
            int t = (root * 2) + 1;
     
            if (str[root] == null) {
        
                System.out.printf(
                    "Can't set child at %d, no parent found\n",
                    t);
            }
            else {
        
                str[t] = key;
            }
        }
     
        // 创建 root 的右子树
        public void set_Right(String key, int root)
        {
        
            int t = (root * 2) + 2;
     
            if (str[root] == null) {
        
                System.out.printf(
                    "Can't set child at %d, no parent found\n",
                    t);
            }
            else {
        
                str[t] = key;
            }
        }
     
        // 打印树
        public void print_Tree()
        {
        
     
            // Iterating using for loop
            for (int i = 0; i < 10; i++) {
        
                if (str[i] != null)
                    System.out.print(str[i]);
                else
                    System.out.print("-");
            }
        }
    }

12345-6---

# 5.二叉树的增删查操作 #

## 1）按级别顺序插入二叉树 ##

### 思路 ###

1.  使用队列对给定的树进行迭代级别顺序遍历。
2.  如果我们找到一个左孩子为空的节点，我们将创建一个新键作为该节点的左孩子。
3.  否则，如果我们找到一个右孩子为空的节点，我们将新密钥作为右孩子。
4.  我们不断遍历树，直到找到一个节点，其左子节点或右子节点为空

### 代码 ###

public class Tree {
        
        /*二叉树节点有键，指向 左孩子和指向右孩子的指针*/
        static class Node {
        
            int key;
            Node left, right;
            Node(int key)
            {
        
                this.key = key;
                left = null;
                right = null;
            }
        }
        static Node root;
        static Node temp = root;
    
        /* 二叉树的中序遍历*/
        static void inorder(Node temp)
        {
        
            if (temp == null)
                return;
    
            inorder(temp.left);
            System.out.print(temp.key + " ");
            inorder(temp.right);
        }
    
        /*在二叉树中插入元素的函数 */
        static void insert(Node temp, int key)
        {
        
    
            if (temp == null) {
        
                root = new Node(key);
                return;
            }
            Queue<Node> q = new LinkedList<Node>();
            q.add(temp);
    
            // 进行层序遍历，直到找到
            while (!q.isEmpty()) {
        
                temp = q.peek();
                q.remove();
    
                if (temp.left == null) {
        
                    temp.left = new Node(key);
                    break;
                }
                else
                    q.add(temp.left);
    
                if (temp.right == null) {
        
                    temp.right = new Node(key);
                    break;
                }
                else
                    q.add(temp.right);
            }
        }
    
        public static void main(String args[])
        {
        
            root = new Node(10);
            root.left = new Node(11);
            root.left.left = new Node(7);
            root.right = new Node(9);
            root.right.left = new Node(15);
            root.right.right = new Node(8);
    
            System.out.print(
                    "Inorder traversal before insertion:");
            inorder(root);
    
            int key = 12;
            insert(root, key);
    
            System.out.print(
                    "\nInorder traversal after insertion:");
            inorder(root);
        }
    
    }

Inorder traversal before insertion:7 11 10 15 9 8 
    Inorder traversal after insertion:7 11 12 10 15 9 8

## 2)二叉树中的删除 ##

给定一棵二叉树，通过确保树从底部收缩来从中删除一个节点（即删除的节点被最底部和最右侧的节点替换）。这与 BST 删除不同。这里元素之间没有任何顺序，所以我们用最后一个元素替换它们。

Input : Delete 10 in below tree
    
           10
         /    \         
      20     30
    
    
    Output:    
           30
         /             
     20     
    
    Input : Delete 20 in below tree
           10
         /    \         
     20     30
                \
                40
    
    Output:    
           10
       /      \             
    40        30

### 思路 ###

*  从根开始，找到二叉树中最深最右的节点和我们要删除的节点。
 *  将最深最右节点的数据替换为要删除的节点。
 *  然后删除最深最右边的节点。

### 代码 ###

public class Tree {
        
        // 二叉树节点有键，指向左孩子和右孩子的指针
        static class Node {
        
            int key;
            Node left, right;
    
            // Constructor
            Node(int key)
            {
        
                this.key = key;
                left = null;
                right = null;
            }
        }
    
        static Node root;
        static Node temp = root;
    
        // 二叉树的中序遍历
        static void inorder(Node temp)
        {
        
            if (temp == null)
                return;
    
            inorder(temp.left);
            System.out.print(temp.key + " ");
            inorder(temp.right);
        }
    
        // 删除最深的函数二叉树中的元素
        static void deleteDeepest(Node root, Node delNode)
        {
        
            Queue<Node> q = new LinkedList<Node>();
            q.add(root);
    
            Node temp = null;
    
            // 做层序遍历直到最后一个节点
            while (!q.isEmpty()) {
        
                temp = q.peek();
                q.remove();
    
                if (temp == delNode) {
        
                    temp = null;
                    return;
                }
                if (temp.right != null) {
        
                    if (temp.right == delNode) {
        
                        temp.right = null;
                        return;
                    }
                    else
                        q.add(temp.right);
                }
    
                if (temp.left != null) {
        
                    if (temp.left == delNode) {
        
                        temp.left = null;
                        return;
                    }
                    else
                        q.add(temp.left);
                }
            }
        }
    
        // 删除给定元素的函数在二叉树中
        static void delete(Node root, int key)
        {
        
            if (root == null)
                return;
    
            if (root.left == null && root.right == null) {
        
                if (root.key == key) {
        
                    root = null;
                    return;
                }
                else
                    return;
            }
    
            Queue<Node> q = new LinkedList<Node>();
            q.add(root);
            Node temp = null, keyNode = null;
    
            // 进行层序遍历直到，我们找到键和最后一个节点。
            while (!q.isEmpty()) {
        
                temp = q.peek();
                q.remove();
    
                if (temp.key == key)
                    keyNode = temp;
    
                if (temp.left != null)
                    q.add(temp.left);
    
                if (temp.right != null)
                    q.add(temp.right);
            }
    
            if (keyNode != null) {
        
                int x = temp.key;
                deleteDeepest(root, temp);
                keyNode.key = x;
            }
        }
        public static void main(String args[])
        {
        
            root = new Node(10);
            root.left = new Node(11);
            root.left.left = new Node(7);
            root.left.right = new Node(12);
            root.right = new Node(9);
            root.right.left = new Node(15);
            root.right.right = new Node(8);
    
            System.out.print("Inorder traversal "
                    + "before deletion:");
            inorder(root);
    
            int key = 11;
            delete(root, key);
    
            System.out.print("\nInorder traversal "
                    + "after deletion:");
            inorder(root);
        }
    }

Inorder traversal before deletion:7 11 12 10 15 9 8 
    Inorder traversal after deletion:7 8 12 10 15 9

# 6.二叉搜索树的增操作 #

*  `二叉搜索树`是`一种特殊类型的二叉树数据结构`
 *  具有以下属性：
    
     *  `节点的左子树仅包含键小于节点键的节点`
     *  `节点的右子树仅包含键大于节点键的节点`
     *  `左子树和右子树也必须是二叉搜索树`

![在这里插入图片描述][582f6130f6fa4c43b973c1766206a743.png]

## 1）插入二叉搜索树 ##

*  在二叉搜索树中插入一个值：
    
     *  通过维护二叉搜索树的属性，总是在叶子处插入新键。
     *  从根开始搜索键，直到找到叶节点。
     *  一旦找到叶节点，就将新节点添加为叶节点的子节点。
 *  将节点插入二叉搜索树时，遵循以下`步骤`
    
    1.  使用我们所在的当前节点的值（比如 val）检查要插入的值（比如 X）
    2.  如果 X 小于 val 移动到左子树。 否则，移动到右子树。
    3.  到达叶节点后，根据 X 与叶节点值之间的关系，将 X 插入其右侧或左侧。  
        ![在这里插入图片描述][427054a0286245588dc2f0e6c315596a.png]
 *  **插入一个值为 40 的节点：**
    
    1.  第一步：40 将与根比较，即 100。 40 小于 100。 所以移动到100的左子树。左子树的根是20。
    2.  第二步：现在将 40 与 20 进行比较。 它大于 20。 所以移动到根为30的20的右子树。
    3.  第三步：30为叶节点。 所以我们必须在 30 的左边或右边插入 40。 因为 40 大于 30，所以在 30 的右边插入 40。
 *  **新树将如下所示：**  
    ![在这里插入图片描述][8f850ae9e6c341c0aaa3b1be1a23d98e.png]

public class BinarySearchTree {
        
    
        // 二叉搜索树的节点类，包含左右子节点和键值
        class Node {
        
            int key;
            Node left, right;
    
            public Node(int item)
            {
        
                key = item;
                left = right = null;
            }
        }
    
        // 二叉搜索树的根节点
        Node root;
    
        // 无参构造函数，根节点为空
        BinarySearchTree() {
         root = null; }
    
        // 带参构造函数，初始化根节点
        BinarySearchTree(int value) {
         root = new Node(value); }
    
        // 插入节点的方法，调用 insertRec() 方法实现
        void insert(int key) {
         root = insertRec(root, key); }
    
        // 递归地在 BST 中插入新键的方法
        Node insertRec(Node root, int key)
        {
        
            // 如果树为空，则返回新节点
            if (root == null) {
        
                root = new Node(key);
                return root;
            }
    
            // 否则，在树中递归下降
            else if (key < root.key)
                root.left = insertRec(root.left, key);
            else if (key > root.key)
                root.right = insertRec(root.right, key);
    
            // 返回未更改的节点指针
            return root;
        }
    
        // 中序遍历 BST 的方法，调用 inorderRec() 方法实现
        void inorder() {
         inorderRec(root); }
    
        // 中序遍历 BST 的实用函数
        void inorderRec(Node root)
        {
        
            if (root != null) {
        
                inorderRec(root.left);
                System.out.print(root.key + " ");
                inorderRec(root.right);
            }
        }
    
        // 主函数
        public static void main(String[] args)
        {
        
            BinarySearchTree tree = new BinarySearchTree();
    
            /* 创建以下 BST
                  50
               /     \
              30      70
             /  \    /  \
           20   40  60   80 */
            tree.insert(50);
            tree.insert(30);
            tree.insert(20);
            tree.insert(40);
            tree.insert(70);
            tree.insert(60);
            tree.insert(80);
    
            // 打印 BST 的中序遍历结果
            tree.inorder();
        }
    }

20 30 40 50 60 70 80

> 为避免上述错误并避免进行两次 BFS（第一次迭代时搜索最右边的最深节点，第二次迭代时删除最右边的最深节点），我们可以在第一次遍历时存储父节点并将最右边的最深节点的数据设置为需要删除的节点，轻松删除最右边最深的节点。

public class Tree {
        
        static class Node {
        
            int data;
            Node left, right;
    
            public Node(int key) {
        
                this.data = key;
            }
        }
    
        // 二叉树的中序遍历
        static void inorder(Node root) {
        
            if (root == null)
                return;
    
            inorder(root.left);
            System.out.print(root.data + " ");
            inorder(root.right);
        }
    
        static Node deletion(Node root, int key) {
        
            if (root == null)
                return null;
    
            if (root.left == null && root.right == null) {
        
                return root.data == key ? root : null;
            }
    
            Node keyNode = null, temp = null, last = null;
            Queue<Node> q = new LinkedList<>();
            q.offer(root);
    
            //进行层序遍历以找到最深的 node(temp)，要删除的节点（key_node） 和最深节点的父节点（最后一个）
            while (!q.isEmpty()) {
        
                temp = q.poll();
    
                if (temp.data == key)
                    keyNode = temp;
    
                if (temp.left != null) {
        
                    last = temp; // 存储父节点
                    q.offer(temp.left);
                }
    
                if (temp.right != null) {
        
                    last = temp; 
                    q.offer(temp.right);
                }
            }
    
            if (keyNode != null) {
        
                keyNode.data
                        = temp.data; // 将 key_node 的数据替换为最深节点的数据
    
                if (last.right == temp) {
        
                    last.right = null;
                } else {
        
                    last.left = null;
                }
            }
    
            return root;
        }
    
        public static void main(String args[]) {
        
            Node root = new Node(9);
            root.left = new Node(2);
            root.left.left = new Node(4);
            root.left.right = new Node(7);
            root.right = new Node(8);
    
            System.out.print(
                    "Inorder traversal before deletion : ");
            inorder(root);
            System.out.println();
    
            int key = 7;
            root = deletion(root, key);
    
            System.out.print(
                    "Inorder traversal after deletion : ");
            inorder(root);
            System.out.println();
        }
    }

# 7.二叉树的应用： #

*  在编译器中，使用表达式树，它是二叉树的应用。
 *  霍夫曼编码树用于`数据压缩算法`
 *  优先级队列是二叉树的另一种应用，用于在 O(1) 时间复杂度内搜索最大值或最小值。 表示分层数据。
 *  用于 Microsoft Excel 和电子表格等编辑软件。
 *  对于在数据库中分段的索引很有用，对于在系统中存储缓存很有用， 大多数著名的`编程编译器（如 GCC）和 AOCL`都使用语法树来执行算术运算。
 *  用于`实现优先级队列`
 *  用于在`更短的时间内找到元素（二叉搜索树）` 用于在计算机中启用快速内存分配。
 *  `用于执行编码和解码操作。`
 *  二叉树可用于组织和检索大型数据集中的信息，例如倒排索引和 k-d 树。
 *  二叉树可以用来表示游戏中计算机控制角色的决策过程，例如决策树。
 *  二叉树可用于`实现搜索算法`，例如二叉搜索树可用于`快速查找排序列表中的元素`。
 *  ·二叉树可用于实现排序算法，例如堆排序，它使用二叉堆对元素进行有效排序。·

# 8.二叉树遍历： #

树遍历算法可以大致分为两类：

*  `深度优先搜索 (DFS) 算法`
 *  `广度优先搜索 (BFS) 算法`

## 深度优先搜索 (DFS) 算法 ##

使用深度优先搜索（DFS）算法的树遍历可以进一步分为三类：

*  `前序遍历（当前-左-右）`：在访问左子树或右子树内的任何节点之前访问当前节点。这里的遍历是根-左孩子-右孩子。这意味着首先遍历根节点，然后遍历其左子节点，最后遍历右子节点。
 *  `中序遍历（左-当前-右）`：在访问左子树中的所有节点之后但在访问右子树中的任何节点之前访问当前节点。这里，遍历是左孩子-根-右孩子。这意味着先遍历左孩子，然后遍历其根节点，最后遍历右孩子。
 *  `后序遍历（left-right-current）`：访问完左右子树的所有节点后访问当前节点。这里，遍历是左孩子-右孩子-根。这意味着先遍历左孩子，然后是右孩子，最后是它的根节点。

## 广度优先搜索 (BFS) 算法 ##

使用广度优先搜索（BFS）算法的树遍历可以进一步分为一类：  
Level Order Traversal：在同一级别逐级和从左到右的方式访问节点。在这里，遍历是水平的。意思是最左边的孩子先遍历完，然后从左到右同级的其他孩子遍历完。

让我们使用所有四种遍历方法遍历以下树：  
![在这里插入图片描述][9a708266cf09421e9f960863c80f2543.png]  
上面树的预序遍历：1-2-4-5-3-6-7  
上面树的中序遍历：4-2-5-1-6-3-7  
上面树的后序遍历：4-5-2-6-7-3-1  
上面树的层序遍历：1-2-3-4-5-6-7

[a880575b9a0248daa600afcb72706530.png]: https://img-blog.csdnimg.cn/a880575b9a0248daa600afcb72706530.png
[ba53a8c800db433b990aac1c5c98874a.png]: https://img-blog.csdnimg.cn/ba53a8c800db433b990aac1c5c98874a.png
[5d043aebe7c74fc297a98eb0df252767.png]: https://img-blog.csdnimg.cn/5d043aebe7c74fc297a98eb0df252767.png
[c1a47e9d37974a768981a7d500192cf0.png]: https://img-blog.csdnimg.cn/c1a47e9d37974a768981a7d500192cf0.png
[775a9d6d08b74c33be0a123e14731933.png]: https://img-blog.csdnimg.cn/775a9d6d08b74c33be0a123e14731933.png
[eba348e83336499a84aae537efa7694f.png]: https://img-blog.csdnimg.cn/eba348e83336499a84aae537efa7694f.png
[f15f363c03e34eea9461f76643aacb45.png]: https://img-blog.csdnimg.cn/f15f363c03e34eea9461f76643aacb45.png
[4982d395c9fd4b69a8d9325e849399a9.png]: https://img-blog.csdnimg.cn/4982d395c9fd4b69a8d9325e849399a9.png
[5a79af501111470c90d64bc105b2503d.png]: https://img-blog.csdnimg.cn/5a79af501111470c90d64bc105b2503d.png
[a06fed3d9be04101b0a0a9bb67bf13a4.png]: https://img-blog.csdnimg.cn/a06fed3d9be04101b0a0a9bb67bf13a4.png
[127621b6dcce42f7a4e05902faff74bb.png]: https://img-blog.csdnimg.cn/127621b6dcce42f7a4e05902faff74bb.png
[e7b241d8fafa4122b0c1c3d5bcd0bd57.png]: https://img-blog.csdnimg.cn/e7b241d8fafa4122b0c1c3d5bcd0bd57.png
[582f6130f6fa4c43b973c1766206a743.png]: https://img-blog.csdnimg.cn/582f6130f6fa4c43b973c1766206a743.png
[427054a0286245588dc2f0e6c315596a.png]: https://img-blog.csdnimg.cn/427054a0286245588dc2f0e6c315596a.png
[8f850ae9e6c341c0aaa3b1be1a23d98e.png]: https://img-blog.csdnimg.cn/8f850ae9e6c341c0aaa3b1be1a23d98e.png
[9a708266cf09421e9f960863c80f2543.png]: https://img-blog.csdnimg.cn/9a708266cf09421e9f960863c80f2543.png