醋醋百科网

二叉树是树型数据结构的一种，二叉就是每个节点最多有两个子树(度不超过两个)，就是左节点、右节点。根据不同的特点又引申出完全二叉树、满二叉树、平衡二叉树、红黑树、二叉排序树、一般二叉树等。

节点是二叉树的基础，节点连接成复杂结构的单元；二叉树是n个节点集合，有且仅有一个根节点，最多有连个子节点，每个子节点又可以看成子树，所有子树是不相交的。树的定义本身就是一个递归的概念，所以树的各种操作也都是递归来实现的。度是节点拥有的子树的个数，二叉树的度最大为2；节点的层，就是节点在树的哪个深度，树的深度树树最大的层数。

斜树，只有左子树的二叉树叫左斜树，只有右子树的二叉树叫右斜树，统称为斜树。

满二叉树，所有非叶子节点的度都是2，所有叶子节点都在同一层

完全二叉树，叶子节点在最下层和次下层，且最下层的叶子节点在左侧，满二叉树是完全二叉树的一种。

二叉树的存储结构，顺序存储结构数组存储，下标表示节点的位置

链表存储

type TreeNode struct{
   Val int
   Left *TreeNode
   Right *TreeNode 
}

二叉树的遍历，前中后序遍历，深度广度优先遍历。

前序遍历从跟节点出发先遍历左子树的左节点一次从左到右访问，ABDHIEJCFG

中序遍历，从左中右访问模式，HDIBJEAFCG

后续遍历，左右中访问模式，HIDJEBFGCA

//前序遍历
func PreOrderTraversal(tree *TreeNode)  {
	if tree == nil {
		return
	}

	fmt.Println("%d ->", tree.Val)
	PreOrderTraversal(tree.Left)
	PreOrderTraversal(tree.Right)
}
// 中序遍历
func MidOrderTraversal(tree *TreeNode) {
	if tree == nil {
		return
	}

	MidOrderTraversal(tree.Left)
	fmt.Printf(" %d -> ", tree.Val)
	MidOrderTraversal(tree.Right)
}
// 后序遍历
func PostOrderTraversal(tree *TreeNode) {
	if tree == nil {
		return
	}

	PostOrderTraversal(tree.Left)
	PostOrderTraversal(tree.Right)
	fmt.Printf(" %d -> ", tree.Val)
}

按层遍历，从上到下按层依次遍历，ABCDEFGHIJ

// 按层遍历
func LevelOrderTraversal(tree *TreeNode) {
	if tree == nil {
		return
	}

	// 采用队列实现
	queue := make([]*TreeNode, 0)
	queue = append(queue, tree) // queue push
	for len(queue) > 0 {
		tree = queue[0]
		fmt.Printf(" %d -> ", tree.Val)

		queue = queue[1:] // queue pop

		if tree.Left != nil {
			queue = append(queue, tree.Left)
		}
		if tree.Right != nil {
			queue = append(queue, tree.Right)
		}
	}
}

典型例题：已知前序遍历序列和后序遍历序列，不可以唯一确定一棵二叉树；若一棵二叉树的前序遍历为ABCDEF，中序遍历为CBAEDF，请画出这棵二叉树？