数据存储(数据结构)
2020-09-21 11:20:25 13 举报
AI智能生成
数据结构整理,包含数组、链表、栈、队列、树、图
作者其他创作
大纲/内容
物理结构
线性存储结构
数组
链式存储结构
链表
逻辑结构
线性结构
顺序表
散列表(哈希表)
栈
队列
优先队列
最大优先队列
无论入队顺序如何,都是当前最大的元素优先出队
最小优先队列
无论入队顺序如何,都是当前最小的元素优先出队
非线性结构
树
二叉树
二叉树类型
满二叉树
完全二叉树
图示
二叉堆
最大堆
任何一个父节点的值,都大于或等于它左、右孩子节点的值
最小堆
任何一个父节点的值,都小于或等于它左、右孩子节点的值
二叉查找树 Binary serarch tree
[又称 二叉排序树 Binary sort tree]
O(logn)
[又称 二叉排序树 Binary sort tree]
O(logn)
在二叉树基础上添加条件:
1.如果左子树不为空,则左子树上所有节点的值均小于根节点的值
2.如果右子树不为空,则右子树上又有节点的值均大于根节点的值
3.左右子树也都是二叉查找树
1.如果左子树不为空,则左子树上所有节点的值均小于根节点的值
2.如果右子树不为空,则右子树上又有节点的值均大于根节点的值
3.左右子树也都是二叉查找树
自平衡问题衍生出如下树结构
红黑树
AVL树
树堆
二叉树的遍历
广度优先遍历
层序遍历
从根节点到叶子结点,一层层横向遍历
黑色数字即为遍历顺序(拍摄于小灰漫画算法)
深度优先遍历
前序遍历
输出顺序:根节点、左子树、右子树
黑色数字即为遍历顺序(拍摄于小灰漫画算法)
中序遍历
输出顺序:左子树、根节点、右子树
黑色数字即为遍历顺序(拍摄于小灰漫画算法)
后序遍历
输出顺序:左子树、右子树、根节点
黑色数字即为遍历顺序(拍摄于小灰漫画算法)
图
0 条评论
下一页