树
遍历
树的节点的机构
typedef struct TreeNode
{
char data;
struct TreeNode* lchild;
struct TreeNode* rchild;
}TreeNode;
前序遍历
根节点 -> 左节点 -> 右节点
/*
#名称# preOrder
#功能# 对二叉树进行前序遍历读值
#参数# T：树的头指针
#返回值# 无
*/
void preOrder(TreeNode* T)
{
if(T == NULL)
{
return;
}
else
{
printf("%c ",T->data);
preOrder(T->lchild);
preOrder(T->rchild);
}
}
中序遍历
左节点 -> 根节点 -> 右节点
/*
#名称# inOrder
#功能# 对二叉树进行中序遍历读值
#参数# T：树的头指针
#返回值# 无
*/
void inOrder(TreeNode* T) {
if(T == NULL)
{
return;
}
else
{
inOrder(T->lchild);
printf("%c ",T->data);
inOrder(T->rchild);
}
}
后序遍历
左节点 -> 右节点 -> 根节点
/*
#名称# postOrder
#功能# 对二叉树进行后序遍历读值
#参数# T：树的头指针
#返回值# 无
*/
void postOrder(TreeNode* T) {
if(T == NULL)
{
return;
}
else
{
postOrder(T->lchild);
postOrder(T->rchild);
printf("%c ",T->data);
}
}
应用场景
树的结构
二叉查找树
二叉查找树是一种特殊的二叉树，又称为排序二叉树、二叉搜索树、二叉排序树等等，它实际上是数据域有序的二叉树，即对树上的每个结点，都满足其左子树上所有结点的数据域均小于或等于根结点的数据域，右子树上所有结点的数据域均大于根结点的数据域。
二叉搜索树的特点主要是较小的值总是保存在左节点上，相对较大的值总是保存在右节点上。这种特点使得二叉搜索树的查询效率非常高
平衡二叉树
平衡二叉树是由前苏联的两位数学家G.M.Adelse-Velskil和E.M.Landis联合提出，因此一般也称作AVL树，AVL树本质还是一棵二叉查找树，只是在其基础上增加了“平衡”的要求，需保证其左子树与右子树的高度之差的绝对值不超过1，其中左子树与右子树的高度因子之差称为平衡因子。
对于AVL树，不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡。由于旋转比较耗时，所以AVL树适合用于插入与删除次数比较少，但查找多的情况。
特点及应用
所有节点的左右子树高度差不超过1，广泛用于Windows NT内核中
红黑树
红黑树也是一颗二叉查找树，需要为每个节点存储节点的颜色，可以是红或黑。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，来确保没有一条路径会比其它路径长出两倍，因此，红黑树是一种弱平衡二叉树。
由于是弱平衡二叉树，那么在相同的节点情况下，AVL树的高度小于等于红黑树的高度，相对于要求严格的AVL树来说，它的旋转次数少，所以对于插入，删除操作较多的情况下，用红黑树的查找效率会更高一些。
特点
- 每个节点非红即黑
- 根节点是黑的
- 每个叶子节点（叶子节点即树尾端NULL节点）都是黑的
- 每条路径都包含相同的黑节点
- 如果一个节点是红的，那么它的两儿子都是黑的
- 对于任意节点而言，其到叶子点的每条路径都包含相同数目的黑节点
应用
- 广泛用于C++的STL中，如 map 和 set 是用红黑树实现的
- Linux的进程调度用红黑树管理进程控制块，进程的虚拟内存空间都存储在一颗红黑树上，每个虚拟内存空间都对应红黑树的一个节点
- IO多路复用的 epoll 采用红黑树组织管理socket fd，以支持快速的增删改查
- Nginx中用红黑树管理定时器，可以快速得到距离当前最小的定时器
- Java的TreeMap的用红黑树实现
完全二叉树
- 除了二叉树最后一层外，其他各层的节点数都达到了最大值；
- 并且，最后一层的叶子节点从左向右是连续存在，只缺失右侧若干叶子节点；
- 完美二叉树是特殊的完全二叉树；
- 完全二叉树：按从上到下，从左到右的方式存储数据。