树和二叉树的定义

ゞ浴缸里的玫瑰 2022-05-24 12:24 174阅读 0赞

*  树的概念  
    
    
     *  子节点和父节点（是相对定义的）：  
        一棵树的根节点称为该树的子树的根节点的父节点  
        子树的根是树根的子节点
     *  边：从父节点到子节点的连线（边有方向）
     *  兄弟节点：父节点相同的节点互为兄弟节点
     *  树叶、分支节点：没有子节点的节点称为树叶，树中的其余节点称为分支节点（分支节点可只有一个分支）
     *  祖先和子孙：基于父节点/子节点关系和传递性，可以确定相应的传递关系，称为祖先关系或子孙关系
     *  度数：一个节点的子节点个数称为该节点的度数
     *  路径、路径长度：  
        从一个祖先节点到其子孙节点的一系列边称为树中一条路径（从一棵树的根到树中任一个节点都有唯一路径）  
        路径中边的条数称为路径的长度，认为每个节点到自身有长0的路径
     *  节点的层数：  
        树根到节点的路径长度是该节点的层数  
        节点都有层数，根所在的层为0
     *  高度（或深度）：  
        树的高度或深度是树中节点的最大层数（最长路径的长度）加1  
        空树高度为0，只有根节点的树高度为1
 *  二叉树的定义：
    
     *  二叉树是一种树形结构：  
        特点是与每个节点关联的子节点至多有两个（可为0,1,2）  
        每个节点的子节点有关联位置关系
     *  定义：  
        二叉树是节点的有限集合，该集合或为空集，或由一个根元素和两棵不相交的二叉树组成（递归定义）  
        二叉树的两棵子树分别称为它的左子树和右子树
     *  二叉树的5种基本形态：  
        ![这里写图片描述][70]
     *  满的和完全的二叉树：  
        
        
         *  满二叉树：树中每个分支节点（非叶节点）都有两棵非空子树
         *  完全二叉树：除最下两层外，其余节点度数都是2，如果最下面的节点不满，则所有空位都在右边，左边没有空位，如下图  
            ![这里写图片描述][70 1]
         *  扩充二叉树（由已有非空二叉树生成的一种二叉树）：  
            是原二叉树的最小节点扩充，使原树中所有节点的度数都变成2  
            ![这里写图片描述][70 2]
     *  二叉树的性质：  
        
        
         *  性质1. 非空二叉树第 i 层上至多有 2i 个结点（i ≥ 0）
         *  性质2. 高度为 k 的二叉树至多有 2k-1 个结点（k ≥ 0)
         *  性质3. 对任何非空二叉树 T，若其叶结点个数为 n0，度数为 2 的结点  
            个数为 n2，则n0 = n2 + 1
         *  性质4. n 个结点的完全二叉树的高度 k = ⎡log2(n+1)⎤
         *  性质5. 满二叉树里的叶结点比分支结点多一个
 *  二叉树的数据结构  
    
    
     *  基本操作  
        
    
    > 创建二叉树  
    > 一棵二叉树或为空（用 None 表示），或是两棵已有二叉树和要存在树根结点的一项数据，构造起的根结点代表构造出的二叉树：  
    > BiTree(dat, left, right)  
    > 判断树空：is\_empty(bitree)  
    > 访问操作，访问二叉树的组成成分：  
    > 访问二叉树的根结点数据元素：data()  
    > 取得一棵二叉树的左右子树：right()，left()

[70]: /images/20220524/16ec1e26bcdc47ad8971c05a5715755b.png
[70 1]: /images/20220524/38e847db57064ac29e29a4188803317b.png
[70 2]: /images/20220524/05eb2eedaa9e4f83bd6744dff19d35ef.png