数据结构和算法-二叉树三种遍历方式|学习笔记

简介: 快速学习数据结构和算法-二叉树三种遍历方式

开发者学堂课程【Go 语言核心编程 - 数据结构和算法: 数据结构和算法-二叉树三种遍历方式】学习笔记,与课程紧密联系,让用户快速学习知识。

课程地址:https://developer.aliyun.com/learning/course/627/detail/9869


数据结构和算法-二叉树三种遍历方式


 内容介绍

一、二叉树的示意图

二、二叉树的案例

 

一、二叉树的示意图

1. 定义:

树有很多种,每个节点最多只能有两个子节点的一种形式称为二叉树。

我们重点讲解一下二叉树的前序遍历,中序遍历和后序遍历。

image.png

 

二、二叉树的案例

1.使用前序,中序和后序对下面的二叉树进行遍历.

image.png

(1)前序遍历:是二叉树遍历的一种,也叫做先根遍历、先序遍历、前序周游,可记做根左右。前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。

packagemain

import (

"fmt"

type Hero struct {

No int

Name string

Left *Hero

Right *Hero

}

//前序遍历【先输出 root 节点,在输出左子树,然后在输出右子树】

func PreOrder(node *Hero) {

if node != nil {

fmt.Printf("no=%d name=%s\n",node.No,node.Name)

PreOrder(node.Left)

PreOrder(node.Right)

}

}

func main(){

//构建一个二叉树

root := &Hero{

No : 1,

Name:“宋江“,

}

left1 := &Hero{

No : 2,

Name:"吴用”,

}

right1 := &Hero{

No : 3,

Name:"卢俊义",

}

root.Left = left1

root.Right = right1

right2 := &Hero{

No : 4,

Name:"林冲",

}

right1.Right = right2

PreOrder(root)

}

(2)思考:

image.png

这回输出顺序为“宋江”,“吴用”,“10”,“12”,“卢俊义”,“林冲”。

(3)中序遍历:是二叉树遍历的一种,也叫做中根遍历、中序周游。在二叉树中,中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。

packagemain

import (

"fmt"

type Hero struct {

No int

Name string

Left *Hero

Right *Hero

}

//中序遍历[先输出 root 的左子树,再输 root 的右子树,最后输出 root 的节点]

func InfixOrder(node *Hero) {

if node != nil {

InfixOrder(node.Left)

fmt.Printf("no=%d name=%s\n", node.No, node.Name)

InfixOrder(node.Right)

}

}

func main(){

//构建一个二叉树

root := &Hero{

No : 1,

Name:“宋江“,

}

left1 := &Hero{

No : 2,

Name:"吴用”,

}

right1 := &Hero{

No : 3,

Name:"卢俊义",

}

root.Left = left1

root.Right = right1

right2 := &Hero{

No : 4,

Name:"林冲",

}

right1.Right = right2

//PreOrder(root)

InfixOrder(root)

}

(4)后序遍历:是二叉树遍历的一种,也叫做后根遍历、后序周游,可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中,先左后右再根,即首先遍历左子树,然后遍历右子树,最后访问根结点。

package main

import  (

"fmt"

type Hero struct  {

No int

Name string

Left *Hero

Right *Hero

}

//序遍历[先输出 root 的左子树,再输 root 结点,最后输出 root 的右子树]

func PostOrder(node *Hero) {

if node != nil {

PostOrder(node.Left)

PostOrder(node.Right)

fmt.Printf("no=%d name=%s\n", node.No, node.Name)

}

}

func main(){

//构建一个二叉树

root := &Hero{

No : 1,

Name:“宋江“,

}

left1 := &Hero{

No : 2,

Name:"吴用”,

}

right1 := &Hero{

No : 3,

Name:"卢俊义",

}

root.Left = left1

root.Right = right1

right2 := &Hero{

No : 4,

Name:"林冲",

}

right1.Right = right2

//PreOrder(root)

InfixOrder(root)

}

相关文章
|
16天前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
27 1
|
19天前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
63 4
|
17天前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
|
17天前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
25天前
|
算法
数据结构之路由表查找算法(深度优先搜索和宽度优先搜索)
在网络通信中,路由表用于指导数据包的传输路径。本文介绍了两种常用的路由表查找算法——深度优先算法(DFS)和宽度优先算法(BFS)。DFS使用栈实现,适合路径问题;BFS使用队列,保证找到最短路径。两者均能有效查找路由信息,但适用场景不同,需根据具体需求选择。文中还提供了这两种算法的核心代码及测试结果,验证了算法的有效性。
86 23
|
16天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
42 1
|
25天前
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法,包括先序、中序、后序的递归与非递归遍历方法。通过编程实践,加深对二叉树结构的理解,学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
74 4
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
159 9
|
1月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
26 1
|
17天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
38 5

热门文章

最新文章