远方的岛第三章 树与二叉树
type
status
date
slug
summary
tags
category
icon
password
3.1树与二叉树的基本术语
树：构造性递归定义、逻辑结构特点
结点的度、树的度、叶子结点、分支结点
孩子结点、双亲结点、兄弟
路径、路径长度、祖先、子孙
结点的层数、树的深度
有序树、无序树、森林
n - 1
A
B
3.2二叉树
定义、结构特点
斜树、满二叉树、完全二叉树
二叉查找树BST、平衡二叉树AVL
二叉树的性质
C
B
C
D
二叉树的遍历
先序遍历（根左右）、中序遍历（左根右）、后序遍历（左右根）、层序遍历
二叉树的恢复算法
前中序、中后序可唯一确定一棵二叉树（打配合）
前后序不能唯一确定
二叉树的基本操作
二叉树的存储结构
二叉树的顺序存储结构：完全（满）、一般
二叉树的左右链存储结构
建立：先序递归、非递归
遍历（核心）
递归：先序、中序、后序
非递归：先序、中序（指针入栈）、后序（指针和标志入栈）、层序（队列）
应用举例：二叉树结点个数、高度、交换所有结点子树（递归、非递归：栈）、先序打印叶子结点
二叉树的其他链式存储结构
动态三叉链表、静态二叉/三叉链表
B
C
D
C
线索二叉树
A
C
逻辑结构：集合、线性、树形、图形
存储（物理）结构：顺序、链式、索引、散列
线索二叉树的若干算法
先先前、后后后，得遍历
二叉树的复制
dbca D
D
A
debxac D
B
二叉树的计数
3.3堆
完全二叉树：最大堆、最小堆
3.4选择树
完全二叉树：胜者树、败者树
3.5树
基本操作、遍历操作
存储结构
双亲表示法、孩子链表表示法（邻接表）、二叉链表表示法（左孩子-右兄弟链表表示）：把树转换为二叉树
3.6森林（树）与二叉树间的转换
B
D
C
C
B
3.7树的应用
一、哈夫曼树
路径长度、树的路径长度：从树根到每一结点的路径长度之和
结点带权的树
结点的带权路径长度、树的带权路径长度：树中所有叶子结点的带权路径长度之和
哈夫曼树：带权路径长度WPL最小的二叉树，最优二叉树
存储结构：静态三叉链表
构造算法
哈夫曼编码：前缀编码
二、表达式求值
三、情感分析的搭配抽取任务
期末真题
2021
B
中序序列中的后继结点
2019
不能
2017
B
2016
D
B
C
n + 1 你画一个试试不就完了吗！
Loading...