9.求二叉树的镜像
算法1：利用上述遍历二叉树的方法（比如说前序遍历），把访问操作修改为交换左右节点的逻辑：
static void PreOrder(ref BinNode root)
{
if (root == null)
return;
//visit current node
BinNode temp = root.Left;
root.Left = root.Right;
root.Right = temp;
PreOrder(ref root.Left);
PreOrder(ref root.Right);
}

算法2：使用循环也可以完成相同的功能。
static void PreOrder2(ref BinNode root)
{
if (root == null)
return;
Stack stack = new Stack();
stack.Push(root);
while (stack.Count > 0)
{
//visit current node
BinNode temp = root.Left;
root.Left = root.Right;
root.Right = temp;
if (root.Left != null)
stack.Push(root.Left);
if (root.Right != null)
stack.Push(root.Right);
}
}

10.一棵排序二叉树（即二叉搜索树BST），令 f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。
算法思想：最小最大节点分别在最左下与最右下节点，O(N)
static BinNode Find(BinNode root)
{
BinNode min = FindMinNode(root);
BinNode max = FindMaxNode(root);
double find = (double)(min.Element + max.Element) / 2;
return FindNode(root, find);
}

static BinNode FindMinNode(BinNode root)
{
BinNode min = root;
while (min.Left != null)
{
min = min.Left;
}
return min;
}
static BinNode FindMaxNode(BinNode root)
{
BinNode max = root;
while (max.Right != null)
{
max = max.Right;
}
return max;
}
递归寻找BST的节点，O(logN)。
static BinNode FindNode(BinNode root, double mid)
{
//如果小于相等，则从右边找一个最小值
if (root.Element <= mid)
{
if (root.Right == null)
return root;
BinNode find = FindNode(root.Right, mid);
//不一定找得到
return find.Element < mid
root : find;
}
//如果大于，则找到Left
else //temp.Element > find
{
if (root.Left == null)
return root;
BinNode find = FindNode(root.Left, mid);
//不一定找得到
return find.Element < mid
root : find;
}
}

11.把二叉搜索树转变成排序的双向链表，如
//// 13
//// 10 15
//// 5 11 17
//// 16 22
转变为Link：5=10=11=13=15=16=17=22
算法思想：这个就是中序遍历啦，因为BST的中序遍历就是一个从小到大的访问顺序。局部修改中序遍历算法，于是有如下代码：
static void ConvertNodeToLink(BinNode root, ref DoubleLink link)
{
if (root == null)
return;
BinNode temp = root;
if (temp.Left != null)
ConvertNodeToLink(temp.Left, ref link);
//visit current node
link.Next = new DoubleLink(link, null, root);
link = link.Next;
if (temp.Right != null)
ConvertNodeToLink(temp.Right, ref link);
}

但是我们发现，这样得到的Link是指向双链表最后一个元素22，而我们想要得到的是表头5，为此，我们不得不额外进行while循环，将指针向前移动到表头：
static DoubleLink ReverseDoubleLink(BinNode root, ref DoubleLink link)
{
ConvertNodeToLink(root, ref link);
DoubleLink temp = link;
while (temp.Prev != null)
{
temp = temp.Prev;
}
return temp;
}
这么写有点蠢，为什么不直接在递归中就把顺序反转呢？于是有算法2：

算法2：观察算法1的递归方法，访问顺序是Left -> Root –> Right，所以我们要把访问顺序修改为Right -> Root –> Left。
此外，算法的节点访问逻辑，是连接当前节点和新节点，同时指针link向前走，即5=10=11=13=15=16=17=22=link
代码如下所示：
link.Next = new DoubleLink(link, null, root);
link = link.Next;
那么，即使我们颠倒了访问顺序，新的Link也只是变为：22=17=16=15=13=11=10=5=link。
为此，我们修改上面的节点访问逻辑——将Next和Prev属性交换：
link.Prev = new DoubleLink(null, link, root);
link = link.Prev;
这样，新的Link就变成这样的顺序了：link=5=10=11=13=15=16=17=22
算法代码如下所示：
static void ConvertNodeToLink2(BinNode root, ref DoubleLink link)
{
if (root == null)
return;
BinNode temp = root;
if (temp.Right != null)
ConvertNodeToLink2(temp.Right, ref link);
//visit current node
link.Prev = new DoubleLink(null, link, root);
link = link.Prev;
if (temp.Left != null)
ConvertNodeToLink2(temp.Left, ref link);
}

以下算法属于二叉树的基本概念，未列出：
1.Huffman Tree的生成、编码和反编码
2.BST的实现
3.Heap的实现，优先队列