首页  

数据结构之树     所属分类 DS 浏览量 102
树(tree)是包含n(n>0)个节点的有限集合 
每个元素称为节点(node)
有一个特定的节点被称为根节点或树根(root)
除根节点之外的其余数据元素被分为m(m≥0)个互不相交的集合 T1 T2 ... Tm-1
其中每一个集合Ti(1<=i<=m)本身也是一棵树,被称作原树的子树(subtree)


操作系统 红黑树
数据库 了B+树
编译器 语法树
内存管理 堆
信息论中的哈夫曼编码
Java TreeMap TreeSet  红黑树  


二叉树 满二叉树 完全二叉树 二叉查找树 BST 平衡二叉树 AVL树 堆 一颗完全二叉树
二叉树 每个结点至多只有二棵子树 左右子树 第i层至多有2^(i-1)个结点(i从1开始) 深度为k的二叉树至多有2^(k)-1)个结点 对任何一棵二叉树,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1 具有n个结点的完全二叉树的深度为log(n+1)
满二叉树 完全二叉树 满二叉树 除最后一层无任何子节点外,每一层上的所有结点都有两个子结点 完全二叉树 若设二叉树的深度为h,除第 h 层外,其它各层 (1~(h-1)层) 的结点数都达到最大个数 第h层所有的结点都连续集中在最左边 满二叉树是完全二叉树的一个特例
二叉查找树 二叉查找树,又称二叉排序树或 二叉搜索树 Binary Sort Tree BST 若左子树不空,则左子树上所有结点的值均小于其根结点的值 若右子树不空,则右子树上所有结点的值均大于或等于其根结点的值 左、右子树也分别为二叉排序树 没有键值相等的节点 中序遍历,即可得到有序的数列
平衡二叉树 平衡二叉树又称为AVL树 它是一棵空树或左右子树的高度差不超过1 解决二叉查找树不平衡导致查找效率退化为线性的问题 由 BST 的 Node 加上 height 节点高度属性 ,用于判断树是否平衡 维护树的平衡关键就在于旋转
堆 堆是一颗完全二叉树 大根堆 父节点大于等于子节点 小根堆 父节点小于等于子节点 完全二叉树 , 从上到下,从左到右 编号 通过一个节点在数组中的索引 计算 其父节点及左右孩子节点的索引 堆的用途 堆排序,优先队列 由于调整代价较小,适合实时排序与变更

上一篇     下一篇
数据结构第二章线性表

数据结构第三章栈和队列

程序员排行榜

算法导论第二版中文目录

《算法图解》笔记

数据结构图基础