首页  思维导图  详情



 



树与二叉树

2021-08-27 12:35:05   1  举报





AI智能生成

数据结构树于二叉树知识纲要

数据结构思维导图

模板推荐

作者其他创作

大纲/内容

树的基本概念

树的定义

性质

二叉树的概念

存储结构

顺序存储结构

完全二叉树

满二叉树

链式存储结构

性质

n个结点的二叉链表，共有n+1个空链域

二叉树共有5种形态

非空二叉树的   叶子结点数=度为2的结点数+1

非空二叉树第K层最多2^(k-1)个结点

高度为h的二叉树共有2^h-1个结点

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

二叉树的遍历 （遍历算法和程序实现）

先序遍历

根左右

中序遍历

左根右

后序遍历

左右根

层次遍历

由遍历序列构造二叉树

前+中

后+中

层+中

线索二叉树 （物理结构）

概念

指向结点前驱和后继的指针称为线索

typedef struct ThreadNode{              int data;              struct ThreadNode *lchild,*rchild;              int ltag,rtag; }ThreadNode,*ThreadTree;

为了加快查找结点的前驱和后继

先序线索二叉树

不能有效解决先序前驱的问题

中序线索二叉树

后序线索二叉树

不能有效解决后序后继的问题

树、森林

树的存储结构

顺序存储

双亲表示法

需要一组连续的地址空间来存储每个节点，同时在每个结点添加一个伪指针，用来标明双亲结点在数组中的位置

链式存储

孩子兄弟表示法

左孩子右兄弟

孩子表示法

将每个结点用单链表链接起来形成一个线性结构

树、二叉树和森林的转换

P163见图5.17

树和森林的遍历

树与二叉树的应用

二叉排序树（BST）

若BST是一个只有左（右）孩子的单支树，则其平均查找长度O(n)

平衡二叉树

BST左右子树高度之差的绝对值不超过1,平均查找长度O(log n)

插入

LL平衡旋转(右单旋转)

在A的左孩子的左子树插入导致不平衡

RR平衡旋转

LR平衡旋转(先左后右双旋转)

RL平衡旋转(先右后左双旋转)

哈夫曼树和哈夫曼编码

在含有n个带权叶结点的二叉树中，WPL最小的二叉树称为哈夫曼树

构造

哈夫曼编码

前缀编码

没有一个编码是其他编码的前缀

哈夫曼树不唯一，因此哈夫曼编码不唯一

 Collect

Get Started

二叉树题目整理

 Collect

Get Started

二叉树

 Collect

Get Started

考研树与二叉树知识点笔记总结

 Collect

Get Started

二叉树





0 条评论

下一页