二叉树的定义和使用

1.二叉树概念：

• 树的定义：
  树是一种抽象数据类型，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点通过连接它们的边组成一个具有层次关系的集合（根朝上，而叶朝下）。
• 二叉树的定义：
  二叉树属于树形结构，二叉树特点就是是每个节点最多只能有两棵子树，且有左右之分；

2.二叉树的类型：

• 满二叉树：
  满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上（深度为k，有2^k-1个节点的二叉树）；
  

• 完全二叉树：
  在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置；
  

• 二叉搜索树：
  二叉搜索树就是有序树：
  若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  它的左、右子树也分别为二叉排序树
  

• 二叉平衡搜索树：
  空树或左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
  

3.二叉树的存储

• 顺序存储 --数组：元素在内存是连续分布的；
  如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2
  

• 链式存储 --指针：通过指针把分布在散落在各个地址的节点串联一起；
  

4.二叉树的遍历

• 深度优先遍历
  前序遍历（递归法，迭代法）
  中序遍历（递归法，迭代法）
  后序遍历（递归法，迭代法）
• 广度优先遍历
  层次遍历（迭代法）

https://blog.csdn.net/m0_61630116/article/details/124877205

5.二叉树在程序中的定义（链式）：

C++:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
1
2
3
4
5
6

JAVA:

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;
  	}
}
1
2
3
4
5
6
7
8
9
10
11
12

PYTHON：

class TreeNode: 
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
1
2
3
4
5

原博链接：https://github.com/youngyangyang04/leetcode-master/blob/master/problems/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.md