二叉树理论基础

「爱情、让人受尽委屈。」 2023-10-14 21:12 15阅读 0赞

### 二叉树理论基础 ###

*  1. 二叉树的种类
 *   *  2. 两种主要的形式
 *  3. 存储方式
 *  4. 遍历方式
 *   *  4.1 深度优先搜索
     *  4.2 广度优先搜索
     *  递归法和迭代法
 *  5. 二叉树的定义

# 1. 二叉树的种类 #

1.  满二叉树
2.  完全二叉树
3.  二叉搜索树
4.  平衡二叉搜索树（AVL）

## 2. 两种主要的形式 ##

1.  满二叉树
2.  完全二叉树

# 3. 存储方式 #

代码实现过程中是用链表来进行存储的。

# 4. 遍历方式 #

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

## 4.1 深度优先搜索 ##

深度优先搜索一般是用**递归**的方式来实现的。

前序遍历、中序遍历和后序遍历都是深度优先搜索，都是通过递归的方式实现的。

## 4.2 广度优先搜索 ##

广度优先搜索中常见的是层序遍历。

层序遍历使用的就是**迭代**法。其使用方法就是使用队列来实现对二叉树一层一层的搜索。

在图论里我们广度优先搜索也是使用队列。因为队列的先进先出的规则符合我们一层一层这个遍历的需求。

## 递归法和迭代法 ##

其实用栈也可以模拟递归的过程。

我们也可以使用迭代法，也可以分别实现这个前中后序。所谓迭代法就是非递归的方式。

使用递归法来解决问题，也都可以用相应的迭代法来解决。

# 5. 二叉树的定义 #

public class TreeNode {
        
        int val;
        TreeNode left;
        TreeNode right;
    
        TreeNode() {
        }
        TreeNode(int val) {
         this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
        
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

**参考资料**：[二叉树理论基础篇][Link 1]

[06f0f765417e4ac5b66427dc0bda955c.png]: https://img-blog.csdnimg.cn/06f0f765417e4ac5b66427dc0bda955c.png
[Link 1]: https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html