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

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

开发者学堂课程【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)

}

相关文章
|
3月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
73 1
|
3月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
83 0
|
7月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
189 10
 算法系列之数据结构-二叉树
|
7月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
158 3
 算法系列之数据结构-Huffman树
|
7月前
|
算法 Java
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
196 22
|
8月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
200 30
|
8月前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
313 25
|
8月前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
286 23
|
9月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
186 12
|
9月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
166 10