目 录CONTENT

文章目录

算法学习-二叉树

Sakura
2023-09-23 / 0 评论 / 0 点赞 / 26 阅读 / 13136 字 / 正在检测是否收录...

算法学习-二叉树

二叉树基本概念: 7.1   二叉树 - Hello 算法 (hello-algo.com)

1. 二叉树基础

1.1 定义二叉树

// TreeNode 二叉树节点
type TreeNode struct {
	Value any
	Left  *TreeNode
	Right *TreeNode
}

// NewTreeNode 构建二叉树节点
func NewTreeNode(value any) *TreeNode {
	return &TreeNode{
		Value: value,
		Left:  nil,
		Right: nil,
	}
}

1.2 初始化二叉树

初始化如图所示的一个二叉树

func TestNewTreeNode(t *testing.T) {
	// 定义节点
	node1 := NewTreeNode(1)
	node2 := NewTreeNode(2)
	node3 := NewTreeNode(3)
	node4 := NewTreeNode(4)
	node5 := NewTreeNode(5)

	// 构建二叉树
	node1.Left = node2
	node1.Right = node3
	node2.Left = node4
	node2.Right = node5
}

2. 二叉树种类

2.1 完美二叉树(满二叉树)

完美二叉树(perfect binary tree)所有层的节点都被完全填满。

在完美二叉树中,叶节点的度为 0 其余所有节点的度都为 2 ;若树的高度为 ℎ ,则节点总数为 2ℎ+1−1

完美二叉树

2.2 完全二叉树

完全二叉树(complete binary tree)只有最底层的节点未被填满,且最底层节点尽量靠左填充。

完全二叉树

2.3 完满二叉树

满二叉树(full binary tree)除了叶节点之外,其余所有节点都有两个子节点。

完满二叉树

2.4 平衡二叉树

平衡二叉树(balanced binary tree)中任意节点的左子树和右子树的高度之差的绝对值不超过 1 。

平衡二叉树

3. 二叉树的遍历

3.1 层序遍历

层序遍历(level-order traversal)从顶部到底部逐层遍历二叉树,并在每一层按照从左到右的顺序访问节点。

本质上属于广度优先遍历(breadth-first traversal),也称广度优先搜索(breadth-first search, BFS),体现了一种“一圈一圈向外扩展”的逐层遍历方式。

二叉树的层序遍历

层序遍历代码实现:

使用队列的先进先出,来实现广度优先遍历

// 层序遍历
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.Value)
		// 如果左子节点不为nil,入队
		if node.Left != nil {
			queue.PushBack(node.Left)
		}
		if node.Right != nil {
			queue.PushBack(node.Right)
		}
	}
	return nums
}

  • 测试

func TestNewTreeNode(t *testing.T) {
	// 1.初始化节点
	node1 := NewTreeNode(1)
	node2 := NewTreeNode(2)
	node3 := NewTreeNode(3)
	node4 := NewTreeNode(4)
	node5 := NewTreeNode(5)
	node6 := NewTreeNode(6)
	node7 := NewTreeNode(7)

	// 2.构建二叉树
	node1.Left = node2
	node1.Right = node3
	node2.Left = node4
	node2.Right = node5
	node3.Left = node6
	node3.Right = node7

	// 3.层序遍历二叉树
	order := levelOrder(node1)
	fmt.Println("层序遍历二叉树:", order)

}

3.2 前,中,后序遍历

二叉搜索树的前序、中序、后序遍历

前,中,后序遍历代码实现

使用递归实现深度优先搜索

// 前序遍历
// 节点访问顺序 根 -> 左 -> 右
func PreOrder(node *TreeNode) []any {
	var result []any
	var preOrder func(node *TreeNode)
	preOrder = func(node *TreeNode) {
		if node == nil {
			return
		}
		result = append(result, node.Value)
		preOrder(node.Left)
		preOrder(node.Right)
	}
	preOrder(node)
	return result
}

// 中序遍历
// 节点访问顺序 左 -> 根 -> 右
func MiddleOrder(node *TreeNode) []any {
	var result []any
	var middleOrder func(node *TreeNode)
	middleOrder = func(node *TreeNode) {
		if node == nil {
			return
		}
		middleOrder(node.Left)
		result = append(result, node.Value)
		middleOrder(node.Right)
	}
	middleOrder(node)
	return result
}

// 后序遍历
// 节点访问顺序 左 -> 右 -> 根
func PostOrder(node *TreeNode) []any {
	var result []any
	var postOrder func(node *TreeNode)
	postOrder = func(node *TreeNode) {
		if node == nil {
			return
		}
		postOrder(node.Left)
		postOrder(node.Right)
		result = append(result, node.Value)
	}
	postOrder(node)
	return result
}

  • 测试

func TestNewTreeNode(t *testing.T) {
	// 1.初始化节点
	node1 := NewTreeNode(1)
	node2 := NewTreeNode(2)
	node3 := NewTreeNode(3)
	node4 := NewTreeNode(4)
	node5 := NewTreeNode(5)
	node6 := NewTreeNode(6)
	node7 := NewTreeNode(7)

	// 2.构建二叉树
	node1.Left = node2
	node1.Right = node3
	node2.Left = node4
	node2.Right = node5
	node3.Left = node6
	node3.Right = node7


	// 前序遍历
	preOrderResult := PreOrder(node1)
	fmt.Println("前序遍历:", preOrderResult)

	// 中序遍历
	middleOrderResult := MiddleOrder(node1)
	fmt.Println("中序遍历:", middleOrderResult)

	// 后序遍历
	postOrderResult := PostOrder(node1)
	fmt.Println("后序遍历:", postOrderResult)
}

4. 二叉树用数组表示

7.3   二叉树数组表示 - Hello 算法 (hello-algo.com)

  • 完美二叉树用数组表示

完美二叉树的数组表示

  • 任意二叉树用数组表示

任意类型二叉树的数组表示

  • 完全二叉树用数组表示

完全二叉树的数组表示

4.1 定义数组二叉树

// SliceBinaryTree 二叉树数组表示
type SliceBinaryTree struct {
	// 因为表示任意二叉树需要有 nil,所以类型为 any
	Tree []any
}

// NewSliceBinaryTree 构建数组二叉树
func NewSliceBinaryTree(tree []any) *SliceBinaryTree {
	return &SliceBinaryTree{
		Tree: tree,
	}
}

4.2 数组二叉树的基本操作

二叉树的数组表示主要有以下优点。

  • 数组存储在连续的内存空间中,对缓存友好,访问与遍历速度较快。

  • 不需要存储指针,比较节省空间。

  • 允许随机访问节点。

然而,数组表示也存在一些局限性。

  • 数组存储需要连续内存空间,因此不适合存储数据量过大的树。

  • 增删节点需要通过数组插入与删除操作实现,效率较低。

  • 当二叉树中存在大量 None 时,数组中包含的节点数据比重较低,空间利用率较低。

5. 二叉搜索树

5.1 定义二叉搜索树

二叉搜索树

  1. 对于根节点,左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值。

  2. 任意节点的左、右子树也是二叉搜索树,即同样满足条件 1.

// BinarySearchTree 定义二叉搜索树
type BinarySearchTree struct {
	root *TreeNode
}

func NewBinarySearchTree() *BinarySearchTree {
	return &BinarySearchTree{
		root: nil,
	}
}

5.2 二叉搜索树的插入,删除,查找

  • 代码实现

// InsertInto 插入
func (b *BinarySearchTree) InsertInto(value int) {
	curNode := b.root
	// 若树为空,初始化根节点
	if curNode == nil {
		b.root = NewTreeNode(value)
		return
	}

	// 待插入节点之前的节点
	var pre *TreeNode = nil
	// 循环查找
	for curNode != nil {
		if curNode.Value == value {
			return
		}
		if curNode.Value < value {
			pre = curNode
			curNode = curNode.Right
		} else {
			pre = curNode
			curNode = curNode.Left
		}
	}
	// 插入节点
	node := NewTreeNode(value)
	if pre.Value < value {
		pre.Right = node
	} else {
		pre.Left = node
	}
}

// 删除

// Search 查询
func (b *BinarySearchTree) Search(value int) *TreeNode {
	curNode := b.root
	for curNode != nil {
		if curNode.Value < value {
			curNode = curNode.Right
		}
		if curNode.Value > value {
			curNode = curNode.Left
		}
		if curNode.Value == value {
			return curNode
		}
	}
	return nil
}
  • 测试

func TestNewBinarySearchTree(t *testing.T) {
	// 初始化二叉树根节点
	binarySearchTreeRoot := NewBinarySearchTree()
	binarySearchTreeRoot.InsertInto(5)
	binarySearchTreeRoot.InsertInto(2)
	binarySearchTreeRoot.InsertInto(1)
	binarySearchTreeRoot.InsertInto(7)
	//
	//fmt.Println(tree.root.Value)
	//fmt.Println(tree.root.Left.Left.Value)
	//fmt.Println(tree.root.Value)
	//fmt.Println(tree.root.Right.Value)

}

6. AVL 树

0

评论区