go 语言实现二叉树 前序遍历 中序遍历 后序遍历

树的定义

树(Tree) 是 n(n>=0) 个结点的有限集, n=0 时称为空树, 在任意一颗非空树当中,

• 有且只有一个特定的称为根(Root) 的结点
• 当n>1时, 其余结点可分为 m(m>0) 个互不相交的优先集 T1 T2 … Tm, 其余每一个集合本身又是一棵树, 并且称为根的子树 (SubTree)

特别强调两点 :

• n>0时, 根节点是位移的, 不可能存在多个根节点
• 当m>0时, 子树的个数并没有限制, 但他们一定是互不相交的, 像下图的两个结构就不符合树的定义, 因为他们都有相交的子树

树的结点包含一个暑假元素以及若干个指向其子树的分支. 结点所拥有的子树的个数, 称为结点的度(Degree)

度为0的结点称为叶节点 或者终端结点, 度不为0的结点称为非终端结点或者分支结点, 除根节点以外, 分支结点也称为内部结点, 数的度是树内部各结点的度的最大值。

树的其他相关概念

结点的层级（level), 根为第一层, 根的孩子为第二层, 同一个父节点的结点互为堂兄弟结点。

森林（Forest） 是 m(m>=0) 棵互不相交的数的集合, 对数中每个节点而言, 其子树的集合即为森林,

对于下图1 来说, 两个子树就可以理解为森林

图一

图二

二叉树

• 每个节点最多有两棵子树, 没有子树或者只有一颗子树也是可以的
• 左子树和右子树是有顺序的, 次序不能任意颠倒
• 即使树中某结点只有一颗树, 也要区分是右树还是左树

特殊二叉树

斜树:所有的结点都只有左子树的二叉树, 叫左斜树, 所有结点都只有右子树的, 叫右斜树

满二叉树：在一颗二叉树中, 如果所有分支结点都存在左子树和右子树, 并且所有叶子都在同一层上, 这样的二叉树称为满二叉树

完全二叉树

除最后一层外，每一层上的节点数均达到最大值，在最后一层上只缺少右边的若干结点

二叉树的遍历

二叉树的遍历：从根节点触发，按照某种次序，一次访问二叉树的所有结点，使得每个节点被访问一次且只被放问一次

二叉树的遍历方法：

前序遍历：若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树

如下图, 遍历顺序为 ABDGHCEIF

中序遍历：若树为空，则空操作返回，否则从左节点开始先遍历左子树，然后访问根节点，最后遍历右子树

如下图遍历顺序为 GDHBAEICF

后序遍历：若树为空，则空操作返回，否则从左到右遍历访问左右子树，最后访问跟根节点

如下图, 遍历顺序是 GHDBIEFCA

层序遍历:若树为空，则空操作返回，否则从数的第一层，也就是根节点开始，在同一层，按照从左到右的顺序逐个访问，

如下图, 遍历顺序是 ABCDEFGHI

go 语言代码

package main

import "fmt"

type Object interface {

}

type node struct {
	data Object
	lchild  *node//左子树
	rchild  *node//右子树
}

func main() {
	var a = &node{
		data : "A",
	}
	var b = &node{
		data : "B",
	}
	var c = &node{
		data : "C",
	}
	a.lchild = b;
	a.rchild = c;

	var d = &node{
		data : "D",
	}
	b.lchild=  d

	var e = &node{
		data : "E",
	}
	c.lchild = e


	var f = &node{
		data : "F",
	}
	c.rchild = f

	var g = &node{
		data : "G",
	}
	d.lchild = g

	var h = &node{
		data : "H",
	}
	d.rchild = h

	var i = &node{
		data : "I",
	}
	e.lchild = i

	//PreOrder(a)
	midOrder(a)
	//afterOrder(a)
}

func PreOrder(BiTree *node)  {
	//前序遍历
	if BiTree.data ==nil {
		fmt.Println("二叉树为空无法遍历")
	}
	//先展示当前结点的元素（先遍历自己）
	fmt.Print(BiTree.data)
	//再遍历左子树
	if BiTree.lchild !=nil {
		PreOrder(BiTree.lchild)
	}
	//最后遍历右子树
	if BiTree.rchild !=nil {
		PreOrder(BiTree.rchild)
	}
}

func midOrder(BiTree *node)  {
	//先遍历左子树
	if BiTree.lchild !=nil {
		midOrder(BiTree.lchild)
	}
	//再遍历自己
	if BiTree.data !=nil {
		fmt.Print(BiTree.data)
	}
	//最后遍历右子树
	if BiTree.rchild !=nil {
		midOrder(BiTree.rchild)
	}
}

func afterOrder(BiTree *node)  {
	//后序遍历左子树
	if BiTree.lchild !=nil{
		afterOrder(BiTree.lchild)
	}
	//后序遍历右子树
	if BiTree.rchild !=nil {
		afterOrder(BiTree.rchild)
	}
	//最后自己
	if BiTree.data !=nil {
		fmt.Print(BiTree.data)
	}
}