代码随想录---二叉树的总结和二叉树的定义

二叉树的种类：

满二叉树：树的所有节点都是满，即都有左右孩子。

这棵二叉树为满二叉树，也可以说深度为k，有2^k-1个节点的二叉树。

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

 二叉搜索树：二叉搜索树是一颗排序树。

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

 平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

二叉树的存储方式：

二叉树可以链式存储，也可以顺序存储。

那么链式存储方式就用指针， 顺序存储的方式就是用数组。

链式存储：使用链表

 顺序存储：使用数组的方式

查找节点：如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

但是用链式表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。

二叉树的遍历方式：

二叉树主要有两种遍历方式：

1. 深度优先遍历：先往深走，遇到叶子节点再往回走。
2. 广度优先遍历：一层一层的去遍历。

那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：

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

前中后遍历其实就是看根节点的位置。在中间就是中序；在前面就前序；在后面就是后序遍历。

• 前序遍历：中左右
• 中序遍历：左中右
• 后序遍历：左右中

二叉树的定义：

java的定义：

public class TreeNode {int value;TreeNode left;TreeNode right;//无参数构造器：TreeNode(){}TreeNode(int value){this.value=value;}//有参数构造器：public TreeNode(int value, TreeNode left, TreeNode right) {this.value = value;this.left = left;this.right = right;}
}

python的定义：

class TreeNode: def __init__(self, value):self.value = valueself.left = Noneself.right = None

C++的定义：

struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};