王道数据结构复习总结笔记---树（上）
登录 / 注册
侧边栏壁纸
博主昵称
yjprolus

  • 累计撰写 40 篇文章
  • 累计收到 134 条评论
计基

王道数据结构复习总结笔记---树（上）

yjprolus
yjprolus
2022-02-04 / 2 评论 / 15 阅读 / 正在检测是否收录...

5.1树的基本概念

5.1.1树的定义和基本术语

基本概念

在这里插入图片描述
树形逻辑结构的应用
在这里插入图片描述

属性描述

在这里插入图片描述

概念区分

在这里插入图片描述

总结

在这里插入图片描述

5.1.2树的性质

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

总结

在这里插入图片描述

5.2二叉树的概念

5.2.1 二叉树的定义和基本术语

在这里插入图片描述

几个特殊的二叉树

满二叉树和完全二叉树

在这里插入图片描述

二叉排序树

在这里插入图片描述

平衡二叉树

在这里插入图片描述

总结

在这里插入图片描述

5.2.2二叉树的性质

一般二叉树

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

完全二叉树的性质

在这里插入图片描述

总结

突破点：完全二叉树最多只会有一个度为1的结点

在这里插入图片描述

5.2.3二叉树的存储结构

顺序存储

二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来。
在这里插入图片描述
二叉树的顺序存储结构，只适合存储完全二叉树
在这里插入图片描述

链式存储

n个结点的二叉链表共有 n+1 个空链域
在这里插入图片描述
三叉链表——方便找父结点
在这里插入图片描述

总结

在这里插入图片描述

5.3二叉树的遍历和线索二叉树

5.3.1二叉树的先中后序遍历

层次遍历

在这里插入图片描述

先/中/后序遍历：基于树的递归特性

先序遍历：根左右（NLR）
中序遍历：左根右（LNR）
后序遍历：左右根（LRN）
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

代码

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

递归遍历的手算法

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

例：求树的深度（应用）

在这里插入图片描述

总结

在这里插入图片描述

5.3.2二叉树的层次遍历

在这里插入图片描述

总结

在这里插入图片描述

5.3.3由遍历序列构造二叉树

不同二叉树的遍历序列

在这里插入图片描述
若只给出一棵二叉树的 前/中/后/层 序遍历序列中的一种，不能唯一确定一棵二叉树

由遍历序列构造二叉树

在这里插入图片描述

前序 + 中序遍历序列

在这里插入图片描述
在这里插入图片描述

后序 + 中序遍历序列

在这里插入图片描述

层序 + 中序遍历序列

在这里插入图片描述
在这里插入图片描述

总结

在这里插入图片描述
前序、后序、层序序列的两两组合无法唯一确定一科二叉树（必须有个中序）

5.3.4线索二叉树的概念

作用

在这里插入图片描述

存储结构

在这里插入图片描述

三种线索二叉树

中序线索二叉树

在这里插入图片描述

先序线索二叉树

在这里插入图片描述

后序线索二叉树

在这里插入图片描述

对比

在这里插入图片描述

总结

在这里插入图片描述

0
暂无标签
版权属于： yjprolus
本文链接： https://yjprolus.top/post/18.html
作品采用： 《 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 》许可协议授权

评论 (2)

取消
  1. 头像
    煎子
    Windows 7 · Google Chrome

    支持支持

    回复
  2. 头像
    捶你一下可以吗
    Windows 7 · Google Chrome

    前排观摩大佬

    回复