二叉树类

一. 什么是二叉树

二叉树是计算机科学中一种重要的数据结构，它由节点（Node）、左子树（LeftSubtree）和右子树（RightSubtree）组成，且左子树和右子树也是二叉树。当所有节点都不存在左子树和右子树时，称其为叶子节点（LeafNode）。二叉树可以被用于搜索、排序和遍历数据等操作，常被用于编写算法。

二. 二叉树的分类

1. 完全二叉树

如果一棵二叉树除了最后一层节点上的孩子节点个数可以少于2个之外，其它层的节点都是满的，那么这棵二叉树被称为完全二叉树。

2. 平衡二叉树

平衡二叉树是很多编程语言中的数据结构，它是一种自平衡二叉搜索树， 具有以下性质：

- 是一棵空树，或者它的左右两个子树的高度差的绝对值不超过1，且左右两个子树都是一棵平衡二叉树。

- 一棵高度为h的平衡二叉树，其节点个数越多，其越接近于2的（h+2）次幂减1。

3. 二叉查找树

二叉查找树（BST，Binary Search Tree），也称二叉搜索树或二叉排序树，是一种特殊的二叉树，它的所有左子树上的节点都小于它的根节点，所有右子树上的节点都大于它的根节点。

三. 二叉树的遍历方式

遍历(binary tree traversal)即按照一定规律逐个访问二叉树中所有结点，每个结点最多会被访问一次。常用的二叉树遍历方式有：

1. 前序遍历(preorder traversal)：首先访问根节点，接着递归地访问左子树和右子树。

2. 中序遍历(inorder traversal)：首先递归地访问左子树，然后访问根节点，最后递归地访问右子树。

3. 后序遍历(postorder traversal)：首先递归地访问左子树和右子树，最后访问根节点。

四. 二叉树的应用

1. 操作系统中进程（任务）调度优化。

2. 代数累加器（Algorithmic accumulator）的设计。

3. 路径查找（Pathfinding）。

4. 机器学习中的决策树算法等。

5. 单纯形算法（Simplex algorithm）中，求解线性规划问题的时候，通过改变线性规划的边界条件和目标来改变可行解域，进而找最优解，就可以用二叉树结构来实现循环。