标签： 二叉树

什么是二叉树？

1. 二叉树像链表一样，属于动态数据结构
2. 二叉树的特点：
   1. 二叉树具有唯一的根节点
   2. 二叉树的每一个节点最多只有两个孩子
3. 二叉树具有天然的递归结构
   1. 每一个节点的左、右子树也是一个二叉树
4. 二叉树不一定是满的

二叉树的节点

//节点
type Node struct{
    value  int      //节点值
    Node   *left        //左孩子
    Node   *right   //右孩子
}

//二叉树
type BST struct{
    Node root   //根节点
    int  size   //二叉树的节点数（大小）
}

为什么要发明这种树结构？

1. 树结构本身是一种天然的组织结构。
2. 树结构具有高效性。

二分搜索树的应用举例

• 平衡二叉树
• AVL
• 红黑树
• 堆、并查集
• 线段树
• Trie（字典树、前缀树）（多叉树）（对字符串的操作）