二叉树的基本运算2

这一篇是接上一篇文章二叉树的基本运算二叉树的遍历二叉树遍历分为三种：前序、中序、后序:前序遍历：根结点 -> 左子树 -> 右子树中序遍历：左子树 -> 根结点 -> 右子树后序遍历：左子树 -> 右子树 -> 根结点另外还有一种层次遍历，即每一层都从左向右遍历。譬如，对于下面的二叉树前序遍历：abdefgc中序遍历：debgfac后序遍历：edgfbca层次遍历：abcdfeg实现方法因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在三种遍历中，前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点中序遍历go实现// 中序遍历，用栈实现func inOrderBinaryTree1(root *BinaryTreeNode) { if root == nil { return } stack := []*BinaryTreeNode{} top := -1 for top >= 0 || root != nil { for root != nil { stack = append(stack, root) top++ root = root.lChild } item := stack[top] stack = stack[:top] top– // 出栈 fmt.Print(item.data) if item.rChild != nil { root = item.rChild } }}