数据结构 4.树

wangc

May 2, 2017

阅读本文需要 20 分钟(按字数)

定义
性质
应用
抽象类型定义
存储结构
二叉搜索树（ BST ）
平衡二叉树（ AVL树）

定义

查找：根据某个关键字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 结点在二叉树中位置相同

结点的度（ Degree）：结点的子树个数
树的度：树的所有结点中最大的度数
叶结点（ Leaf）：度为0的结点
父结点（ Parent）：有子树的结点是其子树的根结点的父结点
子结点（ Child）：若A结点是B结点的父结点，则称B结点是A结点的子结点；子结点也称孩子结点。
兄弟结点（ Sibling）：具有同一父结点的各结点彼此是兄弟结点。
路径和路径长度：从结点n1到nk的路径为一个结点序列n1 , n2 ,… , nk , ni是 ni+1的父结点。路径所包含边的个数为路径的长度。
祖先结点(Ancestor)：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点。
子孙结点(Descendant)：某一结点的子树中的所有结点是这个结点的子孙。
结点的层次（ Level）：规定根结点在1层，其它任一结点的层数是其父结点的层数加1。
树的深度（ 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 ）

定义
二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质：

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

存储结构

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;
} 

定义

性质

应用

抽象类型定义

存储结构

二叉搜索树（ BST ）

平衡二叉树（ AVL树）