二叉树的顺序存储

前言

顺序存储结构难些。因为树是一种一对多的数据结构，由于它的特殊性使用顺序存储结构也可以实现。

顺序存储二叉树：

二叉树的顺序存储结构就是一维数组存储二叉树中的节点，并且节点的存储位置，也就是数组下标要能体现节点之间的关系，比如双亲和孩子的关系。左右兄弟关系等。

来看看一颗完全二叉树的顺序存储：

将这两颗树存储到数组里面，注意下标的表示位置

这下子可以看出完全二叉树的优越性来了把。然而也有出现一些极端的情况，如

这种普通的二叉树显然是对存储空间的浪费，所以遇到这种情况的二叉树，建议使用链式二叉树，我们的顺序存储二叉树适合使用在完全二叉树下

#include <stdio.h>
#include "stdlib.h"  
#include "io.h"  
#include "math.h" 
#include "time.h" 

#define MAXSIZE 100
#define MAX_TREE_SIZE 100
typedef int Status;        /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int TElemType;  /* 树结点的数据类型，目前暂定为整型 */
typedef int SqBiTree[MAX_TREE_SIZE];/* 0号单元存储根结点  */

typedef struct{
    /* 结点的层,本层序号(按满二叉树计算) */
    int level,order;
}Position;

//假设整数0代表为空
int Nil = 0;

//构造空的二叉树，因为T是固定数组，不会改变，故不需要&
Status InitBiTree(SqBiTree T){
    int I;
    for(i=0; i<MAX_TREE_SIZE; i++){
        T[i] = Nil; //初始值为空
    }
    return 1;
}

//按层序次序输入二叉树的节点的值(字符型或整形)，构造顺序存储二叉树
Status CreateBiTree(SqBiTree T){
    int i =0;
    printf("请按层序输入结点的值(整型)，0表示空结点，输999结束。结点数≤%d:\n",MAX_TREE_SIZE);
    while(i<=10){
        T[i] = I+1;
        if(i!=0&&T[(i+1)/2-1] == Nil&&T[i]!=Nil){
            printf("出现了无双亲且非根节点%d\n",T[i]);
            exit(0);
        }
        I++;
    }
    //然后将后面的值赋值为空
    while(i<MAX_TREE_SIZE){
        T[i] = Nil;
        I++;
    }
    return 1;
}

//清空二叉树，在顺序存储中，两函数完全一样
#define ClearBiTree InitBiTree

/* 初始条件: 二叉树T存在 */
/* 操作结果: 若T为空二叉树,则返回TRUE,否则FALSE */
Status BiTreeEmpty(SqBiTree T){
    if(T[0] == Nil){
        return 1;
    }
    return 0;
}

/* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */
Status BiTreeDepth(SqBiTree T){
    //性质2：深度为k的二叉树至多有2^k个节点
    int k = 0;
    while(powl(2,k)<=(10+1)){
        k++;
    }
    return k;
}

/* 初始条件: 二叉树T存在 */
/* 操作结果:  当T不空,用e返回T的根,返回OK;否则返回ERROR,e无定义 */
Status Root(SqBiTree T){
    TElemType root;
    if(BiTreeEmpty(T)){
        return 0;
    }else{
        root = T[0];
        return root;
    }
}

/* 初始条件: 二叉树T存在,e是T中某个结点(的位置) */
/* 操作结果: 返回处于位置e(层,本层序号)的结点的值 */
Status Value(SqBiTree T,Position e){
    if(e.order <= powl(2,e.level-1)) //不超过每层的节点数
        return T[(int)powl(2,e.level-1)+e.order-2];
    else
        return 0;
}

/* 初始条件: 二叉树T存在,e是T中某个结点(的位置) */
/* 操作结果: 给处于位置e(层,本层序号)的结点赋新值value */
Status Assign(SqBiTree T,Position e,TElemType value){
    int index = (int)powl(2,e.level-1)+e.order-2;
    //值不为空，且双亲节点不存在时
    if(value!= Nil&&T[(index+1)/2-1]==Nil){
        return 0;
    }
    /*  给双亲赋空值但有叶子 */
    else if(value == Nil && (T[index*2+1]!=Nil || T[index*2+2]!=Nil)){
        return 0;
    }
    T[index] = value;
    return 1;
}

//求一个节点的双亲节点
TElemType Parent(SqBiTree T,Position e){
    int index = 0;
    index = (int)powl(2,e.level-1)+e.order-2;
    //为空树或者只有根节点
    if(T[0] == Nil ||(T[2*index+1]==Nil || T[2*index+2]==Nil)){
        return 0;
    }else{
        if(index%2==0)
            return T[index/2-1];
        else
            return T[index/2];
    }
    return 0;
}

//求一个节点的左孩子节点
TElemType LeftChild(SqBiTree T,Position e){
    int index = 0;
    index = (int)powl(2,e.level-1)+e.order-2;
    if(T[0] == Nil ||(T[2*index+1]==Nil || T[2*index+2]==Nil)){
        return 0;
    }else{
        return T[2*index+1];
    }
}

//求一个节点的右孩子节点
TElemType RightChild(SqBiTree T,Position e){
    int index = 0;
    index = (int)powl(2,e.level-1)+e.order-2;
    if(T[0] == Nil ||(T[2*index+1]==Nil || T[2*index+2]==Nil)){
        return 0;
    }else{
        return T[2*index+2];
    }
}


//求一个节点的左兄弟节点
TElemType LeftSibling(SqBiTree T,Position e){
    int index = 0;
    index = (int)powl(2,e.level-1)+e.order-2;
    if(T[0] == Nil ||(T[2*index+1]==Nil || T[2*index+2]==Nil)){
        return 0;
    }else{
        if(index%2==0)
            return T[index-1];
        else 
            return 0;
    }
}

//求一个节点的左兄弟节点
TElemType RightSibling(SqBiTree T,Position e){
    int index = 0;
    index = (int)powl(2,e.level-1)+e.order-2;
    if(T[0] == Nil ||(T[2*index+1]==Nil || T[2*index+2]==Nil)){
        return 0;
    }else{
        if(index%2==0){
            return 0;
        }            
        else 
            return T[index+1];
    }
}
//////////////////////////遍历////////////////////////////
//先序遍历的原则(递归)：
void PreTraverse(SqBiTree T,int index){
    printf("%d ",T[index]);
    if(T[2*index+1]!=Nil){
        PreTraverse(T,2*index+1);
    }
    if(T[2*index+2]!=Nil){
        PreTraverse(T,2*index+2);
    }
}
void PreOrderTraverse(SqBiTree T){
    if(!BiTreeEmpty(T)){
        PreTraverse(T,0);
    }
    printf("\n");
}

//中序遍历原则：
void InTraverse(SqBiTree T,int index){

    if(T[2*index+1]!=Nil){
        InTraverse(T,2*index+1);
    }
    printf("%d ",T[index]);
    if(T[2*index+2]!=Nil){
        InTraverse(T,2*index+2);
    }
}
void InOrderTraverse(SqBiTree T){
    if(!BiTreeEmpty(T)){
        InTraverse(T,0);
    }
    printf("\n");
}

//后序遍历原则：
void PostTraverse(SqBiTree T,int index){

    if(T[2*index+1]!=Nil){
        PostTraverse(T,2*index+1);
    }
    if(T[2*index+2]!=Nil){
        PostTraverse(T,2*index+2);
    }
    printf("%d ",T[index]);
}
void PostOrderTraverse(SqBiTree T){
    if(!BiTreeEmpty(T)){
        PostTraverse(T,0);
    }
    printf("\n");
}



int main(){

    SqBiTree T;
    InitBiTree(T);
    //创建二叉树
    CreateBiTree(T);

    //判断是否为空
    printf("二叉树是否为空:%d\n",BiTreeEmpty(T));

    //清空二叉树后    
    //判断是否为空
    printf("二叉树是否为空:%d\n",ClearBiTree(T));
    //重新创建二叉树
    CreateBiTree(T);

    //树的深度
    printf("树的深度：%d\n",BiTreeDepth(T));

    //树根
    printf("树的根节点：%d\n",Root(T));

    //寻找某一层某个特地的元素
    Position e;
    e.level = 2;
    e.order = 2;
    printf("2层第2个是：%d\n",Value(T,e));

    //修改节点元素
    Assign(T,e,50);
    printf("2层第2个是：%d\n",Value(T,e));

    //求节点双亲
    printf("2层第2个的双亲是：%d\n",Parent(T,e));

    //求节点左孩子
    printf("2层第2个的左孩子是：%d\n",LeftChild(T,e));

    //求节点右孩子
    printf("2层第2个的左孩子是：%d\n",RightChild(T,e));
    

    //求节点左兄弟
    printf("2层第2个的左兄弟是：%d\n",LeftSibling(T,e));
    //求节点右兄弟
    printf("2层第2个的右兄弟是：%d\n",RightSibling(T,e));


    //先序遍历
    printf("先序遍历\n");
    PreOrderTraverse(T);

    //中序遍历
    printf("中序遍历\n");
    InOrderTraverse(T);

    //后序遍历
    printf("后序遍历\n");
    PostOrderTraverse(T);
    return 0;
}