二叉树的性质介绍

二叉树的性质介绍

性质一

  1. 非空二叉树的叶子节点等于双分支节点数加一
    • 总分支数 = 总结节点数 + 1

性质二

  1. 二叉树的第 i 层，最多有 2^{i-1} 个节点
    • 节点最多时，为满二叉树

性质三

  1. 高度（或深度）为 k 的二叉树，最多有 2^k-1 个节点
    • 满二叉树的前 k 层的节点数为 2^k-1 个节点

性质四

  1. 具有 n 个节点的完全二叉树（若 i 为节点 a 的编号）
    • 若 i\not=1 ，则 a 的双亲节点为 \lfloor{i/2}\rfloor
    • 若 2i\leq{n} ，则 a 的左孩子的编号为 2i ；若 2i>{n} ，则 a 没有左孩子
    • 若 2i+1\leq{n} ，则 a 的右孩子的编号为 2i+1 ；若 2i+1>{n} ，则 a 没有右孩子
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。