树和二叉树（知识整理）

1、树型结构是一类非常重要的非线性结构，
    树型结构为：分支结构、一对多、层次结构

2、树(tree)是n(n>=0)个结点的有限集合T，若n=0时称为空树，否则：
    （1）有且只有一个特殊的称为树的根（root）结点；根是入口
    （2）若n>1时，其余的结点被分为m(m>0)个互不相交的子集T1,T2,T3..,其中每个子集本身又是一棵树，称其为根的子树

3、树的定义：树的递归定义，即用树来定义树，而只有一个结点的树必定仅由根组成（树只有一个根，根是树的入口）

4、树的组成元素：结点
    结点（node）：一个数据元素及其若干指向其子树的分支
    结点的度（degree）：结点所拥有的子树的棵数
    树的度：树中结点度的最大值

    叶子（终端）结点：树中度为0的结点
    非叶子（非终端、分支）结点：度不为0的结点
    分支结点又称内部结点

    孩子结点：一个结点的子树的根称为该结点的孩子结点或子节点
    双亲结点：该结点是其孩子结点的双亲结点或父节点
    兄弟结点：同一双亲结点的所有子节点
    堂兄弟结点：双亲结点在同一层上，且不是兄弟结点的所有结点
    
    层次：规定树中根结点的层次为1，其余结点的层次等于其双亲结点的层次加1
    若某结点在第i层，则其子节点在第i+1层
    
    结点的层次路径：从根结点开始，到达某结点p所经过的所有结点称为结点p的层次路径（有且只有一条）
    结点层次：从根开始定义起，根为第一层，跟的孩子为第二层，以此类推

    p的祖先：结点p的层次路径上的所有结点（p除外）
    结点的子孙结点：一某一结点为根的子树中的任意结点

    树的深度：树中结点的最大层次值，又称树的高的）
    森林：是m(m>=0)棵互不相交的树的集合。显然，若将一棵树的根结点删除，剩余的子树就构成了森林。

    判断有序树和无序树：交换子树的顺序，是否是一个树

    
5、二叉树：是n(n>=0)个结点的有限集合。若n=0时称为空树，否则：
    （1）有且只有一个根结点
    （2）二叉树是有序的
    （3）二叉树最多两个子树

6、二叉树的5种形态：空二叉树、单结点二叉树、左子树为空、右子树为空、左右子树都不空

7、二叉树性质：
    1）在非空二叉树中，第i层上至多有2的i-1次幂个结点（i>=1)
    2）深度为k的二叉树至多有2的k次幂-1个结点
    3）对任何一棵二叉树，若其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1

8、满二叉树：每层都是满的
    对满二叉树连续编号：应层次从1开始，编号从1开始，“自上而下、自左而右”的原则进行

8、完全二叉树：与满二叉树对比
    1）对应位置、对应编号
    2）且不允许跳号

9、完全二叉树的性质：
    1）第i层，至多有2的i-1次幂个结点
    2）前k层，至多有（2的k次幂-1）个结点
    3）n0=n2+1
    4)深度为k，最多有（2的k次幂-1）个
    5）深度为k，那么前（k-1)层必须是满的，前（k-1）层有（2的k-1次幂-1）个，第k层至少有一个
    6）深度为k，所以叶子结点都出现在第k层或k-1层
    7）如果右子树最大层为j，则其左子树最大层为j或j+1
    8）n个结点的完全二叉树深度为：|log2n|+1
    9）i结点的双亲为i/2，左子树为2i，右子树为2i+1

10、只有完全二叉树才使用顺序结构

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！