二叉树简介

合集 - 数据结构(3)

1.栈：数据结构中的后进先出（LIFO）容器11-042.队列（Queue）：先进先出（FIFO）的数据结构11-05

3.二叉树简介11-08

收起

什么是二叉树？

二叉树是计算机科学中一种重要的数据结构，它在许多应用领域中都有广泛的用途。本文将介绍二叉树的概念、性质、常见类型和应用。

二叉树（Binary Tree）是一种树形数据结构，它由节点构成，每个节点最多有两个子节点，通常称为左子节点和右子节点。这两个子节点可以为空，也可以包含数据或值。二叉树是一种层次结构，根节点位于树的顶部，其他节点按照层级依次排列。

二叉树的性质

二叉树具有许多重要的性质，包括：

1. 根节点（Root Node）： 二叉树的顶部节点称为根节点，它是整棵树的起点。
2. 分支节点（Internal Node）： 除了叶子节点以外的节点都称为分支节点，它们至少有一个子节点。
3. 叶子节点（Leaf Node）： 叶子节点是没有子节点的节点，它们位于树的末梢。
4. 父节点（Parent Node）： 有子节点的节点被称为父节点。每个节点都有一个父节点，除了根节点。
5. 子节点（Child Node）： 子节点是直接连接到父节点的节点。一个父节点可以有最多两个子节点，即左子节点和右子节点。
6. 深度（Depth）： 节点的深度是从根节点到该节点的路径长度，根节点的深度为0。
7. 高度（Height）： 二叉树的高度是从根节点到最深层叶子节点的最长路径长度。树的高度是整棵树的高度。
8. 度（Degree）： 节点的度是指其子节点的数量，对于二叉树，节点的度最大为2。
9. 子树（Subtree）： 子树是树中的任何节点及其所有后代节点形成的树。子树可以是原树的一部分。

常见类型的二叉树

二叉树有许多不同类型的变体，其中一些最常见的包括：

1. 二叉搜索树（Binary Search Tree，BST）： 二叉搜索树是一种特殊类型的二叉树，其中左子树的值小于或等于根节点的值，右子树的值大于根节点的值。这种有序性质使得BST在搜索、插入和删除操作上非常高效。
2. 平衡二叉树（Balanced Binary Tree）： 平衡二叉树是一种二叉搜索树，它确保树的高度保持在较小范围内，以提高搜索性能。常见的平衡二叉树包括AVL树和红黑树。
3. 满二叉树（Full Binary Tree）： 满二叉树是一种每个节点都有0或2个子节点的二叉树。它的叶子节点都位于同一层。
4. 完全二叉树（Complete Binary Tree）： 完全二叉树是一种除了最后一层外，其他层都被完全填充的二叉树。最后一层的节点从左向右填充。

二叉搜索树

以下是一个简单的Go语言实现的二叉搜索树（Binary Search Tree，BST）示例。这个示例包括二叉搜索树的基本操作，如插入、查找和中序遍历。

package main
 
import "fmt"
 
// TreeNode 表示二叉搜索树的节点结构
type TreeNode struct {
	Value int
	Left  *TreeNode
	Right *TreeNode
}
 
// Insert 用于向BST中插入新的节点
func (root *TreeNode) Insert(value int) *TreeNode {
	if root == nil {
		return &TreeNode{Value: value}
	}
 
	if value < root.Value {
		root.Left = root.Left.Insert(value)
	} else if value > root.Value {
		root.Right = root.Right.Insert(value)
	}
 
	return root
}
 
// Search 用于在BST中搜索特定值
func (root *TreeNode) Search(value int) *TreeNode {
	if root == nil || root.Value == value {
		return root
	}
 
	if value < root.Value {
		return root.Left.Search(value)
	}
 
	return root.Right.Search(value)
}
 
// InorderTraversal 用于执行中序遍历BST
func (root *TreeNode) InorderTraversal() {
	if root != nil {
		root.Left.InorderTraversal()
		fmt.Printf("%d ", root.Value)
		root.Right.InorderTraversal()
	}
}
 
func main() {
	root := &TreeNode{Value: 10}
	root.Insert(5)
	root.Insert(15)
	root.Insert(3)
	root.Insert(7)
	root.Insert(12)
	root.Insert(18)
 
	fmt.Println("Inorder Traversal of BST:")
	root.InorderTraversal()
	fmt.Println()
 
	searchValue := 7
	if root.Search(searchValue) != nil {
		fmt.Printf("Found %d in BST.\n", searchValue)
	} else {
		fmt.Printf("%d not found in BST.\n", searchValue)
	}
 
	searchValue = 8
	if root.Search(searchValue) != nil {
		fmt.Printf("Found %d in BST.\n", searchValue)
	} else {
		fmt.Printf("%d not found in BST.\n", searchValue)
	}
}

在这个示例中，我们定义了一个TreeNode结构来表示BST的节点，以及用于插入和搜索节点的方法。我们还实现了中序遍历以演示BST中元素的有序输出。在main函数中，我们创建了一个BST，插入了一些值，然后进行了搜索操作并进行了中序遍历。

平衡二叉树

平衡二叉树（Balanced Binary Tree）是一种特殊类型的二叉树，它的高度保持在较小范围内，以确保树的性能在搜索、插入和删除操作上都很好。其中一个常见的平衡二叉树是AVL树。以下是一个用Go语言实现的简单AVL树示例：

package main
 
import (
	"fmt"
)
 
type TreeNode struct {
	Value       int
	Left, Right *TreeNode
	Height      int
}
 
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
 
func height(node *TreeNode) int {
	if node == nil {
		return -1
	}
	return node.Height
}
 
func updateHeight(node *TreeNode) {
	node.Height = 1 + max(height(node.Left), height(node.Right))
}
 
func rotateRight(y *TreeNode) *TreeNode {
	x := y.Left
	T2 := x.Right
 
	x.Right = y
	y.Left = T2
 
	updateHeight(y)
	updateHeight(x)
 
	return x
}
 
func rotateLeft(x *TreeNode) *TreeNode {
	y := x.Right
	T2 := y.Left
 
	y.Left = x
	x.Right = T2
 
	updateHeight(x)
	updateHeight(y)
 
	return y
}
 
func getBalance(node *TreeNode) int {
	if node == nil {
		return 0
	}
	return height(node.Left) - height(node.Right)
}
 
func insert(root *TreeNode, value int) *TreeNode {
	if root == nil {
		return &TreeNode{Value: value, Height: 1}
	}
 
	if value < root.Value {
		root.Left = insert(root.Left, value)
	} else if value > root.Value {
		root.Right = insert(root.Right, value)
	} else {
		// Duplicate values are not allowed
		return root
	}
 
	updateHeight(root)
 
	balance := getBalance(root)
 
	// Left-Left case
	if balance > 1 && value < root.Left.Value {
		return rotateRight(root)
	}
 
	// Right-Right case
	if balance < -1 && value > root.Right.Value {
		return rotateLeft(root)
	}
 
	// Left-Right case
	if balance > 1 && value > root.Left.Value {
		root.Left = rotateLeft(root.Left)
		return rotateRight(root)
	}
 
	// Right-Left case
	if balance < -1 && value < root.Right.Value {
		root.Right = rotateRight(root.Right)
		return rotateLeft(root)
	}
 
	return root
}
 
func inorderTraversal(root *TreeNode) {
	if root != nil {
		inorderTraversal(root.Left)
		fmt.Printf("%d ", root.Value)
		inorderTraversal(root.Right)
	}
}
 
func main() {
	var root *TreeNode
 
	values := []int{10, 5, 15, 3, 7, 12, 18}
 
	for _, value := range values {
		root = insert(root, value)
	}
 
	fmt.Println("Inorder Traversal of AVL Tree:")
	inorderTraversal(root)
	fmt.Println()
}

在这个示例中，我们定义了一个TreeNode结构来表示AVL树的节点，包括值、左子树、右子树和高度。我们还实现了插入操作，以确保树的平衡性。在main函数中，我们创建了一个AVL树，插入了一些值，然后进行了中序遍历以显示树的元素按升序排列。

满二叉树

满二叉树（Full Binary Tree）作为一种特殊类型的二叉树，每个节点都有0或2个子节点，而且叶子节点都位于同一层。以下是一个用Go语言实现的满二叉树示例：

package main
 
import (
	"fmt"
)
 
type TreeNode struct {
	Value  int
	Left   *TreeNode
	Right  *TreeNode
}
 
func NewTreeNode(value int) *TreeNode {
	return &TreeNode{Value: value}
}
 
func main() {
	root := NewTreeNode(1)
	root.Left = NewTreeNode(2)
	root.Right = NewTreeNode(3)
	root.Left.Left = NewTreeNode(4)
	root.Left.Right = NewTreeNode(5)
	root.Right.Left = NewTreeNode(6)
	root.Right.Right = NewTreeNode(7)
 
	fmt.Println("Inorder Traversal of Full Binary Tree:")
	inorderTraversal(root)
	fmt.Println()
}
 
func inorderTraversal(root *TreeNode) {
	if root != nil {
		inorderTraversal(root.Left)
		fmt.Printf("%d ", root.Value)
		inorderTraversal(root.Right)
	}
}

在这个示例中，我们定义了一个TreeNode结构来表示满二叉树的节点，包括值、左子树和右子树。在main函数中，我们手动构建了一个满二叉树，并执行了中序遍历以显示树的元素。请注意，满二叉树的特点是每个节点都有0或2个子节点，并且叶子节点都在同一层。这使得满二叉树在某些应用中具有特殊的优势。

完全二叉树

以下是一个用Go语言实现的完全二叉树示例。在完全二叉树中，除了最后一层，其他层都是满的，最后一层的节点从左向右填充。

package main
 
import (
	"fmt"
)
 
type TreeNode struct {
	Value int
	Left  *TreeNode
	Right *TreeNode
}
 
func NewTreeNode(value int) *TreeNode {
	return &TreeNode{Value: value}
}
 
func main() {
	root := NewTreeNode(1)
	root.Left = NewTreeNode(2)
	root.Right = NewTreeNode(3)
	root.Left.Left = NewTreeNode(4)
	root.Left.Right = NewTreeNode(5)
	root.Right.Left = NewTreeNode(6)
 
	fmt.Println("Inorder Traversal of Complete Binary Tree:")
	inorderTraversal(root)
	fmt.Println()
}
 
func inorderTraversal(root *TreeNode) {
	if root != nil {
		inorderTraversal(root.Left)
		fmt.Printf("%d ", root.Value)
		inorderTraversal(root.Right)
	}
}

在这个示例中，我们定义了一个TreeNode结构来表示完全二叉树的节点，包括值、左子树和右子树。在main函数中，我们手动构建了一个完全二叉树，并执行了中序遍历以显示树的元素。请注意，完全二叉树的特点是除了最后一层，其他层都是满的，最后一层的节点从左向右填充。这种结构在一些应用中具有特殊的性质，例如在堆数据结构中的应用。

二叉树的应用

二叉树在计算机科学和编程中有广泛的应用，包括：

1. 二叉搜索树的搜索、插入和删除操作： 用于高效地管理有序数据集合。
2. 图形学： 用于构建场景图、动画和图形渲染。
3. 文件系统： 文件和目录的组织通常以树的形式表示，以实现高效的文件检索和管理。
4. 数据压缩： 哈夫曼树（Huffman Tree）用于数据压缩。
5. 编译器： 语法分析器使用语法树来表示程序的结构，以进行编译和优化。
6. 网络路由： 网络路由算法使用树结构来确定最佳路径。
7. 人工智能： 决策树用于模拟决策和行为。

二叉树的遍历

二叉树的遍历是一种常见的操作，用于访问树中的所有节点。主要的遍历方法包括：

1. 前序遍历（Preorder Traversal）： 从根节点开始，首先访问根节点，然后依次遍历左子树和右子树。
2. 中序遍历（Inorder Traversal）： 从根节点开始，首先遍历左子树，然后访问根节点，最后遍历右子树。对于二叉搜索树，中序遍历可以得到有序的结果。
3. 后序遍历（Postorder Traversal）： 从根节点开始，首先遍历左子树和右子树，最后访问根节点。
4. 层序遍历（Level-order Traversal）： 从树的顶部开始，逐层遍历节点，首先访问根节点，然后依次遍历每一层的节点。

二叉树的遍历是许多树操作的基础，它们可以用于搜索、数据提取、树的复制等任务。

---

声明：本作品采用署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)进行许可，使用时请注明出处。
Author: mengbin
blog: mengbin
Github: mengbin92
cnblogs: 恋水无意

---