数据结构java第六章
2019-06-19 13:25:18 10 举报AI智能生成
数据结构java第六章
作者其他创作
大纲/内容
树的定义
由n各节点构成的有限集合
双亲节点或父母节点
节点上面的相邻接点,或指节点的前驱结点
孩子节点
任何一个以n作为双亲结点的结点,或指结点n的后继结点
树的根
有且只有一个特定结点,没有双亲结点
祖先结点
包括n的双亲结点,n的双亲结点的双亲结点
兄弟结点
两结点共有一个双亲结点
叶子结点
没有孩子结点的结点
结点n的度
n的孩子结点的数量
树的度
树中所有结点的最大度数
二叉树的重要性质
根结点的层次为1 , 则二叉树的第i层最多有2^(i - 1)个结点
高度为h的二叉树中,最多有2^h - 1个结点
设一棵二叉树的叶子结点数为n0 , 2度结点数为n2 , 则 n0 = n2 + 1
设二叉树结点个数n , 1度结点个数 n1 , 则n = n0 + n1 + n2 且 n = n1 + 2*n2 + 1
满二叉树
一棵高度为h且有2^h - 1个结点的二叉树称为满二叉树
完全二叉树
删除高度为h的满二叉树中第h层的0个或多个最右边叶结点的树
如果深度为h、由n个结点的二叉树中每个结点能够与深度为h的顺序编号的满二叉树从1到n标号的结点相对应，则称这样的二叉树为完全二叉树
Huffman树的构造
0 条评论
下一页
