GO实现构建完全二叉树并实现层次、先序、中序、后序遍历的递归和非递归算法

一、树及节点定义

/*
 树
 */
type Tree struct {
	rootNode *TreeNode // 根节点确定一棵树
}

/*
 树节点
 */
type TreeNode struct {
	nodeValue int32
	Parent *TreeNode // 父节点，根节点没有
	LNode *TreeNode // 左子节点
	RNode *TreeNode // 右子节点
}

二、构建完全二叉树

     基本思路：先生成所有的节点，存到链表中，然后从根节点（curNode）开始依次将后面被添加的节点（addNode）加到curNode 的子节点，直到链表元素全部添加完毕，代码如下

func buildTree(values... int32) *Tree{
	if len(values) == 0 {
		return nil
	}
	tree := Tree{}
	nodeList := list.New()
	for i:=0; i< len(values); i++ {
		node := TreeNode{}
		node.nodeValue = values[i]
		nodeList.PushBack(&node)
	}

	curNode := nodeList.Front()
	addNode := nodeList.Front().Next()
	for addNode != nil {
		node := curNode.Value.(*TreeNode)
		if node.LNode == nil {
			node.LNode = addNode.Value.(*TreeNode)
		} else if node.RNode == nil {
			node.RNode = addNode.Value.(*TreeNode)
			curNode = curNode.Next()
		}
		addNode.Value.(*TreeNode).Parent = node
		addNode = addNode.Next()
	}

	tree.rootNode = nodeList.Front().Value.(*TreeNode)
	return &tree
}

三、方便调试和查看结果，添加节点打印方法

// 打印单个节点
func printNode(node *TreeNode) {
	if node == nil {
		return
	}
	fmt.Printf("%d ", node.nodeValue)
}

四、层次遍历

   这个没啥好说的，类似剥洋葱，一层一层剥完就行。

   这里采用链表存储当前层次（开始时为根节点这层）的所有节点并打印，然后将链表中的节点移除，把这些节点的子节点加入链表，重复遍历打印，直至链表为空，就遍历完了，代码如下

func levelTraverse(tree *Tree) {
	lis := list.New()
	lis.PushFront(tree.rootNode)
	for lis.Len() > 0  {
		len := lis.Len()
		for i:=0; i<len; i++ {
			item := lis.Front()
			lis.Remove(item)
			node := item.Value.(*TreeNode)
			printNode(node)
			if node.LNode != nil {
				lis.PushBack(node.LNode)
			}
			if node.RNode != nil {
				lis.PushBack(node.RNode)
			}
		}
	}
}

五、先序遍历

  遍历方式： 根节点 -> 左节点 -> 右节点，最简单的方法是采用递归的方式，十分简单。但我主要想写的是非递归的方式遍历，代码如下，同时我也给出了递归遍历的算法

/*
 先序遍历
 根->左->右，非递归算法
 */
func frontTraverse(tree *Tree) {
	curNode := tree.rootNode
	for curNode != nil {
		printNode(curNode)
		if curNode.LNode != nil {
			curNode = curNode.LNode
		} else if curNode.RNode != nil{
			curNode = curNode.RNode
		} else {
			for{
				if curNode.Parent.RNode == curNode {
					curNode = curNode.Parent
				} else if curNode.Parent.RNode != nil{
					curNode = curNode.Parent.RNode
					break
				} else {
					curNode = curNode.Parent.Parent
				}
				// 回溯到根节点遍历结束
				if curNode == tree.rootNode {
					return
				}
			}
		}
	}
}

/*
 先序遍历-递归算法
 */
func frontTraverse1(tree *Tree) {
	frontTraverseRecursively(tree.rootNode)
}
func frontTraverseRecursively(node *TreeNode) {
	if node != nil {
		printNode(node)
		frontTraverseRecursively(node.LNode)
		frontTraverseRecursively(node.RNode)
	}
}

 六、中序遍历

 遍历方式： 左节点  -> 根节点  -> 右节点

/*
 中序遍历，非递归算法
 左 -> 根节点 -> 右
 */
func midTraverse(tree *Tree) {
	curNode := tree.rootNode
	for curNode != nil {
		if curNode.LNode != nil {
			curNode = curNode.LNode
			continue
		}
		printNode(curNode)
		if curNode == curNode.Parent.LNode {
			printNode(curNode.Parent)
		}

		if curNode.RNode != nil {
			curNode = curNode.RNode
		} else {
			for {
				// 没有子节点了，往上找右子树
				if curNode.Parent.RNode != nil && curNode.Parent.LNode == curNode{
					curNode = curNode.Parent.RNode
					break
				} else if curNode == curNode.Parent.RNode && curNode.Parent.Parent != nil &&
					curNode.Parent == curNode.Parent.Parent.LNode {
					// 无右子树的节点，直接打印
					printNode(curNode.Parent.Parent)
				}
				curNode = curNode.Parent
				if curNode == tree.rootNode {
					return
				}
			}
		}
	}
}

 

七、后序遍历

 遍历方式： 左节点  -> 右节点 -> 根节点

/*
 后序遍历，非递归算法
 左 -> 右 -> 根
 */
func behindTraverse(tree *Tree) {
	curNode := tree.rootNode
	for curNode != nil{
		if curNode.LNode != nil{
			curNode = curNode.LNode
		} else if curNode.RNode != nil {
			curNode = curNode.RNode
		} else {
			printNode(curNode)
			for {
				// 父节点无右子节点，或者当前节点就是父节点的右子节点，则打印
				if curNode.Parent.RNode == nil || curNode.Parent.RNode == curNode{
					printNode(curNode.Parent)
					curNode = curNode.Parent
				} else if curNode.Parent.RNode != nil && curNode.Parent.LNode == curNode{
					curNode = curNode.Parent.RNode
					break
				}
				if curNode == tree.rootNode {
					return
				}
			}
		}
	}
}

 以上就是构建完全二叉树及相关的遍历方法的算法实现，完全个人思路，给需要的码友参考，上班没事做学习算法随便写的，可能与最优实现方式相径庭，大佬们看到有错误的还望指正。