二叉树学习及Go语言实现

二叉树是比较基础的数据结构，以前也知道，但是一直没有细究，不明白它究竟有什么作用，这次学习数据结构，结合Go语言来动手实践一个，只有动手做一做对它的理解才比较深一点。

二叉树的定义

首先是二叉树的定义，二叉树顾名思义有两个叉，左右各一个，最多两个。

根节点

关于根节点，起初我还以为二叉树的根节点会变，比如根据值的大小，改变根节点。这个理解是不对的，代码实现的时候，第一个就作为根节点，后面来的，小的就往左放，大的就往右放，会调整改变的那个叫平衡二叉树
下面用这个图来说明一下
比如有四个数 13， 14， 15， 19
比如我按这样的顺序放树就长这样： 19 , 13, 14, 15

如果我们这样的顺序来放 14，13， 15，19， 树就是这样的

所以树长什么样子，跟我们放的顺序有关，而不是说一个对于相同的数值，有固定的树。

二叉树的遍历

二叉树分为三种遍历方式
中序遍历（InOrder） 左子树-> 树根 -> 右子树， 如下图就是 abc
前序遍历（PreOrder) 树根 -> 左子树 -> 右子树 如下图就是 bac
后序遍历 (PostOrder) 左子树 -> 右子树 -> 树根 如下图就是 acb
这个前序中序后序是以树根的位置来说的，记住这一点，就不怕混淆了。

我们可以看到前序遍历就能达到排序的效果，abc。

下面通过go 语言来实现二叉树，代码其实非常简单

type tree struct {
	value int
	left  *tree
	right *tree
}

func add(t *tree, value int) *tree {
	if t == nil {
		t = new(tree)
		t.value = value
		return t
	}

	if value < t.value {
		t.left = add(t.left, value)
	} else {
		t.right = add(t.right, value)
	}

	return t

}

func inOrder(node *tree) {
	if node != nil {
		inOrder(node.left)
		fmt.Printf(" [%d] ", node.value)
		inOrder(node.right)

	}
}


func main() {
	values := []int{7, 4, 1, 5}

	var tree *tree
	for _, value := range values {
		//fmt.Printf(" [%d] ", value)
		tree = add(tree, value)
	}

	inOrder(tree)
}

代码块中我们定义了tree的结构体，它含有一个value，然后两个指针一个指向左边，一个指向右边
定义了一个add方法，通过递归调用，小的就放左边，大的就放右边。
然后inOrder方法也是递归调用，先找左边，再找右边。 中间值打印出来。通过这个方法就达到了我们示例的排序效果。程序的输出为 1 4 5 7，

通过Go 的代码我们可以看出二叉树实现起来代码非常精简，也很清晰。

原文地址：http://www.cnblogs.com/dk168/p/16866192.html