# 编程开发深度搜索算法相关题目总结

17-10-25        来源：[db:作者]

“ 图解用栈数据结构对树的前序遍历，中序遍历，后续遍历。”

### 二叉树遍历

```    public class TreeNode
{
public T val { get; set; }
public TreeNode left { get; set; }
public TreeNode right { get; set; }
public TreeNode(T data)
{
val = data;
}
}```

### 前序遍历（栈结构实现）

```        public static IList PreorderTraversal(
TreeNode root)
{
IList rtn = new List();
if (root == null) return rtn;
var s = new Stack>();
s.Push(root);
TreeNode context = root;
while (s.Count > 0) {
if (context == null)
context = s.Peek();
s.Pop();
if (context.right != null) //左子树入栈
s.Push(context.right);
if (context.left != null)  //右子树入栈
s.Push(context.left);
context = context.left;
}
return rtn;
}```

while遍历前，各个变量的状态
s 栈有一个节点 1
context 上下文变量引用节点 1

context = node2

context = null

if (context == null)
context = s.Peek();

context = null

context = node5

context = null

1->2->4->3->5

### 中序遍历

```  public IList InorderTraversal(TreeNode root)
{
IList rtn = new List();
var s = new Stack>();
if (root == null) return rtn;
s.Push(root);
while (s.Count > 0)
{
var context = s.Peek();
while (context != null)
{
s.Push(context.left);
context = context.left;
}
s.Pop();
if (s.Count == 0)
return rtn;
TreeNode curNode = s.Pop();
s.Push(curNode.right);
}
return rtn;
}```