树 是一种常见的数据结构，它由节点（Node）和边（Edge）组成，具有层次结构。树的特点是每个节点有零个或多个子节点，但只有一个父节点（根节点除外）。树的常见类型包括二叉树、二叉搜索树、平衡树等。
树的基本术语
- 根节点（Root Node）: 树的顶端节点，没有父节点。
- 子节点（Child Node）: 由某个节点直接连接的下一级节点。
- 父节点（Parent Node）: 直接连接某个节点的上一级节点。
- 叶子节点（Leaf Node）: 没有子节点的节点。
- 内部节点（Internal Node）: 具有至少一个子节点的节点。
- 高度（Height）: 从根节点到叶子节点的最长路径上的边数。
- 深度（Depth）: 从根节点到某个节点的路径上的边数。
树的类型
- 二叉树（Binary Tree）: 每个节点最多有两个子节点，分别称为左子节点和右子节点。
- 二叉搜索树（Binary Search Tree, BST）: 一种特殊的二叉树，左子节点的值小于父节点，右子节点的值大于父节点。
- 平衡树（Balanced Tree）: 保持树的高度尽可能小的树，如AVL树、红黑树等。
树的操作
- 插入（Insert）: 在树中添加一个节点。
- 删除（Delete）: 从树中移除一个节点。
- 查找（Search）: 在树中查找一个节点。
- 遍历（Traversal）: 访问树中的所有节点，常见的遍历方式有前序遍历、中序遍历和后序遍历。
二叉树
二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树 。
有序二叉树，就是左子树上的数值小于树根上的值，树根的值小于右子树的值。