数据结构与算法（二）二叉树的前序遍历、中序遍历、后序遍历和层序遍历（Go语言实现）
树是一种非线性的数据结构，我们可以理解为一棵树是一系列节点对象的集合，这些节点被组织成树状，每个节点都保存着下游子节点的地址。
01 二叉树及其数据结构
二叉树就是每个节点只有两个分支的树。二叉树可以使用链表或者数组作为底层结构。
1、以链表为底层结构
以链表为底层结构的树，它的一个节点包含3部分： 存储数据的data变量，指向左子节点的left指针 和 指向右子节点的right指针
使用链表来表示树是最为直观的表示方式。
2、以数组为底层结构
用数组作为底层结构的树具有如下规则：
1.根节点所在的数组下标是0。
2.根据父节点下标计算子节点下标：对于某个父节点，其下标是p，那么其左子节点下标为 2p+1，右子节点下标为 2p+2。
3.根据子节点下标计算父节点下标：反过来即可，(左节点-1)/2，右节点/2 - 1。
对于一个满二叉树（就是树的每一个节点都有2个子节点的树），它的所有节点可以填满数组没有空缺。但是对于非满二叉树，用数组为底层结构就会出现空缺，例如上面的数组下标5和下标7就会出现空缺。
所以 对于一个稀疏的二叉树而言，使用数组是非常浪费空间的 。
02 二叉树的深度优先遍历
二叉树的深度优先遍历有3种方式：前序遍历，中序遍历和后序遍历。
前序遍历
中序遍历
后序遍历
从动态图可以看出，前序遍历是自顶向下的遍历，中序和后序遍历是自底向上的遍历。
下面是3种遍历的具体代码，使用了递归来实现（GO语言实现）：
package tree
import ( "fmt" "zbp_struct/struct/list")
// 二叉树type BTS struct{ LeftTree *BTS; // 左子树 RightTree *BTS; // 右子树 Val interface{}; // 根节点}
// 前序遍历func PreOrderTraveral(tree *BTS){ if(tree == nil){ return; } fmt.Println(tree.Val) PreOrderTraveral(tree.LeftTree) PreOrderTraveral(tree.RightTree)}
// 中序遍历func InOrderTraveral(tree *BTS){ if(tree == nil){ return; } InOrderTraveral(tree.LeftTree) fmt.Println(tree.Val) InOrderTraveral(tree.RightTree)}
// 后序遍历func PostOrderTraveral(tree *BTS){ if(tree == nil){ return; } PostOrderTraveral(tree.LeftTree) PostOrderTraveral(tree.RightTree) fmt.Println(tree.Val)}
上述树的遍历是通过递归来实现的，那么有没有不用递归的方式来实现前序遍历呢？
基本上，能用递归解决的问题都能用栈解决，只需借助栈和一个指针就能做到非递归前序遍历。栈内的每一个元素存储的是遍历到当前节点的遍历路径（存的是树节点指针）。如下所示是一个前序遍历（借助栈）的过程：
节点4既没有左子节点，也没有右 子节点
，所以此时需要回溯到上一个节点2。栈已经存储了刚才遍历的路径1->2->4，所以让栈顶元素4出栈，就可以重新访问节点2和节点2的右子节点5。此时节点2已经没有利用价值（因为已经访问过节点2左子节点和右子节点），于是让节点2出栈，节点5入栈，依此类推。
非递归版遍历代码实现如下：
// 非递归版的前序遍历func PreOrderTraveralWithStack(tree *BTS){ stack := list.InitLinkedList() // 使用单向链表模拟一个栈 curNode := tree // 当前遍历节点为根节点,curNode指针表示即将要入栈的节点
for curNode != nil || stack.Length > 0{ // 当前遍历节点如果为nil而且栈内没有可回溯的节点则表示遍历完所有节点 for curNode != nil{ fmt.Println(curNode.Val) // 输出当前节点值 stack.UnShift(curNode) // 记录当前遍历过的节点路径 curNode = curNode.LeftTree // 遍历下一个左节点，如果没有左节点则跳出第一层for循环并回溯；如果有左节点则重复该流程 }
//if(stack.Length > 0){ // 回溯 fNode := (stack.Shift()).(*BTS) // 弹出当前节点的父节点 curNode = fNode.RightTree // 以父节点的右节点作为当前遍历节点，并遍历该右节点的左子树 //} }}
非递归版本的中序和后序遍历：
// 非递归版的中序遍历func InOrderTraveralWithStack(tree *BTS){ stack := list.InitLinkedList() // 使用单向链表模拟一个栈 curNode := tree // 当前遍历节点为根节点
for curNode != nil || stack.Length > 0{ // 当前遍历节点如果为nil而且栈内没有可回溯的节点则表示遍历完所有节点 for curNode != nil{ // 如果当前节点有左子节点 stack.UnShift(curNode) // 记录 curNode = curNode.LeftTree // 查看其左子节点 }
// 如果上一个节点的左节点为nil则回溯 fNode := (stack.Shift()).(*BTS) fmt.Println(fNode.Val)
// 开始往右子树遍历 curNode = fNode.RightTree }}
// 非递归版的中序遍历(需要用到两个栈)func PostOrderTraveralWithStack(tree *BTS){ // 第一个栈放要遍历的根节点 stack1 := list.InitLinkedList() stack1.UnShift(tree)
// 第二个栈放已经遍历了的节点，这个栈里面的存放的节点顺序（从栈顶到栈底）必须是左右中节点 stack2 := list.InitLinkedList()
for stack1.Length > 0 { curNode := (stack1.Shift()).(*BTS) if curNode.LeftTree != nil{ // 如果有左子树，就需要放到stack1以待遍历该左子树 stack1.UnShift(curNode.LeftTree) } if curNode.RightTree != nil{ // 右子树同理，不过必须是先放左子树后放右子树，因为我们要先遍历右子树后遍历左子树，先遍历的右子树节点先放到stack2，因此回溯stack2的时候就是左子树的节点比右子树节点先回溯 stack1.UnShift(curNode.RightTree) }
// 将根节点放到stack2以待回溯 stack2.UnShift(curNode) }
// 当遍历完所有树，开始回溯 for stack2.Length >0{ node := (stack2.Shift()).(*BTS) fmt.Println(node.Val) }}
03 二叉树的广度优先遍历——层序遍历
层序遍历是一种从上到下从左到右的遍历方式。该遍历方法需要用到一个队列，队列中存放要遍历的根节点，遍历的关键在于当某一个节点遍历完出队时，它的左右子树就会入队。
遍历过程如下
根节点1入列
根节点1出队，它的左右子节点入队
节点2出列，左右子节点45入列。
节点3出列，右子节点6入列
最后4、5、6没有子节点，依次出列。
层序遍历代码实现
// 层序遍历（广度优先）func LevelOrderTraveral(tree *BTS){ if tree == nil{ return } queue := list.InitLinkedList() queue.Append(tree)
for queue.Length > 0 { curNode := (queue.Shift()).(*BTS) fmt.Println(curNode.Val)
if curNode.LeftTree != nil{ queue.Append(curNode.LeftTree) } if curNode.RightTree != nil{ queue.Append(curNode.RightTree) } }}
04 构建二叉树的实现
根据数组或链表构建二叉树 是一个把线性结构变为非线性结构的过程，也可以分为深度优先（以前序遍历为例）或者广度优先（层序遍历）2种方式构建。
前序遍历构建二叉树
// 根据一个数组构建一个二叉树（以前序遍历的方式）func CreateTreeFromArr(arr []interface{}) *BTS{ // arr = []interface{16, 14, 13, 10, nil, nil, 17, nil, nil, 15, nil, 19, nil, nil, 18, 6, nil, 27, nil, nil, 30, 29, nil, nil, nil} if len(arr) == 0{ return nil } curIdx := 0 var createTreeFromArr func(curIdx int) (*BTS, int) // 定义一个闭包 createTreeFromArr = func(curIdx int) (*BTS, int){ // 前序遍历 if curIdx+1 >= len(arr) || arr[curIdx] == nil { curIdx++ return nil, curIdx }
node := InitTree(arr[curIdx]) curIdx++ // 移动当前数组指针 node.LeftTree, curIdx = createTreeFromArr(curIdx) node.RightTree, curIdx = createTreeFromArr(curIdx) return node, curIdx } root, _ := createTreeFromArr(curIdx) return root}
// 根据一个链表构建一个二叉树（以前序遍历的方式）func CreateTreeFromList(inputList *list.LinkedList) *BTS{ if inputList == nil || inputList.Cur == nil || inputList.Length == 0{ return nil }
// 使用前序遍历的方式构建这个树 if inputList.Cur.Val == nil{ inputList.Cur = inputList.Cur.Next return nil // 如果未遍历完但是链表当前节点的值为nil，表示该分支到达叶子节点 }
// 以前序遍历的方式构建树 tree := InitTree(inputList.Cur.Val) inputList.Cur = inputList.Cur.Next tree.LeftTree = CreateTreeFromList(inputList) tree.RightTree = CreateTreeFromList(inputList) return tree}
层序遍历构建二叉树
// 根据一个链表构建一个完全二叉树（以层序遍历的方式）func CreateTreeFromListByLevel(inputList *list.LinkedList) (tree *BTS){ // []interface{}{16, 14, 18, 13, 15, 6, 30, 10, 17, nil, 19, nil, 27, 29, nil} if(inputList == nil || inputList.Length == 0){ return tree }
queue := list.InitLinkedList() // 使用一个队列记录已经进入树但是还没有分配左右子节点的节点
tree = InitTree(inputList.Cur.Val) // 将链表中的第一个节点放入树中作为根节点 queue.Append(tree) // 将根节点放入队列中记录起来 inputList.Cur = inputList.Cur.Next
var curNode *BTS // 定义一个树节点作为当前节点 for inputList.Cur != nil && queue.Length > 0{ curNode = (queue.Shift()).(*BTS) // 出列节点给他分配左右节点 if inputList.Cur.Val != nil{ // 如果链表节点的val为nil，那么对应的左节点为nil，如果没有这层判断就变成了有左节点但左节点的val为nil curNode.LeftTree = InitTree(inputList.Cur.Val) queue.Append(curNode.LeftTree) }
inputList.Cur = inputList.Cur.Next if inputList.Cur == nil{ break }
if inputList.Cur.Val != nil { curNode.RightTree = InitTree(inputList.Cur.Val) queue.Append(curNode.RightTree) } inputList.Cur = inputList.Cur.Next } return tree}