小C的第一宇宙
wangc
May 2, 2017
阅读本文需要 20 分钟(按字数)

定义

  • 查找:根据某个关键字K,从集合R中找出关键字与K相同的记录。
    • 静态查找:集合中记录是固定的
      • 没有插入个删除操作,只有查找
    • 动态查找:集合中记录是动态变化的
      • 除查找,还可能发生插入和删除
  • 树(tree):n(n>=0)个节点构成的有限集合。当n=0时,称为空树,对于任一颗非空树(n>0)它具备以下性质:
    • 书中有一个称为根(Root)的特殊节点,用r表示;
    • 其余节点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一个集合本身又是一棵树,称为原来树的子树(SubTree)
  • 二叉树T:一个有穷的结点集合。这个集合可以为空若不为空,则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。
  • 完全二叉树 (Complete Binary Tree) 有n个结点的二叉树,对树中结点按 从上至下、从左到右顺序进行编号, 编号为i( 1 ≤ i ≤ n)结点与满二叉树 中编号为 i 结点在二叉树中位置相同
  1. 结点的度( Degree):结点的子树个数
  2. 树的度:树的所有结点中最大的度数
  3. 叶结点( Leaf): 度为0的结点
  4. 父结点( Parent):有子树的结点是其子树的根结点的父结点
  5. 子结点( Child):若A结点是B结点的父结点,则称B结点是A结点的子结点;子结点也称孩子结点。
  6. 兄弟结点( Sibling):具有同一父结点的各结点彼此是兄弟结点。
  7. 路径和路径长度:从结点n1到nk的路径为一 个结点序列n1 , n2 ,… , nk , ni是 ni+1的父结 点。路径所包含边的个数为路径的长度。
  8. 祖先结点(Ancestor):沿树根到某一结点路 径上的所有结点都是这个结点的祖先结点。
  9. 子孙结点(Descendant):某一结点的子树 中的所有结点是这个结点的子孙。
  10. 结点的层次( Level):规定根结点在1层, 其它任一结点的层数是其父结点的层数加1。
  11. 树的深度( Depth) :树中所有结点中的最大层次是这棵树的深度

性质

  • 一个二叉树第 i层的最大结点数为: 2^(i-1), i >= 1。
  • 对任何非空二叉树T,若n0表示叶结点的个数、n2是度为2的非叶结点个数,那么两者满足关系n0 = n2 +1。
  • 深度为k的二叉树有最大结点总数为: 2^(k-1), k >= 1。

    应用

    :表示客观世界中的层次信息,而分层次组织在管理上具有更高的效率。

抽象类型定义

  • 名称:二叉树
  • 数据对象集:一个有穷的结点集合。若不为空,则由根结点和其左、右二叉子树组成。
  • 操作集: BT∈ nTree, Item∈ElementType,重要操作有:
    1. Boolean IsEmpty( BinTree BT ): 判别BT是否为空;
    2. void Traversal( BinTree BT ):遍历,按某顺序访问每个结点;
      1. void PreOrderTraversal( BinTree BT ):先序—-根、左子树、右子树;
      2. void InOrderTraversal( BinTree BT ):中序—左子树、根、右子树;
      3. void PostOrderTraversal( BinTree BT ):后序—左子树、右子树、根
      4. void LevelOrderTraversal( BinTree BT ): 层次遍历,从上到下、从左到右
    3. BinTree CreatBinTree( ):创建一个二叉树。

存储结构

完全二叉树可以用顺序结构存储,一般用链式结构存储。

typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
}

二叉搜索树( BST )

定义\ 二叉搜索树:一棵二叉树,可以为空;如果不为空,满足以下性质:

  1. 非空左子树的所有键值小于其根结点的键值。
  2. 非空右子树的所有键值大于其根结点的键值。
  3. 左、右子树都是二叉搜索树。

存储结构

typedef struct node  
{  
    int key;  
    struct node *lChild, *rChild;  
}Node, *BST;  

二叉搜索树的查找操作

  • 查找从根结点开始,如果树为空,返回NULL
  • 若搜索树非空,则根结点关键字和X进行比较, 并进行不同处理:
    • 若X小于根结点键值,只需在左子树中继续搜索;
    • 如果X大于根结点的键值, 在右子树中进行继续搜索;
    • 若两者比较结果是相等,搜索完成,返回指向此结点的指针。
Position Find( ElementType X, BinTree BST )
{
    if( !BST ) return NULL; /*查找失败*/
    if( X > BST->Data )
        return Find( X, BST->Right ); /*在右子树中继续查找*/
    Else if( X < BST->Data )
        return Find( X, BST->Left ); /*在左子树中继续查找*/
    else /* X == BST->Data */
        return BST; /*查找成功, 返回结点的找到结点的地址*/
}

由于非递归函数的执行效率高,可将“尾递归” 函数改为迭代函数


Position IterFind( ElementType X, BinTree BST )
{
    while( BST ) {
    if( X > BST->Data )
        BST = BST->Right; /*向右子树中移动, 继续查找*/
    else if( X < BST->Data )
        BST = BST->Left; /*向左子树中移动, 继续查找*/
    else /* X == BST->Data */
        return BST; /*查找成功, 返回结点的找到结点的地址*/
    }
        return NULL; /*查找失败*/
}

查找最大和最小元素

  • 最大元素一定是在树的最右分枝的端结点上
  • 最小元素一定是在树的最左分枝的端结点上
/* 查找最小元素的递归函数 */

Position FindMin( BinTree BST )
{
    if( !BST ) return NULL; /*空的二叉搜索树,返回NULL*/
    else if( !BST->Left )
        return BST; /*找到最左叶结点并返回*/
    else
        return FindMin( BST->Left ); /*沿左分支继续查找*/
}
/* 查找最大元素的迭代函数 */
Position FindMax( BinTree BST )
{
    if(BST )
    while( BST->Right ) BST =         BST->Right;
    /*沿右分支继续查找,直到最右叶结点*/
        return BST;
}

二叉搜索树的插入

关键是要找到元素应该插入的位置, 可以采用与Find类似的方法

BinTree Insert( ElementType X, BinTree BST )
{
    if( !BST ){
    /*若原树为空, 生成并返回一个结点的二叉搜索树*/
        BST = malloc(sizeof(struct TreeNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    }else /*开始找要插入元素的位置*/
    if( X < BST->Data )
        BST->Left = Insert( X, BST->Left);
    /*递归插入左子树*/
    else if( X > BST->Data )
        BST->Right = Insert( X, BST->Right);
    /*递归插入右子树*/
    /* else X已经存在, 什么都不做 */
        return BST;
}

二叉搜索树的删除

  • 要删除的是叶结点: 直接删除, 并再修改其父结点指针—置为NULL
  • 要删除的结点只有一个孩子结点: 将其父结点的指针指向要删除结点的孩子结点
  • 要删除的结点有左、右两棵子树: 用另一结点替代被删除结点: 右子树的最小元素 或者 左子树的最大元素
BinTree Delete( ElementType X, BinTree BST )
{   Position Tmp;
    if( !BST ) printf("要删除的元素未找到");
    else if( X < BST->Data )
        BST->Left = Delete( X, BST->Left); /* 左子树递归删除 */
    else if( X > BST->Data )
        BST->Right = Delete( X, BST->Right); /* 右子树递归删除 */
    else /*找到要删除的结点 */
    if( BST->Left && BST->Right ) { /*被删除结点有左右两个子结点 */
        Tmp = FindMin( BST->Right );
    /*在右子树中找最小的元素填充删除结点*/
        BST->Data = Tmp->Data;
        BST->Right = Delete( BST->Data, BST->Right);
    /*在删除结点的右子树中删除最小元素*/
    } else { /*被删除结点有一个或无子结点*/
        Tmp = BST;
    if( !BST->Left ) /* 有右孩子或无子结点*/
        BST = BST->Right;
    else if( !BST->Right ) /*有左孩子或无子结点*/
        BST = BST->Left;
        free( Tmp );
    }
    return BST;
}

平衡二叉树( AVL树)

基本概念

  • 平衡二叉树( Balanced Binary Tree)( AVL树) 空树,或者任一结点左、右子树高度差的绝对值不超过1,即|BF(T) |≤ 1

  • 平衡因子( Balance Factor,简称BF) : BF(T) = hL-hR,其中hL和hR分别为T的左、右子树的高度。

规律

  • 给定结点数为 n的AVL树的 最大高度为O(log2n)!

平衡操作

typedef int ElementType;
typedef struct AVLNode *Position;
typedef Position AVLTree; /* AVL树类型 */
struct AVLNode{
    ElementType Data; /* 结点数据 */
    AVLTree Left;     /* 指向左子树 */
    AVLTree Right;    /* 指向右子树 */
    int Height;       /* 树高 */
};
 
int Max ( int a, int b ){ return a > b ? a : b; }
int GetHeight( AVLTree A ){ return A->Height; } 

AVLTree SingleLeftRotation ( AVLTree A )
{ /* 注意:A必须有一个左子结点B */
  /* 将A与B做左单旋,更新A与B的高度,返回新的根结点B */     
 
    AVLTree B = A->Left;
    A->Left = B->Right;
    B->Right = A;
    A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) + 1;
    B->Height = Max( GetHeight(B->Left), A->Height ) + 1;
  
    return B;
}

AVLTree SingleRightRotation ( AVLTree A )
{    
    AVLTree B = A->Right;
    A->Right = B->Left;
    B->Left = A;
    A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) + 1;
    B->Height = Max( GetHeight(B->Left), A->Height ) + 1;
  
    return B;
}

AVLTree DoubleLeftRightRotation ( AVLTree A )
{ /* 注意:A必须有一个左子结点B,且B必须有一个右子结点C */
  /* 将A、B与C做两次单旋,返回新的根结点C */
     
    /* 将B与C做右单旋,C被返回 */
    A->Left = SingleRightRotation(A->Left);
    /* 将A与C做左单旋,C被返回 */
    return SingleLeftRotation(A);
}
 
AVLTree DoubleRightLeftRotation ( AVLTree A )
{      
    A->Right = SingleLeftRotation(A->Right);
    return SingleRightRotation(A);
}
 
AVLTree Insert( AVLTree T, ElementType X )
{ /* 将X插入AVL树T中,并且返回调整后的AVL树 */
    if ( !T ) { /* 若插入空树,则新建包含一个结点的树 */
        T = (AVLTree)malloc(sizeof(struct AVLNode));
        T->Data = X;
        T->Height = 0;
        T->Left = T->Right = NULL;
    } /* if (插入空树) 结束 */
 
    else if ( X < T->Data ) {
        /* 插入T的左子树 */
        T->Left = Insert( T->Left, X);
        /* 如果需要左旋 */
        if ( GetHeight(T->Left)-GetHeight(T->Right) == 2 )
            if ( X < T->Left->Data ) 
               T = SingleLeftRotation(T);      /* 左单旋 */
            else 
               T = DoubleLeftRightRotation(T); /* 左-右双旋 */
    } /* else if (插入左子树) 结束 */
     
    else if ( X > T->Data ) {
        /* 插入T的右子树 */
        T->Right = Insert( T->Right, X );
        /* 如果需要右旋 */
        if ( GetHeight(T->Left)-GetHeight(T->Right) == -2 )
            if ( X > T->Right->Data ) 
               T = SingleRightRotation(T);     /* 右单旋 */
            else 
               T = DoubleRightLeftRotation(T); /* 右-左双旋 */
    } /* else if (插入右子树) 结束 */
 
    /* else X == T->Data,无须插入 */
 
    /* 别忘了更新树高 */
    T->Height = Max( GetHeight(T->Left), GetHeight(T->Right) ) + 1;
     
    return T;
}