数据结构-树和二叉树

    树 和 二叉树 

1.树的概念 

    树 tree 
        是n(n>=0)个节点的有限集
        在任意的一个非空树中 
            (1)有且仅有一个特定的被称为 根(root) 的节点 
            (2)当n>1时, 其余的节点可分为m(m>0)个互不相交的有限集T1, T2, T3, .... 
                其中每一个集合本身又是一棵树, 并且称为 根的子树 (Subtree)

    树的节点 
        包含一个数据元素 以及 若干个指向子树的分支(保存的关系)

    
    节点的度 degree 
        节点拥有子树的个数 称为 节点的度 
            度为0的节点, 称为 叶子节点 或者 终端节点
            度不为0的节点, 称为 分支节点 或者 非终端节点

    节点的层次 level 
        从 根 开始定义起的, 根为第一层, 根的子树为第二层, 以此类推 ... 
        
        树中节点最大层次 称为 树的高度 或者 深度 depth 

2.二叉树 Binary 

    1)二叉树 
        是一种树形结构, 它的特点是 每一个节点至多有两个子树 
                                (即二叉树中不存在 度大于2 的节点)
            并且, 二叉树的子树有左右之分的, 其次序是不能颠倒 

    2)二叉树的5种形态  (见图示)
        (1)空树
        (2)只有一个根节点(没有子节点)
        (3)只有一个左子节点
        (4)只有一个右子节点
        (5)有左右两个子节点        

    ☆☆☆
    3)二叉树的性质 

        (1)在二叉树中, 第i层 至多有 2^(i-1) 个节点   (i>=1)

            证明:   数学归纳法 

                    当 n == 1 时, 1 
                    当 n == 2 时, 2
                    当 n == 3 时, 4
                    当 n == 4 时, 8 
                    ...
                       i   --->   2^(i-1) 

        
        (2)深度为k的二叉树中, 至多有 ( 2^k - 1 ) 个节点   (k>=1)

            证明:  由性质(1)可得 
                    1 + 2 + 4 + 8 + 16 + ... + 2^(k-1) = 2^k - 1

                        等比数列前n项和 : Sn = a1 * ( 1 - q^n ) / ( 1 - q ) 

        (3)对于任意一颗二叉树中, 如果其 叶子节点(度为0的节点)的个数为 n0, 度为2的节点的个数为 n2,
            则 n0 = n2 + 1 

            证明: 
                假设一个二叉树中的总的节点个数为N 
                    度为0的节点个数为n0
                    度为1的节点个数为n1
                    度为2的节点个数为n2

                    N = n0 + n1 + n2        (I)

                设这个二叉树的分支数为B 
                    从下往上看, 每一个节点都有一个向上的分支(除了根节点没有) 

                    B = N - 1               (II)

                    从上往下看, 一个节点如果有一个子节点,就会有一个向下的分支
                                如果有两个子节点,就会有2个向下的分支
                                如果没有子节点,就没有分支 

                    B = 0 * n0 + 1 * n1 + 2 * n2    
                    --> 
                        B = n1 + 2 * n2     (III)

                有(I)(II)(II)可得 
                                    B = N - 1
                    ==>   n1 + 2 * n2 = n0 + n1 + n2 - 1
                    ==>            n0 = n2 + 1 

                

            满二叉树:
                一个深度为k 且 有 2^k - 1 个节点的二叉树, 称为 满二叉树 
                    在不改变二叉树深度的情况下, 不能再额外的添加节点了

            完全二叉树:
                (1)除去最后一层, 为满二叉树
                (2)最后一层的节点的排序, 要从左边开始(中间不能有空洞)

        (4)如果对一个有n个节点的完全二叉树 从上至下,从左至右 
            给每一个节点进行编号, 从1开始编号 
            那么,如果一个节点的编号为i, 则 

                父节点的编号为      i/2
                左子节点的编号为    2*i 
                右子节点的编号为    2*i + 1 

            证明: 
                假设编号为i的节点, 在第k层 
                    那么第k层的第一个节点的编号为 2^(k-1) 

                    i这个节点 距离它所在的层次的第一个节点 中间间隔多少个节点? 
                        i - 2^(k-1)  

                    i的子节点在第k+1层 
                        左子节点的编号为  2^k + 2*( i - 2^(k-1) )  ==>  2*i 
                        右子节点的编号为  2*i + 1 

                    i的父节点在 第k-1层 
                        父节点的编号为    2^(k-2) + ( i - 2^(k-1) )/2 ==> i/2 

        (5)具有n个节点的完全二叉树的深度为 log2(n)向下取整 +1 

            证明: 
                假设深度为k 

                    2^(k-1) - 1 < n <= 2^k - 1
                    --> 2^(k-1) <= n < 2^k  

3.二叉树的代码实现 

    如何保存二叉树的节点? 
        保存数据 
        保存数据之间的关系
                对于数的节点来说, 父节点和子节点 

        1)顺序结构 
            用一组地址连续的空间 来保存二叉树   "数组" 

                如何去表示节点与节点之间的关系? 

                    完全二叉树的性质, 如果一个节点的编号为i, 则 
                        父节点的编号为      i/2
                        左子节点的编号为    2*i 
                        右子节点的编号为    2*i + 1 

                用数组来保存一颗完全二叉树 

                    #define MAX_LEN  1024
                    typedef int DataType;       //数据的类型

                    DataType SqBitree[MAX_LEN];     

                        SqBitree[1] 保存根节点的数据
                        SqBitree[2] 保存编号为2的节点
                        SqBitree[3] 保存编号为3的节点
                        ... 

                    缺点: 
                        数组的大小是固定的, 可能会造成空间的浪费,或者空间不足的情况 

        2)链式结构 
            用一组地址不连续的空间 来存储栈的一个二叉树

                二叉树的节点: 
                    数据域: 保存数据 
                    指针域: 至少有两个, 保存左子和右子的指针 

                    typedef int DataType;       //数据的类型

                    typedef struct BitNode      //二叉树节点的类型
                    {
                        DataType data;              //数据域 
                        struct BitNode * lchild;    //指针域 , 左子节点的指针     
                        struct BitNode * rchild;             //右子节点的指针 
                    } BitNode ;

    ☆☆☆
4.二叉树的遍历 

    如何按照某种搜索路径访问二叉树的每一个节点 
        使得每一个节点都能够被访问 且 仅访问一次 

        一般 左子节点的访问 在 右子节点的前面 

        根 左 右 : 先序遍历(先根遍历)
        左 根 右 : 中序遍历 
        左 右 根 : 后序遍历 

    1)先序遍历(先根遍历) 
        (1)先访问根节点 
        (2)再按照先序遍历的方式去访问根的左子树
        (3)再按照先序遍历的方式去访问根的右子树 

            F(t)    --> F表示用先序遍历的方法, t表示这个二叉树的根节点 

            F(t) ==> 
                    (1)判断这个树是否为空
                    (2)访问 根节点 printf
                    (3) F( t->lchild )
                    (4) F( t->rchild )

    2)中序遍历 
        (1)先按照中序遍历的方式去访问根的左子树
        (2)再访问根节点
        (3)再按照中序遍历的方式去访问根的右子树 

    3)后序遍历 
        (1)先按照后序遍历的方式去访问根的左子树
        (2)再按照后序遍历的方式去访问根的右子树
        (3)最后访问根节点

        练习: 
            1) 见图示 

            2) 已知一棵二叉树的先序和中序遍历,请画出这个树, 并写出其后序遍历
                先序遍历: EBADCFHGIKJ
                中序遍历: ABCDEFGHIJK

                    见图示 

5.二叉排序树 

    二叉排序树具有以下的性质: 
        (1)如果它的左子树不为空, 则左子树上的所有节点的值 都是小于 根节点的值
        (2)如果它的右子树不为空, 则右子树上的所有节点的值 都是大于 根节点的值 
        (3)它的左右子树 也分别是一棵二叉排序树 

        练习: 
            1)创建一个二叉排序树 
                实际上就是把一个节点加入到一个二叉排序树中,并保持其排序性
                    不断地 重复二叉排序树的插入操作 

                    BinaryTree.c   /  BinaryTree.h   

                    typedef char DataType;       //数据的类型

                    typedef struct BitNode      //二叉树节点的类型
                    {
                        DataType data;              //数据域 
                        struct BitNode * lchild;    //指针域 , 左子节点的指针     
                        struct BitNode * rchild;             //右子节点的指针 
                    } BitNode ;

                    //往一个二叉排序树中添加节点 

//往一个二叉排序树中添加节点 
BitNode * insert_node( BitNode *r , BitNode *pnew )
{if( r == NULL )     //从无到有 {return pnew;}//从少到多 //找到待插入的位置 BitNode * p = r;    //遍历指针 while( 1 ){if( pnew->data  >  p->data  )   //大于 往右 {if( p->rchild == NULL )     //如果右子为空,那么就添加进来{p->rchild = pnew;break;}p = p->rchild;}else if( pnew->data  <  p->data )   //小于  往左{if( p->lchild == NULL ) //如果左子为空, 那么就添加进来{p->lchild = pnew;break;}p = p->lchild;}else{printf("data repetitive! \n");break;}}//返回根节点return r;
}

                    //创建一个二叉排序树

//创建一个二叉排序树
BitNode * create_sort_tree()
{BitNode * r = NULL;     //保存根节点的指针//1.从键盘上获取输入的数据 char str[32] = {0};scanf("%s", str );int i = 0;while( str[i] ){//2.创建一个新的数据节点空间, 并初始化 BitNode * pnew = (BitNode *)malloc( sizeof(BitNode) );pnew->data = str[i];pnew->lchild = NULL;pnew->rchild = NULL;//3.把新节点加入到二叉树中r = insert_node( r , pnew );i++;}//4.返回根节点return r;
}

            2)用递归的方法, 实现二叉树的先序遍历\中序遍历\后序遍历 

//先序遍历
void pre_order( BitNode * r )
{if( r == NULL ){return ;}//(1)先访问根节点printf("%c ", r->data );//(2)再按照先序遍历的方式去访问根的左子树pre_order( r->lchild );//(3)再按照先序遍历的方式去访问根的右子树 pre_order( r->rchild );
}//中序遍历
void mid_order( BitNode * r )
{if( r == NULL ){return ;}//(1)先按照中序遍历的方式去访问根的左子树mid_order( r->lchild );//(2)再访问根节点printf("%c ", r->data );//(3)再按照中序遍历的方式去访问根的右子树 mid_order( r->rchild );}//后序遍历 
void post_order( BitNode * r )
{if( r == NULL ){return ;}//(1)先按照后序遍历的方式去访问根的左子树post_order( r->lchild );//(2)再按照后序遍历的方式去访问根的右子树post_order( r->rchild );//(3)最后访问根节点printf("%c ", r->data );
}

            3)求一棵二叉树的高度(深度)

//求一棵二叉树的高度(深度)
int TreeHeight( BitNode * t )
{if( t == NULL ){return 0;}int l = TreeHeight( t->lchild );int r = TreeHeight( t->rchild );return l>r ? l+1 : r+1;
}

            4)删除二叉树中值为x的节点  (参考图示)

 
        5)销毁一棵二叉树 

//销毁一棵二叉树 
void destroy_tree( BitNode * r )
{while( r ){r = delete_node( r, r->data ); }
}

        6)层次遍历 

//层次遍历 
void level_order( BitNode * r )
{if( r == NULL ){return ;}//1.初始化一个队列 CircleQueue *q = InitQueue();//2.把根节点入队EnQueue( q, r );while( ! IsEmpty( q ) ){//3.出队, 访问 ElemType d;		// BitNode * d;DeQueue( q, &d );printf("%c ", d->data );//4.再把出队元素的左子和右子全部入队 if( d->lchild ){EnQueue( q, d->lchild );}if( d->rchild ) {EnQueue( q, d->rchild );}}putchar('\n');//5.销毁队列 DestroyQueue( q );
}

6.平衡二叉树 

    1)平衡二叉树 Balance Binary Tree   (又称为 AVL树 )

        它或者是一棵空树, 或者具有以下的性质: 
            它的左子树和右子树本身又是一棵平衡二叉树 
            且 左子树 和 右子树 的深度之差的绝对值不超过1 

        若平衡二叉树的节点的 平衡因子BF 的定义为
            该节点的 左子树的深度 减去 右子树的深度
            则 平衡二叉树上的所有节点的平衡因子的取值范围可能是 -1, 0, 1 
            只要有一个节点的平衡因子的绝对值大于1的,那么这棵树就是不平衡的

        平衡二叉树 --> 平衡的二叉排序树 来实现 

    2)平衡操作 

        (1)单向右旋平衡处理 SingleRotateWithRight 
            在不平衡的节点的左子节点的左边新增一个节点
            ==>对不平衡的节点做 单向右旋平衡处理 

AVLNode * SingleRotateWithRight( AVLNode *k2 )
{AVLNode * k1 = k2->lchild;//平衡处理 k2->lchild = k1->rchild;k1->rchild = k2;//更新树的深度 k2->h = MAX( Height(k2->lchild), Height(k2->rchild) ) + 1 ;k1->h = MAX( Height(k1->lchild), Height(k1->rchild) ) + 1 ;return k1;
}

  (2)单向左旋平衡处理 SingleRotateWithLeft 
            在不平衡的节点的右子节点的右边新增一个节点
            ==>对不平衡的节点做 单向左旋平衡处理 

     

AVLNode * SingleRotateWithLeft( AVLNode *k2 )
{AVLNode *k1 = k2->rchild;//平衡处理 k2->rchild = k1->lchild;k1->lchild = k2;//更新树的深度 k2->h = MAX( Height(k2->lchild), Height(k2->rchild) ) + 1 ;k1->h = MAX( Height(k1->lchild), Height(k1->rchild) ) + 1 ;return k1;
}

  (3)双向旋转(先左后右)平衡处理 DoubleRotateLeftRight
            在不平衡的节点的左子节点的右边新增一个节点
            ==> 先把 不平衡的节点的左子节点 做 单向左旋平衡处理 
                然后再对该 不平衡的节点 做 单向右旋平衡处理

       

AVLNode * DoubleRotateLeftRight( AVLNode * k3 )
{k3->lchild = SingleRotateWithLeft( k3->lchild );k3 = SingleRotateWithRight( k3 );return k3;
}

(4)双向旋转(先右后左)平衡处理 DoubleRotateRightLeft
            在不平衡节点的右子节点的左边新增一个节点
            ==> 先把 不平衡的节点的右子节点 做 单向右旋平衡处理 
                然后再对该 不平衡的节点 做 单向左旋平衡处理 

    

AVLNode * DoubleRotateRightLeft( AVLNode * k3 )
{k3->rchild = SingleRotateWithRight( k3->rchild );k3 = SingleRotateWithLeft( k3 );return k3;
}

    3)代码实现 

            typedef char DataType;      //数据的类型 

            typedef struct AVLNode      //平衡的二叉排序树的节点的数据类型
            {
                DataType data;              //数据域: 保存数据 
                struct AVLNode * lchild;    //指针域, 左子节点的指针 
                struct AVLNode * rchild;            //右子节点的指针 
                int h;                      //保存树的深度
            } AVLNode ;

        练习: 
            1)创建一个平衡二叉排序树 
                其实就是把一个节点 加入到一个平衡二叉排序树中, 并保持其平衡性 

                    AVL.c  /  AVL.h

                    //往一棵平衡二叉排序树t中 插入值为x的节点

AVLNode * insert_AVL_node( AVLNode *t, DataType x )
{if( t == NULL )		//从无到有 {//创建一个新节点, 并初始化AVLNode *pnew = (AVLNode *)malloc( sizeof(AVLNode) );pnew->data = x;pnew->lchild = NULL;pnew->rchild = NULL;pnew->h = 1;return pnew;}//从少到多if( x > t->data )	//大于 往右 {//大于, 把x插入到t的右子树中, 同时做平衡处理t->rchild = insert_AVL_node( t->rchild, x );//更新树的深度t->h = MAX( Height( t->lchild ) , Height( t->rchild ) ) + 1 ;//把x插入到右子树之后,如果不平衡, 需要做平衡处理if( Height( t->rchild ) - Height( t->lchild ) > 1  ){if( x > t->rchild->data )	//右子树的右边{//单向左旋平衡处理t = SingleRotateWithLeft( t );}else						//右子树的左边{//双向旋转(先右后左)平衡处理 t = DoubleRotateRightLeft( t );}}}else if( x < t->data )	//小于 往左 {//小于, 把x插入到t的左子树中, 同时做平衡处理t->lchild = insert_AVL_node( t->lchild, x );//更新树的深度t->h = MAX( Height( t->lchild ) , Height( t->rchild ) ) + 1 ; //把x插入到左子树之后, 如果不平衡, 需要做平衡处理if( Height( t->lchild) - Height( t->rchild) > 1 ){if( x < t->lchild->data )	//左子节点的左边{//单向的右旋平衡处理t = SingleRotateWithRight( t );}else						//左子节点的右边 {	//双向旋转(先左后右)平衡处理t = DoubleRotateLeftRight( t );}}}//返回树的根节点return t;
}

                    //创建一个平衡二叉排序树

AVLNode * create_AVL()
{AVLNode * t = NULL;		//保存根节点 //从键盘上获取输入数据char str[32] = {0};scanf("%s", str );int i = 0;while( str[i] ){//把新的节点 加入到 平衡二叉树中 t = insert_AVL_node( t, str[i] );i++;}//返回 平衡二叉排序树的根节点return t;
}   

7.哈夫曼树 Huffman 

    1)哈夫曼树 

        又称为 最优二叉树 

            它是n个带权的叶子节点 构成的所有的二叉树中, 带权路径长度WPL最小的二叉树 

                (1)一棵树的带权路径长度的定义为 树中所有的叶子节点的带权路径长度之和
                (2)节点的带权路径长度规定 从根节点 到 该节点之间的路径长度 与 该节点上的权值 的乘积 

    2)哈夫曼编码 

        在电报通信中, 电文是以二进制0/1序列形式去发送, 每一个字符对应着一个二进制编码 
        为了缩短 电文的长度,采用不等长的编码方式,把使用频率高的字符用短编码
        使用频率低的字符用长编码

        我们把使用频率作为权值, 把每一个字符作为叶子节点来构建哈夫曼树
        每一个分支节点的左右分支分别用0和1进行编码, 这样就得到了每一个叶子节点的 哈夫曼编码

        使用的是叶子节点的编码, 所以每一个字符的编码都不可能是其他字符编码的前缀 

    3)构建哈夫曼树 

        假设有n个带权的叶子节点 w1, w2, w3, w4, ... wn , 则构建哈夫曼树的步骤: 

            第一步: 构建森林 
                    把每一个叶子节点 都当作是一棵独立的树(只有根结点)
                    这样就形成了森林 
                    把这片森林存放到 有序队列中 , 方便取出最小的节点 

            第二步: 
                    从 有序队列中, 取出两个最小的节点 
                    然后再创建一个新的节点 作为它们的父节点
                        父节点的权值 就是这两个子节点的权值之和 

            第三步: 
                    把新创建的父节点 加入到 有序队列中 

            重复 第二步和第三步, 直到这个有序队列中只剩下一个节点为止 
                最后剩下的这个节点 就是 哈夫曼树的根节点 

    4)代码实现  

            Huffman.c   /  Huffman.h    +  链式队列 

                typedef struct HTnode       //哈夫曼树的节点类型
                {
                    int weight;                 //数据域: 权值 
                    struct HTnode * left;       //指针域: 左子节点的指针
                    struct HTnode * right;              //右子节点的指针
                } HTnode ;

            
            LinkQueue.c 

/*
入队   ---> 有序队列 返回值:1 入队成功0 入队失败
*/
int EnQueue( LinkQueue *q, ElemType d )
{//不能入队的情况: 队列不存在 if( q == NULL ){return 0;}//创建一个新的数据节点空间, 并初始化Node * pnew = (Node *)malloc( sizeof(Node) );pnew->data = d;pnew->next = NULL;//入队 --> 插入有序if( q->num == 0 )  //从无到有{q->front = pnew;q->rear = pnew;}else    //从少到多 {//有序队列Node * p = q->front;	//遍历指针 Node * pre = NULL;		//指向p的前一个 while( p ){//找到第一个比它大的数的前面 (比较二叉树节点里面的权值)if( p->data->weight  >  pnew->data->weight ){break;}pre = p;p = p->next;}if( p != NULL )	//找到了 {if( p == q->front ){//头插 pnew->next = q->front;q->front = pnew;}else {//中间插入 pre->next = pnew;pnew->next = p;}}else	//没有找到 {//尾插法q->rear->next = pnew;q->rear = pnew;}}q->num ++;return 1;
}

/*出队 返回值: 返回出队元素 
*/
Node * DeQueue( LinkQueue *q )
{//不能出队的情况: 队列不存在 || 队列为空 if( q == NULL || q->num == 0 ){return 0;}//出队Node * p = q->front;	//指向要出队的这个节点q->front = q->front->next;p->next = NULL;q->num --;if( q->num == 0 )	//仅剩的一个节点也被删除了,那么队尾rear也要被置NULL{q->rear = NULL;}return p;
}

            Huffman.c 

HTnode * create_Huffman()
{//从键盘上获取所有叶子节点的权值int w[MAX_LEN] = {0};int i;for( i=0; i<MAX_LEN; i++ ){scanf("%d", &w[i] );}//定义指针 保存哈夫曼树的根节点HTnode * r = NULL;//初始化一个有序队列LinkQueue * q = InitQueue();//1.构建森林 (为每一个权值 创建一个叶子节点),并且加入到 有序队列中 HTnode * hfmnode = (HTnode*)malloc( sizeof(HTnode) * MAX_LEN );for( i=0; i<MAX_LEN; i++ ){hfmnode[i].weight = w[i];hfmnode[i].left = NULL;hfmnode[i].right = NULL;//入队EnQueue( q, hfmnode+i );}while( QueueLength( q ) >= 2 ){//2.把最小的两个节点出队, 构建父节点 HTnode * p1 = DeQueue( q )->data;HTnode * p2 = DeQueue( q )->data;HTnode * parent = (HTnode*)malloc( sizeof(HTnode) );parent->weight = p1->weight +p2->weight;parent->left = p1;parent->right = p2;//3.把新创建的父节点 加入到有序队列中 EnQueue( q, parent );}//把最后剩下的节点出队, 该节点 就是 哈夫曼树的根节点 r = DeQueue( q )->data ;//销毁队列 DestroyQueue( q );//返回 哈夫曼树的根节点指针return r;
}

            打印出每一个叶子节点的哈夫曼编码 

//打印出每一个叶子节点的哈夫曼编码 
void print_Huffman_code( HTnode * t , int i )
{static int arr[32];	   //只初始化一次 HTnode * p = t; if( p != NULL ){if( p->left == NULL && p->right == NULL )   //叶子节点 {//打印编码printf("%2d -- ", p->weight );int j;for( j=0; j<i; j++ ){printf("%d", arr[j] );}putchar('\n');}else {arr[i] = 0;print_Huffman_code( p->left , i+1 );arr[i] = 1;print_Huffman_code( p->right , i+1 );}}
}

        

7.其他 

    1)树 转换成 二叉树     (参考图示)

        (1)树中所有相邻的兄弟节点 进行连接 
        (2)只保留原树的第一个子节点的连线,删除与其他子节点的连线 

    2)森林 转换成 二叉树    (参考图示)

        (1)树 转换成 二叉树 
        (2)第一棵树不动, 从第二棵树开始依次把当前二叉树 作为 前一个树的根节点的右子树 进行连接