【二叉树1】基础知识学习笔记1【附代码】

类别

1.满二叉树，如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。节点数量：2^k -1，k是满二叉树的层数。

2.完全二叉树，在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。满二叉树一定是完全二叉树。堆也是一个完全二叉树。

3.二叉搜索树，节点有顺序，左子树所有节点小于中间节点，右边所有子树节点都大于中间节点。只要求节点上的元素满足一定顺序。

4.平衡二叉搜索树，左右子树高度的绝对值相差不能超过1。

存储方式--线性存储，链式存储

1.链式存储，左右两指针指向左子节点和右子节点；

2.线式存储，通过数组来存储数据，下标为i对应的左子节点下标：2*i+1、右子节点下标：2*i+2.

遍历方式

深度优先搜索（Depth-First Search，DFS）是一种图遍历算法，用于访问或搜索图或树的所有节点。DFS 的基本思想是从起始节点开始，沿着一条路径一直深入到最后一个节点，然后回溯，再深入下一条路径，直到遍历完所有节点。主要使用栈（Stack）来维护节点的访问顺序。当访问一个节点时，将其标记为已访问，并将其相邻未被访问的节点入栈，然后继续从栈中取出节点进行深度优先搜索。这个过程会一直持续，直到所有节点都被访问过为止。

前序遍历，中序遍历，后序遍历都是深度优先搜索。

广度优先搜索（Breadth-First Search，BFS）是一种图遍历算法，用于访问或搜索图或树的所有节点。BFS 的基本思想是从起始节点开始，先访问起始节点的所有邻居节点，然后逐层扩展，依次访问每一层的节点，直到遍历完所有节点。主要使用队列（Queue）来维护节点的访问顺序。起始时，将起始节点入队，然后从队列中取出一个节点进行访问，并将其未被访问的邻居节点入队。重复这个过程，直到队列为空为止。常见方式：层序遍历。

二叉树定义

值，左指针，右指针，相当于定义一个链表。

java里省略了指针，让这个过程一开始理解有些难度。但是我们应该换个思路，既然没有指针，直接把下一个节点放在左指针的位置就可以了，也就是这里的left和right。