拓展：顺序存储结构相关

 1、二叉树的建立---顺序存储
 2、顺序存储结构的遍历
 3、二叉树的顺序存储结构转化为链式存储结构
 4、二叉树的链式存储结构转化为顺序存储结构

/**
 * 拓展 ：顺序存储结构相关
 *
 * ①算法思想
 * 1、二叉树的建立---顺序存储
 * 2、顺序存储结构的遍历
 * 3、二叉树的顺序存储结构转化为链式存储结构
 * 4、二叉树的链式存储结构转化为顺序存储结构
 *
 * ②算法设计
 */
 
#include <stdio.h>
#include <iostream>
#define MaxSize 100
 
typedef struct BiTreeNode{
    int data;
    BiTreeNode *lchild,*rchild;
}BiTreeNode,*BiTree;
 
 
//1、二叉树的建立---顺序存储
#define MaxSize 100
struct BiTreeNodeArr{
    int data[MaxSize];
    int length;
};
//假设下标从0开始
void CreatBiTree_0(int arr[],int root,int n){//root用来记录下标
    int data;
    scanf("%d",&data);
    if(data == -1){
        arr[root] = data;
        return;
    }
    if(root * 2 + 1 <= n - 1)
        CreatBiTree_0(arr,root * 2 + 1,n);
    if(root * 2 + 2 <= n - 1)
        CreatBiTree_0(arr,root * 2 + 2,n);
}
//假设下标从1开始
void CreatBiTree_1(int arr[],int root,int n){//root用来记录下标
    int data;
    scanf("%d",&data);
    if(data == -1){
        arr[root] = data;
        return;
    }
    if(root * 2 <= n - 1)
        CreatBiTree_1(arr,root * 2,n);
    if(root * 2 + 1 <= n - 1)
        CreatBiTree_1(arr,root * 2 + 1,n);
}
 
 
 
//2、顺序存储结构的遍历
//假设下标从1开始
//①先序遍历
void PreOrderSq(int node[],int root,int n){
    if(root <= n - 1 && node[root] != -1){//当node数组中有节点时
        printf("%d ",node[root]);
        PreOrderSq(node,2 * root,n);
        PreOrderSq(node,2 * root + 1,n);
    }
}
//②中序遍历
void InOrderSq(int node[],int root,int n){
    if(root <= n - 1 && node[root] != -1){//当node数组中有节点时
        InOrderSq(node,2 * root,n);
        printf("%d ",node[root]);
        InOrderSq(node,2 * root + 1,n);
    }
}
//③后序遍历
void PostOrderSq(int node[],int root,int n){
    if(root <= n - 1 && node[root] != -1){//当node数组中有节点时
        PostOrderSq(node,2 * root,n);
        PostOrderSq(node,2 * root + 1,n);
        printf("%d ",node[root]);
    }
}
 
 
 
//3、二叉树的顺序存储结构转化为链式存储结构
//假设下标从 1 开始,非递归转换
struct Node{
    BiTree T;
    int num;//num代表T节点在顺序存储的节点数组中的位置
};//用结构体把T和他在数组中的位置做一个绑定
//采用层次建立的方式
BiTree BuildSqToLinkByLevel(int arr[],int n){
    Node Queue[MaxSize],p;//p每次出队的时候要用到
    int front = -1,rear = -1;//用来标记Queue
    //先做一个深度的绑定
    BiTree T = (BiTree)malloc(sizeof(BiTreeNode));
    T -> data = arr[1];
    Queue[++rear] = {T,1};//相当于Queue[rear].T = T;Queue[rear].num = 1;
    //层次建立链式存储的二叉树
    while(front != rear){
        p = Queue[++front];//出队一个元素
        //创建左孩子
        if(arr[p.num * 2] == -1 || p.num * 2 > n)
            p.T -> lchild = NULL;
        else{
            p.T -> lchild = (BiTree)malloc(sizeof(BiTreeNode));
            p.T -> lchild -> data = arr[p.num * 2];
            Queue[++rear] = {p.T -> lchild,p.num * 2};
        }
        //创建右孩子
        if(arr[p.num * 2 + 1] == -1 || p.num * 2 + 1 > n)
            p.T -> rchild = NULL;
        else{
            p.T -> rchild = (BiTree)malloc(sizeof(BiTreeNode));
            p.T -> rchild -> data = arr[p.num * 2 + 1];
            Queue[++rear] = {p.T -> rchild,p.num * 2 + 1};
        }
    }
}
 
 
//4、二叉树的链式存储结构转化为顺序存储结构
//假设下标从 1 开始,递归转换
BiTree BuildLinkToSq(BiTree T,int arr[],int root){
    if(T){
        arr[root] = T -> data;
        BuildLinkToSq(T -> lchild,arr,root * 2);
        BuildLinkToSq(T -> rchild,arr,root * 2 + 1);
    }
}