不要只收藏，还有别的事情可以做！不做自私的程序猿！

树

先来说说什么是树，生活中的树，就像下面这样，有根，有枝，有叶子。

通俗的讲，类比链表，数组，很明显，树不是线性的，而是左右这样延续下去的。

树是一种非线性的数据结构，相对于线性的数据结构(链表、数组)而言，树的平均运行时间更短(往往与树相关的排序时间复杂度都不会高)

前言

一般，我们分析树这种数据结构的时候，都会把树“倒过来”看。就如下图。

50节点，就是根节点，10节点，就是叶子节点。

二叉树的定义

二叉树是一种树形数据结构，它包含了n个有限元素的集合，其中每个元素都被称为节点。这些节点通过边（或链接）连接在一起，每个节点最多有两个子节点，分别称为左子树和右子树。树中的第一个节点被称为根节点，它是树的入口点。如果一个节点没有子节点，它被称为叶子节点。如果一个节点有子节点，它被称为内部节点。

二叉树的性质节点数和边数关系： 一个二叉树具有n个节点时，它必然有n-1条边。这是因为每个节点（除了根节点）都通过一条边与其他节点连接。高度和深度： 一个二叉树的高度（height）等于从根节点到最深叶子节点的最长路径上的节点数。根节点的深度（depth）为0，每向下一层，深度增加1。满二叉树： 如果每个节点都有0个或2个子节点，那么这棵二叉树称为满二叉树。在满二叉树中，除了叶子节点外，每个节点都有两个子节点。完全二叉树： 完全二叉树是指除了最后一层外，每一层都被充满节点，并且最后一层的节点从左到右依次填充，不留空缺。完全二叉树通常用于堆数据结构中。二叉搜索树（BST）： 二叉搜索树是一种特殊的二叉树，其中每个节点的值大于其左子树中的所有节点的值，小于其右子树中的所有节点的值。这使得在BST中进行快速的搜索、插入和删除操作成为可能。平衡二叉树： 平衡二叉树是一种特殊的BST，其中左子树和右子树的高度之差不超过1。平衡二叉树的目标是确保树的高度相对较小，从而提高搜索和操作的性能。遍历方式： 二叉树可以通过不同的遍历方式进行遍历，包括前序遍历（preorder）、中序遍历（inorder）、后序遍历（postorder）和层序遍历（level order）。这些遍历方式用于按不同顺序访问树中的节点。高度平衡二叉树： 高度平衡二叉树（AVL树）是一种自平衡的BST，它通过在插入和删除操作时自动调整树的结构，以保持树的高度平衡，从而提供了稳定的性能。特点根节点：树的起始节点，所有其他节点都从根节点开始，通过边连接到根节点。子节点：每个节点最多有两个子节点，分别是左子树和右子树。叶子节点：没有子节点的节点称为叶子节点，它们是树的末端节点。内部节点：有至少一个子节点的节点称为内部节点。空二叉树：如果树中不包含任何节点，那么它被称为空二叉树。有序树：二叉树中的节点之间有顺序关系，即左子树和右子树之间的顺序。二叉树的存储

顺序存储

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。

满二叉树的顺序存储：

对于满二叉树，如果节点的下标为i（从0开始），则其左子节点的下标为2i+1，右子节点的下标为2i+2，父节点的下标为(i-1)/2。例如，数组 [1, 2, 3, 4, 5, 6, 7] 可以表示如下的满二叉树：

 1/ \2   3/ \ /4 5 6 7

完全二叉树的顺序存储：

对于完全二叉树，节点的存储也可以采用顺序方式，但不一定是满的。同样，节点的下标关系与满二叉树类似，但可能会有一些空洞。

二叉树的一般顺序存储：

对于一般的二叉树，顺序存储结构会有一些浪费空间，因为不是每个位置都有节点。通常，可以使用特殊的标记（如null或-1）来表示空节点。

这种顺序存储结构的优点包括对于某些操作的简单性，例如通过下标直接访问节点、节省存储空间等。但缺点是只适用于特定类型的二叉树，例如满二叉树或完全二叉树，并且在一般的二叉树中可能会浪费空间。在不同情况下，树的高度可能会影响到存储结构的效率。

链式储存

二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。

Golang实现二叉树结构的定义

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

func NewTreeNode(value int) *TreeNode {    return &TreeNode{TreeNode: value}}

package mainimport (	"fmt")type TreeNode struct {	Value  int	Left   *TreeNode	Right  *TreeNode}// 在二叉树中查找指定值的节点（递归方式）func FindNode(root *TreeNode, target int) *TreeNode {	if root == nil {		return nil // 如果树为空，则返回nil	}	if root.Value == target {		return root // 如果找到目标值，返回该节点	}	// 递归在左子树中查找	leftResult := FindNode(root.Left, target)	if leftResult != nil {		return leftResult	}	// 递归在右子树中查找	rightResult := FindNode(root.Right, target)	if rightResult != nil {		return rightResult	}	return nil // 如果左右子树都没有找到目标值，则返回nil}func main() {	// 创建一个示例二叉树	root := &TreeNode{		Value: 10,		Left: &TreeNode{			Value: 5,			Left: &TreeNode{				Value: 3,				Left:  nil,				Right: nil,			},			Right: &TreeNode{				Value: 7,				Left:  nil,				Right: nil,			},		},		Right: &TreeNode{			Value: 15,			Left: &TreeNode{				Value: 12,				Left:  nil,				Right: nil,			},			Right: &TreeNode{				Value: 18,				Left:  nil,				Right: nil,			},		},	}	// 查找值为12的节点	targetValue := 12	foundNode := FindNode(root, targetValue)	if foundNode != nil {		fmt.Printf("找到节点值为%d的节点\n", targetValue)	} else {		fmt.Printf("未找到节点值为%d的节点\n", targetValue)	}}

package mainimport (	"fmt")// TreeNode 表示二叉树节点的结构type TreeNode struct {	Val   int	Left  *TreeNode	Right *TreeNode}// InsertNode 插入一个新节点到二叉搜索树func InsertNode(root *TreeNode, val int) *TreeNode {	// 如果树为空，直接创建一个新节点作为根	if root == nil {		return &TreeNode{Val: val}	}	// 如果值小于当前节点的值，则插入左子树	if val < root.Val {		root.Left = InsertNode(root.Left, val)	} else if val > root.Val { // 如果值大于当前节点的值，则插入右子树		root.Right = InsertNode(root.Right, val)	}	return root}// 中序遍历二叉树（用于验证插入操作）func InOrderTraversal(root *TreeNode) {	if root == nil {		return	}	InOrderTraversal(root.Left)	fmt.Printf("%d ", root.Val)	InOrderTraversal(root.Right)}func main() {	// 创建一个简单的二叉搜索树	root := &TreeNode{Val: 10}	root = InsertNode(root, 5)	root = InsertNode(root, 15)	root = InsertNode(root, 3)	root = InsertNode(root, 7)	// 执行中序遍历，验证插入操作	fmt.Println("中序遍历结果:")	InOrderTraversal(root)}

package mainimport (	"fmt")// TreeNode 表示二叉树节点的结构type TreeNode struct {	Val   int	Left  *TreeNode	Right *TreeNode}// FindMinNode 找到二叉搜索树中最小的节点func FindMinNode(root *TreeNode) *TreeNode {	for root.Left != nil {		root = root.Left	}	return root}// DeleteNode 从二叉搜索树中删除节点func DeleteNode(root *TreeNode, key int) *TreeNode {	if root == nil {		return root	}	// 遍历树来找到要删除的节点	if key < root.Val {		root.Left = DeleteNode(root.Left, key)	} else if key > root.Val {		root.Right = DeleteNode(root.Right, key)	} else {		// 找到了要删除的节点		// 如果节点只有一个子节点或没有子节点		if root.Left == nil {			return root.Right		} else if root.Right == nil {			return root.Left		}		// 如果节点有两个子节点，找到右子树中的最小节点来替代当前节点		temp := FindMinNode(root.Right)		root.Val = temp.Val		root.Right = DeleteNode(root.Right, temp.Val)	}	return root}// 中序遍历二叉树（用于验证删除操作）func InOrderTraversal(root *TreeNode) {	if root == nil {		return	}	InOrderTraversal(root.Left)	fmt.Printf("%d ", root.Val)	InOrderTraversal(root.Right)}func main() {	// 创建一个简单的二叉搜索树	root := &TreeNode{Val: 10}	root.Left = &TreeNode{Val: 5}	root.Right = &TreeNode{Val: 15}	root.Left.Left = &TreeNode{Val: 3}	root.Left.Right = &TreeNode{Val: 7}	// 删除值为5的节点	keyToDelete := 5	root = DeleteNode(root, keyToDelete)	// 执行中序遍历，验证删除操作	fmt.Println("中序遍历结果:")	InOrderTraversal(root)}