首页  

数据结构之树的性质     所属分类 DS 浏览量 32
节点的度 Degree  节点拥有的子树数
树的度 该树中节点的最大度数
度为零的节点称为叶子(Leaf)或终端节点
度不为零的节点称为分支节点或非终端节点

孩子(Child) 双亲(Parents)  兄弟 (Sibling)
祖先(Ancestor) 子孙(Descendant)

节点的层数(Level) 树的高度(Height) 深度(Depth)
节点的层数(Level)从根起算  根的层数为 1

任意一棵二叉树中,终端节点数为 n0,度为 2 的节点数为 n2,则 n0=n2+1

结点数=总度数+1

度数为m的树和m叉树的区别


度为m的树
任意节点的度<=m
至少有一个节点度为m
一定是非空树 , 至少m+1 个节点  

m叉树 
每个节点最多只能有m个孩子  
任意节点的度<=m
允许所有节点的度小于m
可以是空树

度为m的树,第i层 最多有 m^(i-1) 个节点

高度为h的m叉树 最多有 (m^h - 1)/(m-1) 个节点
高度为h的m叉树 最少有 h 个节点
高度为h的 度为m的树 最少有 h+m-1 个节点

具有n个节点的m 叉树 最小高度为 ceil(logm(n(m-1)+1))  

二叉排序树(二叉搜索数 二叉查找树)
每个结点的左孩子都比该结点小,右孩子都比该结点大

平衡二叉树  
平衡因子(BF)  左右子树 高度差不超过1
满二叉树    每一层都是满的
完全二叉树  满二叉树最后一层少右边结点 ,叶子结点只能出现在最后两层

红黑树 近似平衡的二叉搜索树

任何一颗二叉树的叶子结点在先序 中序 后序遍历序列中的相对次序 不变 
相对次序发生变化的都是分支结点

上一篇     下一篇
算法导论第二版中文目录

《算法图解》笔记

数据结构图基础

常用数据结构

概率论词汇

线性代数词汇