数据结构
2020-02-17 16:48:31 51 举报
AI智能生成
登录查看完整内容
数据结构
作者其他创作
大纲/内容
树与二叉树
二叉树的定义
二叉树每个结点最多有两棵子树
二叉树的子树有严格的左右之分
二叉树允许只有右(左),而没左(右)子树
二叉树的性质
二叉树中的第i(i>=0)层上的结点数最多为2^n
深度为h(h>=1)的二叉树中最多有2^h-1个结点
具有n个结点的完全二叉树,其深度为(log2^n)+1 或者 (log2^(n+1))
满二叉树
所有结点(叶结点)都非空,满
完全二叉树
在满二叉树的基础上,从右到左,有序减掉0-n个叶结点
二叉树的存储结构
顺序存储
链式存储
二叉链表
三叉链表
二叉树的遍历
树的广度优先遍历(层次遍历)
树的深度优先遍历
先根遍历
递归
非递归
二叉树中查找值为x的结点
中根遍历
后根遍历
求二叉树的深度
哈夫曼树
最优二叉树
构造方法
结点描述
已知构造有n个字符编码的哈夫曼树,则哈夫曼树的结点个数为 2n-1
树与二叉树的转换
树的后根遍历操作对应二叉树的中根遍历操作
树转换为二叉树后只有左子树
排序
外排序
内排序
插入类
直接插入排序 O(n^2)
不带监视哨
带监视哨
是稳定的排序方式
希尔排序
实际上是缩小增量的直接插入排序
是不稳定的排序方式
交换类
选择类
归并类
其他类
数据结构
栈与队列
栈
队列
顺序队列
循环顺序队列
循环队列包含的属性
front(队首指针)
rear(队尾指针)
Object[] queueElem (队列储存空间)
flag(标记)
num(计数器)
构造方式
少用一个存储单元
判空:front==rear
判满:front==(rear+1)%maxSize
求队列长度:(rear-front+length) % length
入队
修改队尾指针:rear=(rear+1) % length
出队
修改队首指针:front= (front+1) % length
设置一个标志变量(flag)
判空: front==rear && flag==0
判满:front==rear && flag==1
修改标志(flag=1)
设置标志(flag=0)
设置一个计数器(num)
判空:num=0
判满:num>0 && front==rear
++num
--num
自由主题
0 条评论
回复 删除
下一页