数据结构-树

树的基本概念

• 树是递归定义的结构

• 结点

  • 根节点：树只有一个根结点

  • 结点的度：结点拥有的子树的数量

    • 度为0：叶子结点或者终端结点

    • 度不为0：分支结点或者非终端结点

      • 分支结点除去根结点也称为内部结点
• 树的度：树中所有结点的度数的最大值

• 结点关系

  • 祖先结点

    • 根结点到该结点的唯一路径的任意结点
  • 子孙结点

  • 双亲结点

    • 根结点到该结点的唯一路径上最接近该结点的结点
  • 孩子结点

  • 兄弟结点

    • 有相同双亲结点的结点

• 层次，高度，深度，树的高度

  • 层次：根为第一层，它的孩子为第二层，以此类推
  • 结点的深度：根结点开始自顶向下累加
  • 结点的高度：叶节点开始自底向上累加
  • 树的高度（深度）：树中结点的最大层数

• 树的性质

  • 1.树中的结点数等于所有结点的度数加1。

    • 证明：不难想象，除根结点以外，每个结点有且仅有一个指向它的前驱结点。也就是说每个结点和指向它的分支一一对应。

假设树中一共有b个分支，那么除了根结点，整个树就包含有b个结点，所以整个树的结点数就是这b个结点加上根结点，设为n，则n=b+1。而分支数b也就是所有结点的度数，证毕。

* 2.度为m的树中第i层上至多有m^(i−1)个结点（i≥1）。
    * 证明：（数学归纳法）

首先考虑i=1的情况：第一层只有根结点，即一个结点，i=1带入式子满足。
假设第i-1层满足这个性质，第i-1层最多有m i-2个结点。
……… ..........
i-1层
………
又因为树的度为m,所以对于第i-1层的每个结点，最多
有m个孩子结点。所以第i层的结点数最多是i-1层的m
倍，所以第i层上最多有m ^(i-1)个结点。

* 3.高度为h的m叉树至多有(m^h-1)/(m-1)个结点
* 4.具有n个结点的m叉树的最小高度为logm(n(m-1)+1) 

树的存储结构

• 顺序存储结构

  • 双亲表示法：用一组连续的存储空间存储树的结点，同时在每个结点中，用一个变量存储该结点的双亲结点在数组中的位置。

• 链式存储结构

  • 孩子表示法：把每个结点的孩子结点排列起来存储成一个单链表。所以n个结点就有n个链表；

如果是叶子结点，那这个结点的孩子单链表就是空的；
然后n个单链表的的头指针又存储在一个顺序表（数组）中。

* 孩子兄弟表示法：顾名思义就是要存储孩子和孩子结点的兄弟，具体来说，就是设置两个指针，分别指向该结

点的第一个孩子结点和这个孩子结点的右兄弟结点。

顺序存储：

void InitBiTree_Sq(SqBiTree T)
{
    int i;
    
    for(i=0; i<MAX_TREE_SIZE; i++)
        T[i] = '\0';                        //空树无结点，以空字符填充数组 
}

void ClearBiTree_Sq(SqBiTree T)                //清空与构造算法一样 
{
    int i;
    
    for(i=0; i<MAX_TREE_SIZE; i++)
        T[i] = '\0';
}

void DestroyBiTree_Sq(SqBiTree T)
{
    //二叉树无法销毁  
} 

Status BiTreeEmpty_Sq(SqBiTree T)
{
    return T[0]=='\0' ? TRUE : FALSE;
} 

Status CreateBiTree_Le_Sq(FILE *fp, SqBiTree T)
{
    char ch;
    int i = 0;
    
    while(Scanf(fp, "%c", &ch)==1 && ch!='\n')
    {
        if(ch == '^')
            T[i++] = '\0';
        else
            T[i++] = ch;
    }
    
    return OK;    
}

Status CreateBiTree_Pre_Sq(FILE *fp, SqBiTree T, int i)
{
    char ch;

    Scanf(fp, "%c", &ch);
    
    if(ch == '^')
        T[i] = '\0';
    else
    {
        T[i] = ch;
        CreateBiTree_Pre_Sq(fp, T, 2*i+1);
        CreateBiTree_Pre_Sq(fp, T, 2*i+2);
    }
    
    return OK;
}

int BiTreeLength_Sq(SqBiTree T)
{
    int len;
    
    for(len=MAX_TREE_SIZE; len-1>=0; len--)        //寻找最后一个结点 
    {
        if(T[len-1]!='\0')
            break;
    }
    
    return len;
}

int BiTreeDepth_Sq(SqBiTree T)
{
    int level=0;                            

    while((int)pow(2, level)-1<BiTreeLength_Sq(T))
        level++;
    
    return level;
}

Status Root_Sq(SqBiTree T, TElemType_Sq *e)
{
    if(BiTreeEmpty_Sq(T))                        //空树无根结点 
        return ERROR;
    
    *e = T[0];
    
    return OK;
} 

TElemType_Sq Value_Sq(SqBiTree T, Position s)
{
    int i =(int)pow(2, s.level-1)+s.order-2;    //将位序转变为树的次序（层序序列） 
    
    return T[i]; 
}

Status Assign_Sq(SqBiTree T, Position s, TElemType_Sq value)
{
    int i =(int)pow(2, s.level-1)+s.order-2;
    
    if(value=='\0' && (T[2*i+1]!='\0' || T[2*i+2]!='\0'))     //元素value是空值但s位序的结点有子树
        return ERROR;
    else if(value!='\0' && T[(i+1)/2-1]=='\0')                 //元素value不为空但s位序的结点无双亲结点
        return ERROR;
    else
        T[i] = value;
    
    return OK; 
}

TElemType_Sq Parent_Sq(SqBiTree T, TElemType_Sq e)
{
    int i;
    
    if(T[0]!='\0')                                //空树 
    {
        for(i=0; i<MAX_TREE_SIZE; i++)
        {
            if(T[i]==e)
                return T[(i+1)/2-1];
        }    
    }
    
    return '\0';                                //未找到e     
}

TElemType_Sq LeftChild_Sq(SqBiTree T, TElemType_Sq e)
{
    int i;
    
    if(T[0]=='\0')
        return '\0';                            //空树

    for(i=0; i<MAX_TREE_SIZE; i++)
    {
        if(T[i]==e)
            return T[2*i+1];
    }
    
    return '\0';                                //未找到e
} 

TElemType_Sq RightChild_Sq(SqBiTree T, TElemType_Sq e)
{
    int i;
    
    if(T[0]=='\0')
        return '\0';                            //空树 

    for(i=0; i<MAX_TREE_SIZE; i++)
    {
        if(T[i]==e)
            return T[2*i+2];
    }
    
    return '\0';                                //未找到e
} 

TElemType_Sq LeftSibling_Sq(SqBiTree T, TElemType_Sq e)
{
    int i;
    
    if(T[0]=='\0')
        return '\0';                            //空树 

    for(i=0; i<MAX_TREE_SIZE; i++)
    {
        if(i%2==0 && T[i]==e)                    //i为偶序数 
            return T[i-1];
    }
    
    return '\0';                                //未找到e
} 

TElemType_Sq RightSibling_Sq(SqBiTree T, TElemType_Sq e)
{
    int i;
    
    if(T[0]=='\0')                     
        return '\0';                            //空树 

    for(i=0; i<MAX_TREE_SIZE; i++)
    {
        if(i%2!=0 && T[i]==e)                    //i为奇序数
            return T[i+1];
    }
    
    return '\0';                                //未找到e
} 

void LevelOrderTraverse_Sq(SqBiTree T, void(Visit)(TElemType_Sq))
{
    int i;
    int len = BiTreeLength_Sq(T);
    
    for(i=0; i<len; i++)
    {
        if(T[i]!='\0')
            Visit(T[i]);
    }
}

void PreOrderTraverse_Sq(SqBiTree T, void(Visit)(TElemType_Sq), int i)
{
    if(T[i]!='\0')
    {
        Visit(T[i]);
        PreOrderTraverse_Sq(T, Visit, 2*i+1);
        PreOrderTraverse_Sq(T, Visit, 2*i+2);
    }    
}

void InOrderTraverse_Sq(SqBiTree T, void(Visit)(TElemType_Sq), int i)
{
    if(T[i]!='\0')
    {
        InOrderTraverse_Sq(T, Visit, 2*i+1);
        Visit(T[i]);
        InOrderTraverse_Sq(T, Visit, 2*i+2);
    }    
}

void PostOrderTraverse_Sq(SqBiTree T, void(Visit)(TElemType_Sq), int i)
{
    if(T[i]!='\0')
    {
        PostOrderTraverse_Sq(T, Visit, 2*i+1);
        PostOrderTraverse_Sq(T, Visit, 2*i+2);
        Visit(T[i]);
    }
}

void Print_Sq(SqBiTree T)
{
    int i, j, level;
    char tmp[MAX_TREE_SIZE][MAX_TREE_SIZE] = {}; 
    
    level = BiTreeDepth_Sq(T);
    
    for(i=1; i<=level; i++)
        for(j=1; j<=(int)pow(2,i-1); j++)
            tmp[i-1][(int)pow(2,level-i)+(j-1)*(int)pow(2,level-i+1)-1] = T[(int)pow(2,i-1)-1+j-1];
    
    for(i=0; i<level; i++)
    {
        for(j=0; j<2*(int)pow(2,level-1)-1; j++)
        {
            if(tmp[i][j]!='\0')
                printf("%c", tmp[i][j]);
            else
                printf(" ");
        }
        printf("\n");
    }
}

双亲表示：

void InitTree_P(PTree *T)
{
    (*T).n = 0;                                        //结点数量 
}

void ClearTree_P(PTree *T)
{
    (*T).n = 0;
}

void DestroyTree_P(PTree *T)
{
    //此存储结构下的树无法销毁 
} 

Status TreeEmpty_P(PTree T)
{
    return (T.n ? FALSE : TRUE); 
} 

Status CreateTree_P(FILE *fp, PTree *T)
{
    TElemType_P ch, p, tmp;
    int i, j;
    
    Scanf(fp, "%c", &ch);
    printf("录入树的根结点 %c \n", ch);
    Scanf(fp, "%c", &tmp);                            //跳过换行符 
    
    if(ch!='^')
    {
        i = 0;                                        //根结点起点设为0
        (*T).nodes[i].data = ch;
        (*T).nodes[i].parent = -1;
        
        j = -1;
        while(!feof(fp))
        {
            Scanf(fp, "%c", &p);
            printf("依次录入 %c 的孩子结点：", p);
            j++;
            while(1)
            {
                Scanf(fp, "%c", &ch);
                if(ch=='^' || ch=='\n')
                {
                    if(ch=='^')
                    {
                        printf("%c", ch);
                        Scanf(fp, "%c", &tmp);        //跳过换行符 
                    }
                        
                    break;
                }
                else
                {
                    printf("%c", ch);
                    i++;
                    (*T).nodes[i].data = ch;
                    (*T).nodes[i].parent = j;
                }
            }
            
            printf("\n");
        }
        
        (*T).n = i+1;        
    }
        
    return OK;
}

int TreeDegree_P(PTree T)
{
    int i, tmp, count;
    int max;
    
    max = count = 0;
    
    if(T.n)
    {
        tmp = T.nodes[0].parent;
        
        for(i=0; i<T.n; i++)
        {
            if(T.nodes[i].parent!=tmp)
            {
                tmp = T.nodes[i].parent;
                count = 1;            
            }
            else
                count++;
            
            if(count>max)
                max = count;
        }        
    }
    
    return max;
}

int TreeDepth_P(PTree T)                                        //由于按层序序列存储，故最后存储的结点必在最大层 
{
    int k, level;
    
    k = T.n-1;
    level = 0;
    
    if(T.n!=0)
    {
        level++;
        k = T.nodes[k].parent;
        
        while(k!=-1)
        {
            level++;
            k = T.nodes[k].parent;
        }
        
    }
    
    return level; 
}

TElemType_P Root_P(PTree T)
{
    if(T.n)
        return T.nodes[0].data;

    return '\0';
}

TElemType_P Value_P(PTree T, int i)
{
    if(T.n && i>0 && i<=T.n)
        return T.nodes[i-1].data;
    else
        return '\0';
}

int Order_P(PTree T, TElemType_P e)
{
    int i;
    int k = -1;
    
    for(i=0; i<T.n; i++)
    {
        if(T.nodes[i].data==e)
        {
            k = i;
            break;
        }
    }
    
    return k;
} 

Status Assign_P(PTree *T, TElemType_P e, TElemType_P value)
{
    int i;
    
    for(i=0; i<(*T).n; i++)
    {
        if((*T).nodes[i].data==e)
        {
            (*T).nodes[i].data = value;
            return OK;
        }
    }
    
    return ERROR;
}

TElemType_P ChildValue_P(PTree T, TElemType_P e, int order)
{
    int i, p, count;
    
    count = 0;
    for(i=1; i<T.n; i++)
    {
        p = T.nodes[i].parent;
        if(T.nodes[p].data==e)
        {
            count++;
            if(count==order)
                return T.nodes[i].data;
        }
    }
    
    return '\0';
}

TElemType_P Sibling_P(PTree T, TElemType_P e, int mark)
{
    int i;
    
    if(!TreeEmpty_P(T) && e!=T.nodes[0].data)
    {
        for(i=1; i<T.n; i++)
        {
            if(mark==0)                                        //左兄弟
            {
                if(T.nodes[i].data==e)
                    break;

                if(T.nodes[i].data!=e && i+1<T.n && T.nodes[i+1].parent==T.nodes[i].parent && T.nodes[i+1].data==e)
                    return T.nodes[i].data;
            }
            
            if(mark==1)                                        //右兄弟 
            {
                if(T.nodes[i].data==e && i+1<T.n && T.nodes[i].parent==T.nodes[i+1].parent)
                    return T.nodes[i+1].data;    
            } 
        }    
    }

    
    return '\0';
}

int ChildCount_P(PTree T, TElemType_P p)
{
    int k1, k2, count;
    
    if(TreeEmpty_P(T))                        //空树 
        return -1;

    k1 = Order_P(T, p);
    
    if(k1<0)                                //p结点不存在 
        return -2;
    
    k2 = k1 + 1;
    count = 0;
    while(k2<T.n)                            //统计孩子个数 
    {
        if(T.nodes[k2].parent==k1)
            count++;
        if(T.nodes[k2].parent>k1)
            break;
        k2++;
    }

    return count;
}

int ChildSeat_P(PTree T, TElemType_P p, int i)
{
    int k0, k1, k2, count;
    
    if(TreeEmpty_P(T))                            //空树 
        return -1;
    
    k0 = ChildCount_P(T, p);        //k0标记孩子个数 
    
    if(i<0 || k0<0 || i>k0+1)        //插入位置不正确 
        return -2;
    
    k1 = Order_P(T, p);

    k2 = k1 + 1;    
    if(i==0)                        //此时i为p最后一个结点的下一个位置
    {
        while(k2<T.n)
        {
            if(T.nodes[k2].parent>k1)
                break;
            k2++;
        }
    } 
    else
    {
        count = 0;
        
        while(k2<T.n)
        {
            if(T.nodes[k2].parent>=k1)
            {
                count++;
                if(count==i)
                    break;
            }
            
            k2++;
        }
    }

    return k2;    
}

Status InsertChild_P(PTree *T, TElemType_P p, int i, TElemType_P e)
{
    int k0, start, end;
    
    if(TreeEmpty_P((*T)) || !e)                //空树或e为空字符 
        return ERROR;

    k0 = 0;                                    //k0标记p的位置 
    while(k0<(*T).n)
    {
        if((*T).nodes[k0].data==p)
            break;
        k0++;
    }    
    
    if(k0==(*T).n)                            //p不存在 
        return ERROR;
    
    start = ChildSeat_P(*T, p, i);            //e结点的插入位置 
    if(start<=0)                            //插入位置不正确 
        return ERROR;
    
    end = (*T).n;
    while(end>start)
    {
        (*T).nodes[end].data = (*T).nodes[end-1].data;
        if((*T).nodes[end-1].parent<start)
            (*T).nodes[end].parent = (*T).nodes[end-1].parent;
        else
            (*T).nodes[end].parent = (*T).nodes[end-1].parent+1;
        end--;
    }
    
    (*T).nodes[start].data = e;
    (*T).nodes[start].parent = k0;
    (*T).n++;
    
    return OK;
}

Status InsertTree_P(PTree *T, TElemType_P p, int i, PTree t)
{
    int k;
    
    if(TreeEmpty_P((*T)) || TreeEmpty_P(t))                //空树 
        return ERROR;

    for(k=0; k<t.n; k++)
    {
        if(k==0)
            InsertChild_P(T, p, i, t.nodes[k].data);
        else
            InsertChild_P(T, t.nodes[t.nodes[k].parent].data, 0, t.nodes[k].data);
    }

    return OK; 
}

Status DeleteTree_P(PTree *T, TElemType_P p, int i)
{
    int k1;                                            //k1标记p的位置 
    int k2 , count;                                    //k2标记第i棵子树起点 
    int k3;
    int stack[MAX_TREE_SIZE], m, n;
    int k4, k5, order[MAX_TREE_SIZE] = {};
    
    for(k1=0; k1<(*T).n; k1++)
    {
        if((*T).nodes[k1].data==p)
            break;
        if(k1==(*T).n-1)
            return ERROR;        
    }
    
    count = 0;        
    for(k2=k1+1; k2<(*T).n; k2++)
    {
        if((*T).nodes[k2].parent==k1)
        {
            count++;
            if(count==i)
                break;
        }
        if(k2==(*T).n-1)
            return ERROR;        
    }
    
    m = n = 0;
    stack[n] = k2;
    n++; 
    (*T).nodes[k2].data = '\0';                    //抹掉此处的值
    
    k3=k2+1;
    while(k3<(*T).n && m<n)
    {        
        if((*T).nodes[k3].parent<stack[m])
            k3++;
        else if((*T).nodes[k3].parent>stack[m])
            m++;
        else        //(*T).nodes[k3].parent==stack[m]
        {
            (*T).nodes[k3].data = '\0';                    //抹掉此处的值
            stack[n] = k3;
            n++;
            k3++;
        }        
    }
    
    k5 = 0;
    for(k4=0; k4<(*T).n; k4++)                            //遍历树，找出各结点现在的实际位置 
    {
        if((*T).nodes[k4].data)
        {
            order[k4] = k5;
            k5++;
            
            if(k4)                                        //不为头结点 
                (*T).nodes[k4].parent = order[(*T).nodes[k4].parent];    //当前结点双亲结点位置发生变化 
        }
    }
    
    k4 = -1;
    k5 = 0;
    while(k5<(*T).n)                                        //遍历，去掉删除的结点 
    {
        if((*T).nodes[k5].data)
        {
            k4++;
            (*T).nodes[k4].data = (*T).nodes[k5].data;
            (*T).nodes[k4].parent = (*T).nodes[k5].parent;
        }
        
        k5++;
    }
        
    (*T).n = k4+1;
    
    return OK; 
}

void LevelOrderTraverse_P(PTree T, void(Visit)(TElemType_P))
{
    int i;
    
    for(i=0; i<T.n; i++)
        Visit(T.nodes[i].data);
}

void Print_P(PTree T)
{
    int row[MAX_TREE_SIZE];                        //各结点实际所处行 
    int col[MAX_TREE_SIZE];                        //各结点在其兄弟中的次序 
    int i, j, tmp;                                //tmp存放当前结点的父结点位置 
    int x[MAX_TREE_SIZE], y[MAX_TREE_SIZE];        //存放各结点打印时所处行和列（从0开始计数） 
    int count;
    int t[MAX_TREE_SIZE][MAX_TREE_SIZE]={};        //孩子链表存储结构 
    char a[MAX_TREE_SIZE][MAX_TREE_SIZE]={};    //按树的形状存放结点 
    SqStack S;
    SElemType_Sq e;

    if(T.n)
    {    
        j = 1;                                //j统计某孩子次序 
        row[0] = 1;
        col[0] = j;
        tmp = T.nodes[0].parent;
                
        for(i=1; i<T.n; i++) 
        {
            if(T.nodes[i].parent!=tmp)
            {
                j = 1;                            //若与上一个结点不属于同一双亲结点，则重新开始计数 
                tmp = T.nodes[i].parent;
            }
            else
                j++;
            
            col[i] = j;    
            row[i] = row[T.nodes[i].parent]+1;                
        }    
        
        for(i=1; i<T.n; i++)                                    //构造孩子链表 
        {
            tmp = T.nodes[i].parent;
            t[tmp][col[i]-1] = i;
        }
        
        count = 0;                                                //追踪行 
        InitStack_Sq(&S);
        Push_Sq(&S, 0);
        while(!StackEmpty_Sq(S))                                    //确定每个结点在树中所在行                
        {
            GetTop_Sq(S, &e);
            if(col[e]!=1)
                count++;
            x[e] = count;

            if(t[e][0])
                Push_Sq(&S, t[e][0]);            
            else
            {
                while(!StackEmpty_Sq(S))
                {
                    Pop_Sq(&S, &e);
                    if(t[T.nodes[e].parent][col[e]])
                    {
                        Push_Sq(&S, t[T.nodes[e].parent][col[e]]);
                        break;
                    }
                }
            }
            
        }

        for(i=0; i<T.n; i++)                                        //确定每个结点在树中所在列 
            y[i] = row[i]-1;

        for(i=0; i<T.n; i++)                                        //将各结点放入a中适当位置 
            a[x[i]][2*y[i]] = T.nodes[i].data;
                    
        for(i=0; i<=count; i++)
        {
            for(j=0; j<=2*y[T.n-1]; j++)
            {
                if(a[i][j])
                    printf("%c", a[i][j]);
                else
                    printf(".");
            }
                
            printf("\n");        
        }
    }
    else
        printf("空树无法打印！！\n");
}