树的中序遍历

对于任一结点P，

1.若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；

2.若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；

3.直到P为NULL并且栈为空则遍历结束

非递归方法：

public static void getValueTWithLoop(TreeNode node, List<int> outArr)         {             Stack<TreeNode> stack = new Stack<TreeNode>();             TreeNode p = node;//定义临时节点p             while (p != null || stack.Count != 0)             {                 if (p.left != null)//如果左子树不为空                 {                     stack.Push(p);//将传入stack                     p = p.left;//p的左子树赋值给p，p变成左子树                 }                 else//左子树为空                 {                     outArr.Add(p.value);//传入p节点值给list                     if (p.right != null)                     {                         p = p.right;                     }                     else                     {                         if (stack.Count == 0)//如果栈已经被取空                         {                             p = null;//将p置为空                         }                         while (p != null && stack.Count > 0)                         {                             p = stack.Pop();                             outArr.Add(p.value);//传入p节点值给list                             if (p.right != null)//如果右子树不为空                             {                                 p = p.right;//把右子树的值给p                                 break;//跳出循环                             }                             else                                 p = null;//p=null                         }                     }                 }             }         }

递归方法：

public static void getValueT(TreeNode node, List<int> outArr)//中序遍历     {         if (node == null)         {             return;         }         if (node.left != null)         {             getValueT(node.left, outArr);         }         outArr.Add(node.value);         if (node.right != null)         {             getValueT(node.right, outArr);         }