周末闲来无事，突然想到了二叉树的遍历问题，如果考虑用递归算法的话比较简单，但是如果用空间换取时间的话，考虑用辅助数据结构：栈来解决遍历的问题，代码如下：
//非递归后序遍历二叉树 static void PostOrder(BinaryTreeNode root) { Stack
stack = new Stack(); while (root != null) { stack.Push(root); root = root.Left; } BinaryTreeNode tmp = null; BinaryTreeNode last = null; while (stack.Count > 0) { tmp = stack.Peek(); if (tmp.Right == null || tmp.Right == last) //关键点：栈顶元素的右孩子为空或者为刚刚访问过的节点时才弹出并输出 { tmp = stack.Pop(); last = tmp; Console.WriteLine(tmp.Data); } else { tmp = tmp.Right;//右孩子不为空入栈
stack.Push(tmp); while (tmp.Left != null)//并将右孩子的所有左子孙节点入栈 { stack.Push(tmp.Left); tmp = tmp.Left; } } }
}
//非递归前序遍历二叉树
static void PrevOrder(BinaryTreeNode root) { Stack stack = new Stack(); stack.Push(root); BinaryTreeNode tmp = null; while (stack.Count >0) { tmp = stack.Pop(); Console.WriteLine(tmp.Data); if (tmp.Right != null) stack.Push(tmp.Right); //右孩子节点不为空入栈,因为要先输出左孩子，鉴于栈的特点是先入后出，所以先入右孩子 if (tmp.Left != null) stack.Push(tmp.Left);//左孩子节点不为空入栈
} }
//非递归中序遍历二叉树 static void MiddleOrder(BinaryTreeNode root) { Stack stack = new Stack(); while (root != null) { stack.Push(root); root = root.Left; } BinaryTreeNode tmp = null; while (stack.Count > 0) { tmp = stack.Pop();//与后续遍历的差别是：输出的时候检测右孩子是否为空，或者右孩子是否刚刚访问过 Console.WriteLine(tmp.Data); tmp = tmp.Right; if (tmp != null) { stack.Push(tmp); while (tmp.Left != null) { stack.Push(tmp.Left); tmp = tmp.Left; } } } }
欢迎拍砖！
延伸阅读
最新评论