数据结构 - 树

树

• 一对多的非线性结构
• 没有前驱的元素称为树的根Root
• 结点:树中的数据元素
• 结点的度degree:结点的子树的数目 记作d(v)
• 树的度:树内各结点度的最大值
• 叶子结点leaf:度为0的结点 又称终端结点 末端结点
• 孩子结点Child:子树的根节点
• 双亲结点Parent:一个结点是它各子树根节点的双亲
• 结点的层次Level:根节点为第一层 根的孩子为第二层 以此类推 记作L(v)
• 树的深度Depth:树的层次的最大值
• 有序树 结点子树有序 不可交换
• 路径长度:路径节点数-1 又称作分支数
• 森林:m(m>=0)棵不相交的树的集合

树的特点总结

• 只有一个根
• 子树不相交
• 除根结点以外 其他结点只有一个前驱 但可有零个或多个后继
• 根结点无前驱 叶子结点无后继
• 若L(vi)=L(vj)-1 则vi是vj的双亲 双亲比孩子少一层

二叉树

• 每个结点最多两棵子树
• 左右子树有序 不可换位
• 即使只有一棵子树 也要确定左右
• 左斜树:所有结点都只有左子树
• 右斜树:所有结点都只有右子树

满二叉树

• 所有分支结点都有左右子树,且叶子结点只在最下一层
• 深度为k的满二叉树结点数为2^k-1

完全二叉树 Complete Binary Tree

• 深度为k 则第一到第k-1层为满二叉树 最后一层所有结点都集中在左侧 且没有空位
• 深度为k的完全二叉树结点范围[ 2^(k-1) +1,2^k-1]
• 满二叉树一定是完全二叉树 反之则不成立
• 当完全二叉树结点数取得最大值时 即为满二叉树

二叉树性质

1. 二叉树第i层最多有2^(i-1)个结点
2. 深度为k二叉树结点范围[k , 2^k-1] (取下限为斜树 取上限为满二叉树)
3. 1. 若终端结点为n0 度为2的结点为n2 则n0 = 1 + n2
   2. 证明:结点总数n = n0 + n1 + n2
   3. 分支数B = n - 1 = n0 + n1 + n2 - 1
   4. 分支数B = 0 * n0 + 1 * n1 + 2 * n2
   5. 即 n0 + n1 + n2 - 1 = n1 + 2 * n2
   6. 化简得 n0 = 1 + n2
4. 1. 深度为k的二叉树 至少有k个结点(斜树)
   2. n个结点的二叉树深度最大为n (斜树)
   3. n个结点的二叉树深度最小为math.ceil(log2 (n+1))
5. n个结点完全二叉树的深度为int(log2 n)+1 或 math.ceil(log2 (n+1))
6. 按从上到下 从左到右 从1开始对完全二叉树结点编号 设结点序数为i 结点总数为n

   

   1. 根结点的i值为1
   2. i>1 其双亲结点i值为 int(i/2)
   3. 若父结点为i且存在左右孩子 则左孩子结点为2i 右孩子结点为2i+1
   4. 若2i>n 则结点i无左孩子,即结点i为叶子结点 若2i+1>n 则结点i无右孩子