[数据结构与算法]-(第0期)-什么是二叉树？

二叉树是一种数据结构，由节点组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的每个节点包含一个值，并且左子节点的值小于等于父节点的值，右子节点的值大于等于父节点的值。这个性质使得二叉树在搜索、排序、解析表达式等方面有着广泛的应用。

二叉树（binary tree）是一种非线性数据结构，代表“祖先”与“后代”之间的派生关系，体现了“一分为二”的分治逻辑。与链表类似，二叉树的基本单元是节点，每个节点包含值、左子节点引用和右子节点引用。

二叉树的基本概念：

• 根节点（Root）：树的顶端节点，没有父节点的节点。
• 节点（Node）：树中的一个元素，包含一个值和指向其子节点的指针。
• 父节点（Parent）：一个节点的直接上级，即指向该节点的节点。
• 子节点（Children）：一个节点的直接下级，即由该节点指向的节点。
• 叶子节点（Leaf）：没有子节点的节点，即位于树末端的节点。
• 深度（Depth）：节点所在的层次，根节点的深度为0，依次递增。
• 高度（Height）：树中任意节点到叶子节点的最长路径的长度，即树的最大深度。
• 子树（Subtree）：树中的一部分，由一个节点及其所有后代节点组成。

常见二叉树类型

常见的二叉树类型包括：

1. 二叉搜索树（Binary Search Tree，BST）：一种有序的二叉树，其中每个节点的左子树中的值都小于该节点的值，右子树中的值都大于该节点的值。这种特性使得在 BST 中进行搜索、插入和删除操作的平均时间复杂度为 O(log n)。
2. 平衡二叉树（Balanced Binary Tree）：一种高效的二叉树，它的任意节点的左右子树的高度差不超过 1。常见的平衡二叉树包括 AVL 树、红黑树等。平衡二叉树可以保持树的高度始终在较小的范围内，从而保证了常数时间复杂度的搜索、插入和删除操作。
3. 满二叉树（Full Binary Tree）：每个节点要么是叶子节点，要么有两个子节点。即除了叶子节点外，每个节点都有两个子节点。满二叉树的节点数为 2^h - 1，其中 h 为树的高度。
4. 完全二叉树（Complete Binary Tree）：除了最后一层外，所有层都被完全填充，并且最后一层从左到右填充。完全二叉树通常用数组来表示，具有一些特殊的性质，例如在数组中第 i 个位置的节点的左子节点位于 2i+1 处，右子节点位于 2i+2 处。
5. 二叉堆（Binary Heap）：一种特殊的完全二叉树，分为最大堆和最小堆。在最大堆中，父节点的值大于或等于任何一个子节点的值；在最小堆中，父节点的值小于或等于任何一个子节点的值。二叉堆通常用于实现优先队列等数据结构。

二叉树的遍历方式：

深度优先遍历

1. 前序遍历（Pre-order traversal）：先访问根节点，然后递归地前序遍历左子树，再递归地前序遍历右子树。

深度优先遍历（前序遍历）
F, B, A, D, C, E, G, I, H.

2. 中序遍历（In-order traversal）：先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。在二叉搜索树中，中序遍历会按照升序访问节点的值。
   

深度优先遍历（中序遍历）
A, B, C, D, E, F, G, H, I.

3. 后序遍历（Post-order traversal）：先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问根节点。
   

深度优先搜索（后序遍历）：
A, C, E, D, B, H, I, G, F.

广度优先遍历

和深度优先遍历不同，广度优先遍历会先访问离根节点最近的节点。二叉树的广度优先遍历又称按层次遍历。算法借助队列实现。 其遍历顺序是

广度优先遍历 - 层次遍历：
F, B, G, A, D, I, C, E, H.

代码实现（Go）

// TreeNode 二叉树节点结构体
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// NewTreeNode  构造方法
func NewTreeNode(v int) *TreeNode {
	return &TreeNode{
		Left:  nil, // 左子节点指针
		Right: nil, // 右子节点指针
		Val:   v,   // 节点值
	}
}

/** 层次遍历 **/
func levelOrder(root *TreeNode) []any{
		queue := list.New()
		queue.PushBack(root)
		
		nums := make([]any,0)
		for queue.Len()>0{
		  	// 出队
		  	node:= queue.Remove(queue.Front()).(*TreeNode)
		    // 保存节点
		    nums = append(nums,node.Val)
		    if node.Left != nil{
		    	 // 左子节点入队
		    	 queue.PushBack(node.Left)
		    }
		    if node.Right !=nil{
		    	 // 右子节点入队
		    	 queue.PushBack(node.Right)
		    }
		}
		return nums
}


func main() {
	/* 初始化二叉树 */
	// 初始化节点
	n1 := NewTreeNode(1)
	n2 := NewTreeNode(2)
	n3 := NewTreeNode(3)
	n4 := NewTreeNode(4)
	n5 := NewTreeNode(5)
	// 构建节点之间的引用（指针）
	n1.Left = n2
	n1.Right = n3
	n2.Left = n4
	n2.Right = n5

	fmt.Println(levelOrder(n1))

}

结果：
[1 2 3 4 5]

二叉树的应用：

1. 搜索树（Search Tree）：二叉搜索树是一种有序的二叉树，可以高效地进行搜索、插入和删除操作。
2. 表达式树（Expression Tree）：二叉树可以用于表示算术表达式，例如中序表达式、前序表达式或后序表达式。
3. 哈夫曼树（Huffman Tree）：二叉树可以用于构建哈夫曼编码，用于数据压缩。
4. 线段树（Segment Tree）：一种用于解决区间查询问题的二叉树结构。

参考

• 树的遍历
• 树