ot，所以我们直接打印，然后root.Right和root.Left先后进栈，那么出栈的时候，就能确保先左后右的顺序。
static void PreOrder(BinNode root)
{
Stack stack = new Stack();
BinNode temp = root;
//入栈
while (temp != null)
{
Console.WriteLine(temp.Element);
if (temp.Right != null)
stack.Push(temp.Right);
temp = temp.Left;
}
//出栈，当然也有入栈
while (stack.Count > 0)
{
temp = (BinNode)stack.Pop();
Console.WriteLine(temp.Element);
while (temp != null)
{
if (temp.Right != null)
stack.Push(temp.Right);
temp = temp.Left;
}
}
}
//后序遍历比较麻烦，需要记录上一个访问的节点，然后在本次循环中判断当前节点的Right或Left是否为上个节点，当前节点的Right为null表示没有右节点。
static void PostOrder(BinNode root)
{
Stack stack = new Stack();
BinNode temp = root;
//入栈
while (temp != null)
{
if (temp != null)
stack.Push(temp);
temp = temp.Left;
}
//出栈，当然也有入栈
while (stack.Count > 0)
{
BinNode lastvisit = temp;
temp = (BinNode)stack.Pop();
if (temp.Right == null || temp.Right == lastvisit)
{
Console.WriteLine(temp.Element);
}
else if (temp.Left == lastvisit)
{
stack.Push(temp);
temp = temp.Right;
stack.Push(temp);
while (temp != null)
{
if (temp.Left != null)
stack.Push(temp.Left);
temp = temp.Left;
}
}
}
}
//中序遍历，类似于前序遍历
static void InOrder(BinNode root)
{
Stack stack = new Stack();
BinNode temp = root;
//入栈
while (temp != null)
{
if (temp != null)
stack.Push(temp);
temp = temp.Left;
}
//出栈，当然也有入栈
while (stack.Count > 0)
{
temp = (BinNode)stack.Pop();
Console.WriteLine(temp.Element);
if (temp.Right != null)
{
temp = temp.Right;
stack.Push(temp);
while (temp != null)
{
if (temp.Left != null)
stack.Push(temp.Left);
temp = temp.Left;
}
}
}
}
6.在二叉树中找出和为某一值的所有路径
算法思想：这道题目的苦恼在于，如果用递归，只能打出一条路径来，其它符合条件的路径打不出来。
为此，我们需要一个Stack，来保存访问过的节点，即在对该节点的递归前让其进栈，对该节点的递归结束后，再让其出栈——深度优先原则（DFS）。
此外，在递归中，如果发现某节点（及其路径）符合条件，如何从头到尾打印是比较头疼的，因为DFS使用的是stack而不是queue，为此我们需要一个临时栈，来辅助打印。
static void FindBinNode(BinNode root, int sum, Stack stack)
{
if (root == null)
return;
stack.Push(root.Element);
//Leaf
if (root.IsLeaf())
{
if (root.Element == sum)
{
Stack tempStack = new Stack();
while (stack.Count > 0)
{
tempStack.Push(stack.Pop());
}
while (tempStack.Count > 0)
{
Console.WriteLine(tempStack.Peek());
stack.Push(tempStack.Pop());
}
Console.WriteLine();
}
}
if (root.Left != null)
FindBinNode(root.Left, sum – root.Element, stack);
if (root.Right != null)
FindBinNode(root.Right, sum – root.Element, stack);
stack.Pop();
}
7.怎样编写一个程序，把一个有序整数数组放到二叉树中？
算法思想：我们该如何构造这棵二叉树呢？当然是越平衡越好，如下所示：
//// arr[0]
//// arr[1] arr[2]
//// arr[3] arr[4] arr[5]
相应编码如下：
public static void InsertArrayIntoTree(int[] arr, int pos, ref BinNode root)
{
root = new BinNode(arr[pos], null, null);
root.Element = arr[pos];
//if Left value less than arr length
if (pos * 2 + 1 > arr.Length – 1)
{
return;
}
else
{
InsertArrayIntoTree(arr, pos * 2 + 1, ref root.Left);
}
//if Right value less than arr length
if (pos * 2 + 2 > arr.Length – 1)
{
return;
}
else
{
root.Right = new BinNode(arr[pos * 2 + 2], null, null);
InsertArrayIntoTree(arr, pos * 2 + 2, ref root.Right);
}
}
8.判断整数序列是不是二叉搜索树的后序遍历结果
比如，给你一个数组： int a[] = [1, 6, 4, 3, 5] ，则F(a) => false
算法思想：在后续遍历得到的序列中，最后一个元素为树的根结点。从头开始扫描这个序列，比根结点小的元素都应该位于序列的左半部分；从第一个大于跟结点开始到跟结点前面的一个元素为止，所有元素都应该大于跟结点，因为这部分元素对应的是树的右子树。根据这样的划分，把序列划分为左右两部分，我们递归地确认序列的左、右两部分是不是都是二元查找树。
由于不能使用动态数组，所以我们每次递归都使用同一个数组arr，通过start和length来模拟“部分”数组。
public static bool VerifyArrayOfBST(int[] arr, int start, int length)
{
if (arr == null || arr.Length == 0 || arr.Length == 1)
{
return false;
}
int root = arr[length + start - 1];
int i = start;
for (; i < length - 1; i++)
{
if (arr[i] >= root)