二叉樹的順序實現

//
//  main.c
//  SqBiTree
//
//  Created by Eason on 2020/8/7.
//  Copyright ? 2020 Eason. All rights reserved.
//

#include <stdio.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
typedef int Status;  //作為返回狀態 如ERROR OK FALSE TRUE，其實也就是返回一個int值
typedef int ElemType;   //元素數據類型，這里就先定義為int
typedef ElemType BiTree[MAXSIZE];   //二叉樹的元素存儲數組，通過數組的下標實現二叉樹結構
//這里一定要注意的是這里存儲容量MAXSIZE 因為獲取孩子的判斷是要判斷T[2*MAXSIZE]這個數量級的，所以實際存儲容量要比真實存儲的內容大一倍
//比如放了10個元素，這時候我的存儲容量至少為21以上，不然判斷的時候數組越界會報錯，數值原因見獲取孩子方法
ElemType null=0;   //將0作為空元素

//初始化一個二叉樹
Status initTree(BiTree T){
    for(int i=0;i<MAXSIZE;i++){   //將二叉樹中所有元素位置置為空元素標志null即0
        T[i] = null;  //即將空元素存入
    }
    printf("二叉樹初始化完成\n");
    return OK;
}

//清空一個二叉樹(也可以使用#define clearTree initTree)
Status clearTree(BiTree T){   //同初始化一個二叉樹相同
    for(int i=0;i<MAXSIZE;i++){
        T[i] = null;
    }
    return OK;
}

//創建一個二叉樹
Status creatBTree(BiTree T){
    printf("創建一個元素為1-10的二叉樹\n");
    int i=0;   //當前數組位置計位器
    int data=1;   //存入的數據元素
    while(data<=10){   //準備存入1-10
        T[i]=data;   //將當前數據元素存入當前數組位置處
        if(i!=0 && i>=MAXSIZE && T[(i+1)/2-1]==null && T[i]!=0){   //即當前結點是非根無雙親且不為空的結點，即為一個懸浮的結點，那么是不能給這個結點賦值的
            printf("出現了無雙親的非根結點\n");
            return ERROR;
        }
        i++;   //數組位置進一
        data++;   //數據元素+1
    }
    return OK;
}

//判斷二叉樹是否為空
Status isEmpty(BiTree T){
    if(T[0]==null){   //若二叉樹沒有根結點，則表明當前二叉樹是空二叉樹
        return TRUE;
    }else{
        return FALSE;
    }
}

//獲取當前二叉樹的根結點數據
Status getRoot(BiTree T, int *e){
    if(isEmpty(T)){   //如果當前二叉樹為空，則沒有根結點
        printf("當前二叉樹為空，無根結點數據\n");
        return ERROR;
    }
    *e = T[0];   //如果不為空則將根結點的數據存入e中供返回查看
    return OK;
}

//獲取二叉樹的深度
int getDepth(BiTree T){
    int i;   //數組位置計位器
    for(i=MAXSIZE-1;i>=0;i--){   //從二叉樹數組的最后位置向前找
        if(T[i]!=null){   //找到最后一個不為空的元素后推出循環
            break;
        }
    }
    i++;   //將i作為位置
    int depth = 1;   //初始depth為1
    while(i>=powl(2, depth)){   //2的depth次方，當2的depth次方大于當前最后元素位置時，depth就為當前二叉樹的深度
        depth++;   //若當前深度仍不包含最后一個元素，則繼續加深深度
    }
    return depth;   //返回深度值
}

//獲取二叉樹某個結點的parent（獲取二叉樹中e元素的雙親結點元素）
ElemType getParent(BiTree T, ElemType e){
    if(isEmpty(T)){   //判斷當前二叉樹是否為空
        printf("二叉樹為空，無法查找\n");
        return ERROR;
    }
    for(int i=0;i<MAXSIZE;i++){   //尋找指定數值結點的位置
        if(T[i]==e){   //若當前位置元素與指定元素相等
            return T[(i+1)/2-1];   //則返回此位置元素的雙親結點數據，若返回0則表示無雙親結點
        }
    }
    printf("二叉樹中無此結點，無法查找\n");
    return ERROR;
}

//獲取二叉樹某個結點的左孩子（獲取二叉樹中e元素的左孩子）
ElemType getLeftChild(BiTree T, ElemType e){
    if(isEmpty(T)){   //判斷當前二叉樹是否為空
        printf("二叉樹為空，無法查找\n");
        return ERROR;
    }
    for(int i=0;i<MAXSIZE;i++){   //尋找指定數值結點的位置
        if(T[i]==e){   //若當前位置元素與指定元素相等
            return T[i*2+1];   //則返回此位置元素的左孩子結點的數據，若返回0則表示無左孩子
        }
    }
    return ERROR;
}

//獲取二叉樹某個結點的右孩子（獲取二叉樹中e元素的右兄弟）
ElemType getRightChild(BiTree T, ElemType e){
    if(isEmpty(T)){   //判斷當前二叉樹是否為空
        printf("二叉樹為空，無法查找\n");
        return ERROR;
    }
    for(int i=0;i<MAXSIZE;i++){   //尋找指定數值結點的位置
        if(T[i]==e){   //若當前位置元素與指定元素相等
            return T[i*2+2];   //則返回此位置元素的右孩子結點的數據，若返回0則表示無右孩子
        }
    }
    return ERROR;
}

//獲取二叉樹某個結點的左兄弟（獲取二叉樹中e元素的左兄弟）
ElemType getLeftBrother(BiTree T, ElemType e){
    if(isEmpty(T)){   //判斷當前二叉樹是否為空
        printf("二叉樹為空，無法查找\n");
        return ERROR;
    }
    for(int i=0;i<MAXSIZE;i++){   //尋找指定數值結點的位置
        if(T[i]==e && i%2==0){   //若當前位置元素與指定元素相等，并且本身位置為右
            return T[i-1];   //則返回此位置右孩子的數據
        }
    }
    return 0;   //若無可滿足條件的元素則返回0，也就是說若返回0則表示這個結點是左結點，也可能是沒有左兄弟
}

//獲取二叉樹某個結點的右兄弟（獲取二叉樹中e元素的右兄弟）
ElemType getRightBrother(BiTree T, ElemType e){
    if(isEmpty(T)){   //判斷當前二叉樹是否為空
        printf("二叉樹為空，無法查找\n");
        return ERROR;
    }
    for(int i=0;i<MAXSIZE;i++){   //尋找指定數值結點的位置
        if(T[i]==e && i%2!=0){   //若當前位置元素與指定元素相等，并且本身位置為左
            return T[i+1];   //則返回此位置左孩子的數據
        }
    }
    return 0;   //若無可滿足條件的元素則返回0，也就是說若返回0則表示這個結點是右結點，也可能是沒有又兄弟
}

//獲取某指定位置的結點數據（獲取二叉樹中第level層第num個結點元素）
ElemType getValue(BiTree T, int level, int num){
    if(isEmpty(T)){   //判斷當前二叉樹是否為空
        printf("二叉樹為空，無法查找\n");
        return ERROR;
    }
    return T[(int)pow(2, level-1)+num-2];
}

//替換某指定位置的結點數據（將二叉樹第level層第num個數據元素替換為value)
Status replace(BiTree T, int level, int num, ElemType value){
    int i = (int)pow(2, level-1)+num-2;   //將指定的level層第num個數據元素替換成在數組中的下標位置
    if(T[i+1/2-1]==null){   //若指定位置的結點無雙親結點則無法賦值
        printf("此結點的雙親結點為空，無法賦值\n");
        return ERROR;
    }
    if(value==null && (T[i*2+1]!=null || T[i*2+2]!=null)){   //若此結點有孩子結點那么則不可為這個結點賦控制
        printf("此結點的孩子結點不為空，不可以為其賦空值\n");
        return ERROR;
    }
    T[i] = value;   //將value存入指定位置
    return OK;
}

//--------------------二叉樹的遍歷----------------------
//均利用遞歸的方式進行遍歷
//先序訪問輸出（供先序遍歷調用）
void preOrderVisit(BiTree T, int now){   //先序遍歷即先訪問根結點然后遍歷左子樹最后訪問右子樹
    printf("%d ", T[now]);   //訪問當前結點數據并打印
    if(T[now*2+1]!=null){   //若當前位置有左子樹則先訪問左子樹
        preOrderVisit(T, now*2+1);   //訪問左子樹
    }
    if(T[now*2+2]!=null){   //若當前位置有右子樹則訪問右子樹
        preOrderVisit(T, now*2+2);    //訪問右子樹
    }
}
//先序遍歷
Status preOrderTraverse(BiTree T){
    if(isEmpty(T)){   //判斷二叉樹是否為空
        printf("二叉樹為空，無法遍歷\n");
        return ERROR;
    }
    preOrderVisit(T, 0);   //調用前序遍歷函數
    printf("\n");
    return OK;
}

//中序訪問輸出（供中序遍歷調用）
void inOrderVisit(BiTree T, int now){   //中序遍歷即先遍歷左子樹后訪問根結點最后遍歷右子樹（參考前序遍歷，只是訪問次序變更）
    if(T[now*2+1]!=null){
        inOrderVisit(T, now*2+1);
    }
    printf("%d ", T[now]);
    if(T[now*2+2]!=null){
        inOrderVisit(T,now*2+2);
    }
}

//中序遍歷
Status inOrderTraverse(BiTree T){
    if(isEmpty(T)){
        printf("二叉樹為空，無法遍歷\n");
        return ERROR;
    }
    inOrderVisit(T, 0);
    printf("\n");
    return OK;
}

//后序訪問輸出（供后序遍歷使用）
void postOrderVisit(BiTree T, int now){   //后序遍歷即先遍歷左子樹后遍歷右子樹最后訪問根結點（參考前序遍歷，只是訪問次序變更）
    if(T[now*2+1]!=null){
        postOrderVisit(T,now*2+1);
    }
    if(T[now*2+2]!=null){
        postOrderVisit(T,now*2+2);
    }
    printf("%d ", T[now]);
}

//后序遍歷
Status postOrderTraverse(BiTree T){
    if(isEmpty(T)){
        printf("二叉樹為空，無法遍歷\n");
        return ERROR;
    }
    postOrderVisit(T, 0);
    printf("\n");
    return OK;
}

//層序遍歷
Status levelOrderTraverse(BiTree T){   //即一層一層的訪問元素，這里主要是判斷哪些元素在哪一層
    if(isEmpty(T)){  //判斷二叉樹是否為空
        printf("二叉樹為空，無法遍歷\n");
        return ERROR;
    }
    int level = 1;   //初始為第一層
    int e;   //用于存儲獲取的元素數值
    for(int i=level;i<=getDepth(T);i++){   //從第一層到此二叉樹的深度
        printf("第%d層：", i);   //打印當前層數
        for(int j=1;j<=pow(2,i-1);j++){   //從本層的第一個元素到本層的最后元素
            e = getValue(T, i, j);   //獲取當前位置的元素數值
            printf("%d ", e);   //訪問并打印當前獲得的元素數值
        }
        printf("\n");
    }
    return OK;
}

//測試
int main(int argc, const char * argv[]) {
    BiTree T;
    int e;
    initTree(T);
    printf("初始化后的二叉樹是否為空？（1是0否）：%d\n", isEmpty(T));
    creatBTree(T);
    printf("創建完成后二叉樹是否為空？（1是0否)：%d\n", isEmpty(T));
    printf("前序遍歷二叉樹T：\n");
    preOrderTraverse(T);
    printf("中序遍歷二叉樹T：\n");
    inOrderTraverse(T);
    printf("后序遍歷二叉樹T：\n");
    postOrderTraverse(T);
    printf("層序遍歷二叉樹T：\n");
    levelOrderTraverse(T);
    getRoot(T, &e);
    printf("當前二叉樹的根結點為：%d\n", e);
    printf("當前二叉樹的深度為：%d\n", getDepth(T));
    e = getParent(T, 5);
    printf("結點5的parent為：%d\n", e);
    e = getLeftBrother(T, 5);
    printf("結點5的左兄弟為：%d\n", e);
    e = getRightBrother(T, 5);
    printf("結點5的右兄弟為：%d\n", e);
    e = getLeftChild(T, 5);
    printf("結點5的左孩子為：%d\n", e);
    e = getRightChild(T, 5);
    printf("結點5的右孩子為：%d\n", e);
    e = getValue(T, 4, 2);
    printf("獲取第4層的第2個元素：%d\n", e);
    replace(T, 4, 2, 666);
    e = getValue(T, 4, 2);
    printf("將第4層的第2個元素替換為666后得：%d\n", e);
    printf("將二叉樹清空后可得：\n");
    clearTree(T);
    levelOrderTraverse(T);
    return 0;
}