二元线性内存

- 日理万妓 2022-04-10 09:59 159阅读 0赞

/***************************************************
    二叉树的线性存储
    by Rowandjj
    2014/5/23
    ***************************************************/
    #include<iostream>
    #include<MATH.H>
    using namespace std;
    
    #define MAX 255
    #define NIL -1
    typedef struct _POSITION_
    {
        int level;//层数
        int order;//序号
        
    }Position,*pPosition;
    
    //若节点位置为i，其父节点位置为(i+1)/2-1
    //若父节点位置为i,则子节点位置为i*2+1,i*2+2
    //若节点的层数为i,序号为j,则在数组中的位置为pow(2,i-1)+j-2
    void InitTree(int *T);
    void CreateTree(int *T);
    int GetDepth(int *T);
    bool GetRoot(int *T,int *e);
    bool IsEmpty(int *T);
    bool GetValue(int *T,Position pos,int *e);
    bool Assign(int *T,Position pos,int iValue);
    void MidTravel(int *T,int i);
    void PreTravel(int *T,int i);
    void PosTravel(int *T,int i);
    void LevelTravel(int *T);
    int GetParent(int *T,int e);
    int GetLeftChild(int *T,int e);
    int GetRightChild(int *T,int e);
    int GetLeftSibling(int *T,int e);
    int GetRightSibling(int *T,int e);
    void InsertNode(int *T,);
    
    void InitTree(int *T)
    {
        int i;
        for(i = 0; i < MAX; i++)
        {
            *(T + i) = NIL;
        }
    }
    
    void CreateTree(int *T)
    {
        int i = 0;
        int a;
        while(true)
        {
            cin>>a;
            if(a == NIL)
            {
                break;
            }
            if(i!=0 && T[(i+1)/2-1]==NIL && a!=NIL)
            {
                return;    
            }
            
            T[i] = a;
            i++;
        }
    }
    int GetDepth(int *T)
    {
        int i = MAX - 1;
        while(T[i] == NIL)
        {
            i--;    
        }
        i++;
        int j = 0;
        while(i >= pow(2,j))
        {
            j++;
        }
        return j;
    }
    bool IsEmpty(int *T)
    {
        return T[0]!=NIL ? false : true;
    }
    
    bool GetRoot(int *T,int *e)
    {
        if(IsEmpty(T))
        {
            return false;
        }else
        {
            *e = T[0];
            return true;
        }
    }
    
    bool GetValue(int *T,Position pos,int *e)
    {
        int index = pow(2,pos.level-1)+pos.order-2;
        if(T[index] == NIL)
        {
            return false;
        }
        else
        {
            *e = T[index];
            return true;
        }
    }
    
    bool Assign(int *T,Position pos,int iValue)
    {
        int index = pow(2,pos.level-1)+pos.order-2;
        if(iValue!=NIL && T[(index+1)/2-1]==-1)//当前节点的父节点为空
        {
            return false;
        }
        if(iValue==NIL && T[index*2+1]!=-1||T[index*2+2]!=-1)//子节点不为空可是当前节点为空
        {
            return false;
        }
        T[index] = iValue;
        return true;
    }
    
    void MidTravel(int *T,int i)
    {
        if(IsEmpty(T))
        {
            return;
        }else
        {
            if(T[i*2+1] != NIL)
            {
                MidTravel(T,i*2+1);
            }
            cout<<T[i]<<endl;
            if(T[i*2+2] != NIL)
            {
                MidTravel(T,i*2+2);
            }
        }
    }
    void PreTravel(int *T,int i)
    {
        if(IsEmpty(T))
        {
            return;
        }else
        {
            cout<<T[i]<<endl;
            if(T[i*2+1]!=NIL)//左子树非空
            {
                PreTravel(T,i*2+1);
            }
            if(T[i*2+2]!=NIL)//右子树非空
            {
                PreTravel(T,i*2+2);
            }
        }
    }
    void PosTravel(int *T,int i)
    {
        if(IsEmpty(T))
        {
            return;
        }
        else
        {
            if(T[i*2+1] != NIL)
            {
                PosTravel(T,i*2+1);    
            }
            if(T[i*2+2] != NIL)
            {
                PosTravel(T,i*2+2);
            }
            cout<<T[i]<<endl;
        }
    }
    void LevelTravel(int *T)
    {
        int j = MAX-1;
        while(T[j] == NIL)
        {
            j--;
        }
        for(int m = 0; m <= j; m++)
        {
            if(T[m] != NIL)
            {
                cout<<T[m]<<endl;
            }
        }
    
    }
    
    int GetParent(int *T,int e)
    {
        if(IsEmpty(T))
        {
            return -1;
        }
        int i = MAX -1;
        while(T[i] == NIL)
        {
            i--;
        }
        for(int j = 1; j <= i;j++)
        {
            if(e == T[j])
            {
                return T[(j+1)/2-1];
            }
        }
        return -1;
    }
    
    int GetLeftChild(int *T,int e)
    {
        if(IsEmpty(T))
        {
            return -1;
        }
        int i = MAX - 1;
        while(T[i] == NIL)
        {
            i--;
        }
        for(int j = 0; j <= i; j++)
        {
            if(T[j] == e)
            {
                return T[2*j]+1;
            }
        }
        return -1;
    }
    int GetRightChild(int *T,int e)
    {
        if(IsEmpty(T))
        {
            return -1;
        }
        int i = MAX - 1;
        while(T[i] == NIL)
        {
            i--;
        }
        for(int j = 0; j <= i; j++)
        {
            if(T[j] == e)
            {
                return T[j*2]+2;
            }
        }
        return -1;
    }
    
    int GetLeftSibling(int *T,int e)
    {
        if(IsEmpty(T))
        {
            return -1;
        }
        int j = MAX -1;
        while(T[j] == NIL)
        {
            j--;
        }
        for(int i = 0; i <= j; i++)
        {
            if(T[i] == e && i%2 == 0)
            {
                return T[i-1];
            }
        }
        return -1;
        
    }
    int GetRightSibling(int *T,int e)
    {
        if(IsEmpty(T))
        {
            return -1;
        }
        int j = MAX -1;
        while(T[j] == NIL)
        {
            j--;
        }
        for(int i = 0; i <= j; i++)
        {
            if( e == T[i] && i%2)
            {
                return T[i+1];
            }
        }
        return -1;
    }