README.md

树

树状图是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：1） 每个结点有零个或多个子结点； 2） 没有父结点的结点称为根结点； 3） 每一个非根结点有且只有一个父结点； 4） 除了根结点外，每个子结点可以分为多个不相交的子树。

1. 反转二叉查找树

输入一颗叉元查找树，将该树转换为它的镜像，即在转换后的二叉查找树中，左子树的结点都大于右子树的结点。可以用递归或者循环方法完成树的镜像转换。

示例：

输入：
     8
   /   \
  6    10
 /\     /\
5  7   9  11

输出：
      8
    /  \
  10    6
  /\    /\
11  9  7  5

2. 从上往下遍历二元树

输入一颗二叉树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。

示例：

输入
：
      8
    /  \
   6    10
  /\     /\
 5  7   9  11

输出：
8   6   10   5   7   9   11

3. 把二元查找树转变成排序的双向链表

输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。

示例：

输入：
        10
      /    \
    6      14
  / \     /　 \
4    8   12   16

输出（其中`=`表示双向链）：
4=6=8=10=12=14=16

4. 在二叉树中找出和为某一值的所有路径

输入一个整数和一棵二叉树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。

示例：

输入整数22和如下二元树
       10
     /    \
    5     12
   / \
  4   7 

打印出两条路径：
[10, 12]
[10, 5, 7]

5. 平衡二叉树

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

在实现二叉树的基础，将一个普通的二叉树转化成平衡二叉树，需要实现如下功能：

• 左旋和右旋
• 节点插入
• 节点删除

5. 红黑树

AVL树追求的是极致平衡，当你插入一个元素时，旋转的次数不能预估，当插入、删除特别频繁时，树就会不停地旋转，严重影响效率，这时候红黑树出现了，红黑树能保证树的大致平衡，最多旋转3次就能实现平衡，它的查找时间复杂度为O(logn)。

在实现二叉树的基础上，将一个普通的二叉树转化成 红黑树，需要实现如下功能：

• 左旋和右旋
• 节点插入
• 节点删除