数据结构——左高树（C语言）

朱雀 2022-08-25 15:39 128阅读 0赞

介绍左高树之前，先简单介绍下扩充二叉树的概念。扩充二叉树一棵二叉树，其所有空的子树都由方形结点代替。方形结点称为外部结点，原来的结点称为内部结点。

设x是扩充二叉树的一个结点，并令left\_child(x)和right\_child(x)分别表示内部结点的左、右儿子。定义shortest(x)为从x到一个外部结点的最短路程长度。

左高树

## 定义 ##

左高树是一棵二叉树，且如果该二叉树不空，则对其中的每个内部结点x，都有：

Shortest(left\_child(x))>= Shortest(right\_child(x))。

左高树的一个应用是合并操作,应用场景是:当某个优先队列的服务器关闭时,就需要将其与另一个正在运行服务器的优先队列合并.如果两个队列的元素总数为n,则一般的堆结构的复杂度为n,但是左高树可以达到log(n).插入和删除操作都可以通过合并操作来完成。

最小（最大）左高树是一棵左高树，其中的每个内部结点的关键字值不大于（不小于）该结点的儿子结点的关键字值。

以下讨论最小左高树的操作：

插入和删除最小元素操作都可以通过合并操作来完成。要把元素x插入到左高树A中，先建立一棵只有一个元素x的最小左高树B，再合并最小左高树A和B。要从一棵非空最小左高树A删除最小元素，则只需合并最小左高树A的左子树和右子树，再把最小左高树的根结点删除。

以下重点介绍最小左高树的合并操作。

假设要合并最小左高树A和B，首先，沿着A和B的最右路径，得到一棵包含A和B所有元素的二叉树（注意：这里只是得到二叉树，而不是最小左高树）。使得该二叉树具有以下性质：所有结点的关键字都不大于其儿子结点关键字。必要时交换结点的左、右子树，将其转化为最小左高树。

## 合并操作 ##

步骤：

1、 假设合并最小左高树A和B，首先比较两棵树根结点的关键字值，以最小的关键字作为新二叉树的根结点。

2、 保留A的左子树不变，将其右子树与最小左高树B合并，合并后的二叉树成为新的A的右子树。

3、 把二叉树转换为最小左高树从最后一个修改结点（注意：这里不是最后结点）开始，回溯到最终的树根结点，使得路径上的所有结点满足不等式：shortest（left\_child()）>= shortest（right\_child()）

## 程序： ##

函数定义：

#ifndef LEFTIST_TREE_H_INCLUDED
    #define LEFTIST_TREE_H_INCLUDED
    #include <malloc.h>
    #include<stdio.h>
    #include<stdlib.h>
    #define MAX_SIZE  11
    #define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))
    
    typedef struct lefttree *LeftistTree;
    typedef struct lefttree
    {
        LeftistTree left_child;
        LeftistTree right_child;
        int data;
        int shortest;
    }left_tree;
    void min_uion(LeftistTree*a,LeftistTree*b);
    void init_left_tree(LeftistTree *a,int data);
    void min_combine(LeftistTree *a,LeftistTree *b);
    void show_pre_tree( LeftistTree *a );
    /*初始化二叉树*/
    void init_left_tree(LeftistTree *b,int data)
    {
        if(!*b)
        {
            *b=(LeftistTree)malloc(sizeof(left_tree));
            (*b)->data=data;
            (*b)->left_child=NULL;
            (*b)->right_child=NULL;
            (*b)->shortest=1;
        }
    }
    /*合并两棵树*/
    void min_combine(LeftistTree *a,LeftistTree *b)
    {
        if(!*a)
            *a=*b;
        else if(*b)
            min_uion(a,b);
        *b=NULL;
    }
    /*合并两棵最小左高树*/
    void min_uion(LeftistTree*a,LeftistTree*b)
    {
        LeftistTree temp=NULL;
        if((*a)->data>(*b)->data)//比较两棵树根结点大小
            SWAP(*a,*b,temp);
        if(!(*a)->right_child)//右子树是否为空
                (*a)->right_child=*b;
        else
            min_uion(&(*a)->right_child,b);//把a右子树和b合并
        if(!(*a)->left_child)
            {
                (*a)->left_child=(*a)->right_child;
                (*a)->right_child=NULL;
            }
        else if((*a)->right_child->shortest>(*a)->left_child->shortest)
            SWAP((*a)->right_child,(*a)->left_child,temp);
        if(!(*a)->right_child)
            (*a)->shortest=1;
        else
            (*a)->shortest=(*a)->right_child->shortest+1;
    }
    /*先序递归遍历最小左高树*/
    void show_pre_tree(LeftistTree *a)
    {
        if (*a)
        {
            printf("%d ", (*a)->data );
            show_pre_tree( &(*a)->left_child );
            show_pre_tree( &(*a)->right_child );
        }
    }
    #endif // LEFTIST_TREE_H_INCLUDED

程序测试：

#include "leftist_tree.h"
    
    
    int main()
    {
        LeftistTree a=NULL;
        LeftistTree b=NULL;
        int i,data;
        for(i=1;i<MAX_SIZE-5;i++)
        {
            scanf("%d",&data);
            init_left_tree(&b,data);
            min_combine(&a,&b);
        }
        show_pre_tree(&a);
        return 0;
    }